Strange log: infeasible root relaxation, feasible MIP
Answered
Hello,
I am getting a strange log with the MIP I'm trying to solve. The MIP is feasible, as proved by the optimal solution displayed below. However, the log says "infeasible" for the root relaxation. I know the optimal solution of the LP relaxation is 3.44, which is what I obtain when force all variables to be continuous. Why is the log showing "infeasible"?
Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (mac64)
Thread count: 2 physical cores, 4 logical processors, using up to 4 threads
Optimize a model with 339 rows, 196 columns and 897 nonzeros
Model fingerprint: 0x643cefbc
Variable types: 1 continuous, 195 integer (195 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 7e+00]
RHS range [1e+00, 2e+00]
Presolve removed 129 rows and 63 columns
Presolve time: 0.01s
Presolved: 210 rows, 133 columns, 786 nonzeros
Variable types: 0 continuous, 133 integer (132 binary)
Found heuristic solution: objective 6.0000000
Presolved: 210 rows, 133 columns, 786 nonzeros
Root relaxation: infeasible, 179 iterations, 0.01 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Tim
0 0 infeasible 0 6.00000 6.00000 0.00% - 0s
Explored 0 nodes (179 simplex iterations) in 0.02 seconds
Thread count was 4 (of 4 available processors)
Solution count 1: 6
Optimal solution found (tolerance 1.00e-04)
Best objective 6.000000000000e+00, best bound 6.000000000000e+00, gap 0.0000%
-
Official comment
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
Hi Paula,
This output can happen if the incumbent found before the root relaxation is solved can be used to tighten the formulation enough. An example would be
\[\begin{align}
\min\, &x\\
\text{s.t.} &x \geq 1.5\\
&x\in \mathbb{Z}
\end{align}\]
\(x=2\) is a feasible solution, which can easily be found without solving any relaxations. Since the objective is integral, we know that in order to improve, it has to be at most \(1\). We can use this information and set an upper bound of \(1\) on \(x\). This results in the root relaxation being infeasible because of the \(x\geq 1.5\) constraint and we know that the previously found solution is optimal.Since in your case, Gurobi removes the single continuous variable and your model is purely integer/binary, it is very likely that a similar argumentation is performed by Gurobi and your model is solved quickly.
Best regards,
Jaromił1 -
Thank you very much for your answer. I understand now. What an interesting example!
0
Post is closed for comments.
Comments
3 comments