getsolution() returns infeasible solution for an unbounded problem

[blegat]

On this problem,

Min y
s.t. x >= 1
loadproblem!(m, [1. 0.], [-Inf, -Inf], [Inf, Inf], [0., 1.], [1.], [Inf], :Min)

calling optimize! returns :Unbounded and then getsolution gives [6.93747e-310,0.0] which is not feasible since x = 6.93747e-310 < 1 (I am using Gurobi 6.51).

However, it seems that in Gurobi getsolution gives a feasible solution even for unbounded problem since for the following problem

Max x
s.t. x >= 1
x unbounded
y <= -1
loadproblem!(m, [1. 0.], [-Inf, -Inf], [Inf, -1], [1., 0.], [1], [Inf], :Max)

optimize! returns :Unbounded and then getsolution returns a feasible solution.

See JuliaOpt/MathProgBase.jl#144

[joehuchette]

This is likely a bug with Gurobi that should be reported upstream

[mlubin]

I would check on the Gurobi documentation to see if this is expected behavior or not.

[blegat]

Gurobi replied:

The solution status "unbounded" only means that there exists an unbounded ray
for the primal problem. This does not necessarily mean that there is a feasible
solution for the primal problem. It could be that there does not even exist a
feasible solution, or it could be that Gurobi proved the existence of the
unbounded ray before it found a feasible solution.

Thus, in order to get a feasible solution (or the answer that the problem is
also infeasible, which means that there exists an unbounded ray for the dual
problem) you need to manually restrict the problem, for example by installing
large finite bounds for all variables.

In theory, you can calculate, given the rational input data, a value M that is
big enough so that there either exists a solution that is within [-M,M] for all
variables or the problem is infeasible. In practice, using a "reasonably large"
bounding box value M should suffice.

In the status code doc, they now say (I am not sure this note was there before, maybe they added it recently)

Model was proven to be unbounded. Important note: an unbounded status indicates the presence of an unbounded ray that allows the objective to improve without limit. It says nothing about whether the model has a feasible solution. If you require information on feasibility, you should set the objective to zero and reoptimize.

What is the definition of MathProgBase for :Unbounded ? I have always thought it was that we could find a solution with objective value abritrarily "good" and if it is the case, it is not the same as the Gurobi status.

[mlubin]

MathProgBase will certainly not be making any guarantees that the solvers are unable to satisfy. If the definitions are inconsistent then we should update the MPB definition.

[blegat]

I have been thinking about a new MPB status system (Following the discussion on MOSEK/Mosek.jl#101).

• status(m): why the solver stopped: Success, UserLimit, ...
• isprimalfeasible(m):
  • true if it is sure that the primal is feasible,
  • false if it is sure it is infeasible,
  • throws an error otherwise,

it may do additional computation to determine this, e.g. if Gurobi says Unbounded, we would set the objective to 0 et reoptimize to determine whether it is feasible, what to do is solver dependent.

• getsolution(m; feasible=true, optimal=true) would return a solution:

	feasible=true	feasible=false
optimal=true	optimal and feasible	???
optimal=false	feasible	anything

The solver should be lazy so in our case of Gurobi/Unbounded, if we ask getsolution(m, feasible=false, optimal=false) then it returns whatever it has but if we ask getsolution(m, feasible=true, optimal=false) then it sets the objective to zero and do a resolve to find a feasible solution and if we ask getsolution(m, feasible=true, optimal=true) it would throw an error.

I am still a little bit unsure about getsolution, we may also do getsolution(m, status::AbstractSolutionStatus) where status is the status we require (e.g. AnySolutionStatus, FeasibleSolutionStatus, OptimalSolutionStatus(eps=1e-6)). and getsolution way also return a pair solution::Vector, status::AbstractSolutionStatus.

What do you think ? I agree that this asks more to each solver but this kind of thing cannot be put somewhere else than in the solver package since these are solver specific.

[mlubin]

I'm not in favor of imposing a requirement in MPB that requires most LP solvers to do extra work in the unbounded case. That could be something that sits on top of MPB, perhaps.
We definitely need to redo MPB statuses though, should be discussed in an issue on the MPB repository.