Skip to main content

Strange log: infeasible root relaxation, feasible MIP

Answered

Comments

2 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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
  • Paula Fermin Cueto
    Gurobi-versary
    First Comment
    First Question

    Thank you very much for your answer. I understand now. What an interesting example!

    0

Please sign in to leave a comment.