10
$\begingroup$

As the question says, I am wondering what happens "behind the scene" when the Dual Infeasibility column of the Gurobi runtime log oscillates wildly, before Gurobi eventually quits with infeasibility. I am solving a mixed-integer model. More specifically, all integer variables are binary. An example plot of Dual Inf is below (value of Dual Inf. versus clock time). I am hoping this could point to some problems in my model formulation.

Value of dual infeasibility versus solver clock time

$\endgroup$
  • $\begingroup$ You are looking at the root node relaxation of your MIP, so the all integer or binary variables are treated as continuous variables. If this relaxation is already infeasible, the corresponding MIP needs not to be processed. So you are looking here at a pure linear programming problem. $\endgroup$ – mattmilten Nov 15 '19 at 11:52
1
$\begingroup$

According to Gurobi's documentation: "When the primal infeasibility, dual infeasibility, and complementarity satisfy barrier convergence tolerances (controlled using the BarConvTol parameter), the solution is declared optimal and optimization is complete.

Unlike the simplex and MIP optimizers, the barrier optimizer produces a logline for each iterate, independent of the value of the DisplayInterval parameter. You may sometimes see a star after the iteration count in the barrier progress log:

  15   2.42800468e+03  8.54543324e+04  1.68e+02 1.02e-09  8.30e+04     0s
  16   4.05292006e+03  4.65997441e+04  1.82e+02 2.50e-01  4.25e+04     0s
  17*  4.88742259e+08  4.30781025e+10  5.17e+00 1.31e-01  2.52e-02     0s
  18*  1.21709951e+06  3.39471138e+13  8.55e-06 3.14e-06  3.14e-05     0s
  19* -1.38021972e+06  3.31580578e+16  3.42e-08 8.20e-09  3.22e-08     0s
  20*  1.25182178e+06  3.31575855e+19  6.54e-12 7.34e-09  3.22e-11     0s

This indicates that the model may be primal or dual infeasible. Note that these intermediate indications of infeasibility won't necessarily turn into an infeasibility proof, so the star may disappear in later iterations."

I think the oscillation that was shown in the plot is related to one of those points with the star in the log file.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.