What to do with constants for results of InfeasibilityCertificate

[blegat]

When the status is InfeasibilityCertificate, the results should be the result of the homogenized version.
For instance, for the problem

min x
x <= -1
x >= 0

with dual

max -y
1 - y >= 0
y <= 0

or equivalently

max -y
1 - y - z = 0
y <= 0
z >= 0

The dual has an infeasibility ray y = -1 (with z = 1). When asking for the constraint dual of x >= 0, this the value of the constraint 1 - y >= 0 in the first case or to the value of z in the second case.
In the first case, one could think it should be 1 - (-1) = 2 but it should be z = 1 in the second case.
The reason is that since it is a ray, it is a feasible solution to the problem with the constant terms removed (which is equivalent to setting the objective of the primal to zero).

By consistency, the when asking for ConstraintPrimal when the primal status is InfeasibilityRay, it should also not take the constant of the function into account.

Moreover, if the objective function has a constant, then it should not be included in the value of the objective value / objective bound for InfeasibilityRay.
Indeed, the objective can be moved to a constrant by adding a new variable and then by consistency, it should not be included since it is in a constraint.

Currently, in MOI.Test, we have tests with infeasibility rays in the dual and the values expected by the tests are the correct ones. The reason is that the MOI definition of the dual is the second case of the introduction example above.
However, we have not test with the objective of the dual nor with infeasibility ray in the primal and for these it is might be much more confusing.

What do you think ? Do you agree that the constants should be removed from the results of rays in ConstraintPrimal and objective value/bound ?
If yes, we should:

• Add a section about this in the doc
• Thoroughly test it
• Test ConstraintPrimal of VectorizeBridge with a DUAL_INFEASIBLE example with nonzero constant for a scalar constraint

[mlubin]

I think this isn't tested because it's a pretty uncommon question to ask. How do solvers like Mosek behave? Will the wrappers get homogenized values back from the solvers or will they have to compute them?

[blegat]

The solvers seem to return the homogenized values for dual certificates as the MOI tests requires the homogenized values and currently, there has been no complaint.
For the objective, most of the solvers do not support constants in the objective so it's the wrapper's job to not put the constant. For primal certificates I guess solvers also give the homogenized version but we'll have to check. What's tricky for primal is that some wrappers might play with the constant in the function and then add it manually when the user ask for ConstraintPrimal. In that case, that might introduce a but when asking for the constraint primal. Also when the dual bounds of the variables are built manually (e.g. JuliaOpt/LinQuadOptInterface.jl#41), when the status of the dual is InfeasibilityCertificate, the objective of the primal should not be added.

[odow]

Related TODOs:

• MathOptInterface.jl/src/Bridges/Constraint/scalarize.jl

  Line 143 in 7923c60

  # TODO do no add constant if the primal status is a ray like in Vectorize

• MathOptInterface.jl/src/Utilities/results.jl

  Line 22 in d816122

  # TODO do not include constant if primal solution is a ray

• MathOptInterface.jl/src/Utilities/results.jl

  Line 176 in d816122

  # TODO do not include constant if primal solution is a ray

[odow]

Indeed, the objective can be moved to a constraint by adding a new variable and then by consistency, it should not be included since it is in a constraint.

Yes, I think this is the right way to think about it. I'll add a background section on this in the documentation.