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 feasibilty 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 infeasibiltiy.
    • 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.