Strange log: infeasible root relaxation, feasible MIP
AnsweredHello,
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.00e04)
Best objective 6.000000000000e+00, best bound 6.000000000000e+00, gap 0.0000%

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
Please sign in to leave a comment.
Comments
2 comments