Obtain feasible solution for Unbounded problem

[Benoît Legat]

When a problem is unbounded and InfUnbdInfo is set to 1, Gurobi provides an infeasibility ray that, as written in the doc (http://www.gurobi.com/documentation/6.5/refman/unbdray.html#attr:UnbdRay), "when added to any feasible solution, yields a new solution that is also feasible but improves the objective". How can I obtain a feasible solution ?

For instance, with the problem:

Max x

such that

x >= 1

y <= -1

the X attribute given by Gurobi v6.51 is [1, -1].

However, with the problem:

Min y

such that

x >= 1

the X attribute given by Gurobi v6.51 is [6.937e-310,0] which is not feasible.

[Michael Winkler]

I couldn't reproduce this behavior. When I try to optimize your second example the solution vector (independent of whether the InfUnbdInfo parameter is set to 1 or not) is always correct showing y=0 x=1. I also tried version 6.5.1.
Could you try to update your Gurobi installation to the current version 7.0.1?

Best,
Michael

[Benoît Legat]

Thanks for your answer. I will indeed try it on Gurobi 7. What I didn't say clearly in the earlier post is that x >= 1 should be set as a constraint and not as a variable bound to have the issue.

On Gurobi 6.51:

If it is set as a variable bound I get:

Optimize a model with 0 rows, 2 columns and 0 nonzeros

Coefficient statistics:

  Matrix range    [0e+00, 0e+00]

  Objective range [1e+00, 1e+00]

  Bounds range    [1e+00, 1e+00]

  RHS range       [0e+00, 0e+00]

Presolve removed 0 rows and 1 columns

Presolve time: 0.00s

Iteration    Objective       Primal Inf.    Dual Inf.      Time

       0      handle free variables                          0s

Solved in 0 iterations and 0.00 seconds

Unbounded model

X = [1.0,0.0]

If it is set as a constraint I get:

Optimize a model with 1 rows, 2 columns and 1 nonzeros

Coefficient statistics:

  Matrix range    [1e+00, 1e+00]

  Objective range [1e+00, 1e+00]

  Bounds range    [0e+00, 0e+00]

  RHS range       [1e+00, 1e+00]

Presolve removed 1 rows and 1 columns

Presolve time: 0.00s

Iteration    Objective       Primal Inf.    Dual Inf.      Time

       0      handle free variables                          0s

Solved in 1 iterations and 0.00 seconds

Unbounded model

X = [6.94934e-310,0.0]

Regars,

Benoît

[Benoît Legat]

I have just tried Gurobi 7.01, the results are exactly the same (except that X = [6.94629e-310,0.0] instead of X = [6.94934e-310,0.0]). I have attached a Julia code to reproduce it using the Julia wrapper (https://github.com/JuliaOpt/Gurobi.jl/)

[Benoît Legat]

Is it a bug in Gurobi or aren't we supposed to be able to retreive a feasible primal solution when the problem is unbounded ?

[Tobias Achterberg]

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.


Best regards,

Tobias