Models at the edge of infeasibility

  • As we saw in the introduction, seemingly contradictory results regarding the feasibility or infeasibility of a model can legitimately occur for models that are at the boundary between feasibility and infeasibility.

  • A more complicated example is <span>$</span>x + 10^{8} y = -1, x<span>$</span>, <span>$</span>y >= 0<span>$</span>. It has two bases, one where <span>$</span>x<span>$</span> is basic and one where <span>$</span>y<span>$</span> is basic. If <span>$</span>x<span>$</span> is basic, we get <span>$</span>x = -1<span>$</span>, which is clearly infeasible. However, if <span>$</span>y<span>$</span> is basic we get <span>$</span>y = -10^{8}<span>$</span>, which is feasible within tolerance. Different algorithms could lead to either of such bases and thus come to apparently contradictory feasibility results.

  • Presolve reductions can also play a role. A presolve reduction, e.g. fixing a variable to a bound, implicitly forces a tolerance of 0 for that variable. When solving the reduced model, the optimizer therefore no longer has the option to "spread" a slight infeasibility of the model over these variables and produce a solution that is feasible within tolerances. This leads to seemingly contradictory feasibility results when solving the model with presolve enabled or disabled.

  • What can be done to diagnose such cases:
    • First step is to tighten the FeasibilityTol to <span>$</span>10^{-9}<span>$</span> and try again. In many cases this will lead to a consistent declaration of infeasibility of the model at hand, which tells you that the model is on this boundary of infeasibility.
    • Use feasRelax to solve your model (again with a tight FeasibilityTol. This boundary case is identified by a non-zero relaxation value.
    • Compute the IIS (again with a tight FeasibilityTol) to analyze the infeasibility.
  • Another source of seemlingly contradictory results is due to numerical issues of the model and will be discussed in the following subsections.

Try Gurobi for Free

Choose the evaluation license that fits you best, and start working with our Expert Team for technical guidance and support.

Evaluation License
Get a free, full-featured license of the Gurobi Optimizer to experience the performance, support, benchmarking and tuning services we provide as part of our product offering.
Academic License
Gurobi supports the teaching and use of optimization within academic institutions. We offer free, full-featured copies of Gurobi for use in class, and for research.
Cloud Trial

Request free trial hours, so you can see how quickly and easily a model can be solved on the cloud.