8.3 Debugging infeasibility

When solving an optimization problem one typically expects to get an optimal solution, but in some cases, either by design, or (most frequently) due to an error in the formulation, the problem may become infeasible (have no solution at all).

This section

• describes the intuitions behind infeasibility,

• helps to debug (unexpectedly) infeasible problems using the command line tool and by inspecting infeasibility reports and problem data by hand,

• gives some hints for how to modify the formulation to identify the reasons for infeasibility.

If, instead, you want to fetch an infeasibility certificate directly using Optimizer API for Python, see the tutorial in Sec. 6.13 (Retrieving infeasibility certificates).

An infeasibility certificate is only available for continuous problems, however the hints in Sec. 8.3.4 (Suggestions) apply to a large extent also to mixed-integer problems.

8.3.1 Numerical issues

Infeasible problem status may be just an artifact of numerical issues appearing when the problem is badly-scaled, barely feasible or otherwise ill-conditioned so that it is unstable under small perturbations of the data or round-off errors. This may be visible in the solution summary if the infeasibility certificate has poor quality. See Sec. 8.1.2 (Solution summary) for how to diagnose that and Sec. 8.2 (Addressing numerical issues) for possible hints. Sec. 8.2.3 (Typical pitfalls) contains examples of situations which may lead to infeasibility for numerical reasons.

We refer to Sec. 8.2 (Addressing numerical issues) for further information on dealing with those sort of issues. For the rest of this section we concentrate on the case when the solution summary leaves little doubt that the problem solved by the optimizer actually is infeasible.

8.3.2 Locating primal infeasibility

As an example of a primal infeasible problem consider minimizing the cost of transportation between a number of production plants and stores: Each plant produces a fixed number of goods, and each store has a fixed demand that must be met. Supply, demand and cost of transportation per unit are given in Fig. 8.1.

Fig. 8.1 Supply, demand and cost of transportation.

The problem represented in Fig. 8.1 is infeasible, since the total demand

\[2300 = 1100+200+500+500\]

exceeds the total supply

\[2200 = 200+1000+1000\]

If we denote the number of transported goods from plant \(i\) to store \(j\) by \(x_{ij}\), the problem can be formulated as the LP:

(8.1)\[\begin{split}\begin{array}{llccccccccccccccl} \mbox{minimize} & & x_{11} & + & 2x_{12} & + & 5x_{23} & + & 2x_{24} & + & x_{31} & + & 2x_{33} & + & x_{34} & & \\ \mbox{subject to}&s_0: & x_{11} & + & x_{12} & & & & & & & & & & & \leq & 200, \\ &s_1: & & & & & x_{23} & + & x_{24} & & & & & & & \leq & 1000,\\ &s_2: & & & & & & & & & x_{31} & + & x_{33} & + & x_{34} & \leq & 1000,\\ &d_0: & x_{11} & & & & & & & + & x_{31} & & & & & = & 1100,\\ &d_1: & & & x_{12} & & & & & & & & & & & = & 200, \\ &d_2: & & & & & x_{23} & + & & & & & x_{33} & & & = & 500, \\ &d_3: & & & & & & & x_{24} & + & & & & & x_{34} & = & 500, \\ & & & & & & & & & & & & & & x_{ij} & \geq & 0. \end{array}\end{split}\]

Solving problem (8.1) using MOSEK will result in an infeasibility status. The infeasibility certificate is contained in the dual variables an can be accessed from an API. The variables and constraints with nonzero solution values form an infeasible subproblem, which frequently is very small. See Sec. 12.1.2 (Infeasibility for Linear Optimization) or Sec. 12.2.2 (Infeasibility for Conic Optimization) for detailed specifications of infeasibility certificates.

A short infeasibility report can also be printed to the log stream. It can be turned on by setting the parameter iparam.infeas_report_auto to onoffkey.on. This causes MOSEK to print a report on variables and constraints which are involved in infeasibility in the above sense, i.e. have nonzero values in the certificate. The parameter iparam.infeas_report_level controls the amount of information presented in the infeasibility report. The default value is \(1\). For the above example the report is

Primal infeasibility report

Problem status: The problem is primal infeasible


The following constraints are involved in the primal infeasibility.


Index        Name     Lower bound      Upper bound      Dual lower       Dual upper
0            s0       none             200              0                1
2            s2       none             1000             0                1
3            d0       1100             1100             1                0
4            d1       200              200              1                0


The following bound constraints are involved in the primal infeasibility.


Index        Name     Lower bound      Upper bound      Dual lower       Dual upper
5            x33      0                none             1                0
6            x34      0                none             1                0

The infeasibility report is divided into two sections corresponding to constraints and variables. It is a selection of those lines from the problem solution which are important in understanding primal infeasibility. In this case the constraints s0, s2, d0, d1 and variables x33, x34 are of importance because of nonzero dual values. The columns Dual lower and Dual upper contain the values of dual variables \(s_l^c\), \(s_u^c\), \(s_l^x\) and \(s_u^x\) in the primal infeasibility certificate (see Sec. 12.1.2 (Infeasibility for Linear Optimization)).

In our example the certificate means that an appropriate linear combination of constraints s0, s1 with coefficient \(s_u^c=1\), constraints d0 and d1 with coefficient \(s_u^c-s_l^c=0-1=-1\) and lower bounds on x33 and x34 with coefficient \(-s_l^x=-1\) gives a contradiction. Indeed, the combination of the four involved constraints is \(x_{33}+x_{34}\leq -100\) (as indicated in the introduction, the difference between supply and demand).

It is also possible to extract the infeasible subproblem with the command-line tool. For an infeasible problem called infeas.lp the command:

mosek -d MSK_IPAR_INFEAS_REPORT_AUTO MSK_ON infeas.lp -info rinfeas.lp

will produce the file rinfeas.bas.inf.lp which contains the infeasible subproblem. Because of its size it may be easier to work with than the original problem file.

Returning to the transportation example, we discover that removing the fifth constraint \(x_{12} = 200\) makes the problem feasible. Almost all undesired infeasibilities should be fixable at the modeling stage.

8.3.3 Locating dual infeasibility

A problem may also be dual infeasible. In this case the primal problem is usually unbounded, meaning that feasible solutions exists such that the objective tends towards infinity. For example, consider the problem

\[\begin{split}\begin{array}{lr} \maximize & 200 y_1 + 1000 y_2 + 1000 y_3 + 1100 y_4 + 200 y_5 + 500 y_6 + 500 y_7\\ \st & y_1+y_4 \leq 1,\ y_1+y_5 \leq 2,\ y_2+y_6 \leq 5,\ y_2+y_7 \leq 2, \\ & y_3+y_4 \leq 1,\ y_3+y_6 \leq 2,\ y_3+y_7 \leq 1 \\ & y_1,y_2,y_3\leq 0 \end{array}\end{split}\]

which is dual to (8.1) (and therefore is dual infeasible). The dual infeasibility report may look as follows:

Dual infeasibility report

Problem status: The problem is dual infeasible


The following constraints are involved in the dual infeasibility.


Index        Name     Activity         Objective        Lower bound      Upper bound
5            x33      -1                                none             2
6            x34      -1                                none             1


The following variables are involved in the dual infeasibility.


Index        Name     Activity         Objective        Lower bound      Upper bound
0            y1       -1               200              none             0
2            y3       -1               1000             none             0
3            y4       1                1100             none             none
4            y5       1                200              none             none

In the report we see that the variables y1, y3, y4, y5 and two constraints contribute to infeasibility with non-zero values in the Activity column. Therefore

\[(y_1,\ldots,y_7)=(-1,0,-1,1,1,0,0)\]

is the dual infeasibility certificate as in Sec. 12.1.2 (Infeasibility for Linear Optimization). This just means, that along the ray

\[(0,0,0,0,0,0,0) + t(y_1,\ldots,y_7)=(-t,0,-t,t,t,0,0), \ t>0,\]

which belongs to the feasible set, the objective value \(100t\) can be arbitrarily large, i.e. the problem is unbounded.

In the example problem we could

• Add a lower bound on y3. This will directly invalidate the certificate of dual infeasibility.

• Increase the objective coefficient of y3. Changing the coefficients sufficiently will invalidate the inequality \(c^Ty^*>0\) and thus the certificate.

8.3.4 Suggestions

Primal infeasibility

When trying to understand what causes the unexpected primal infeasible status use the following hints:

• Remove the objective function. This does not change the infeasibility status but simplifies the problem, eliminating any possibility of issues related to the objective function.

• Remove cones, semidefinite variables and integer constraints. Solve only the linear part of the problem. Typical simple modeling errors will lead to infeasibility already at this stage.

• Consider whether your problem has some obvious necessary conditions for feasibility and examine if these are satisfied, e.g. total supply should be greater than or equal to total demand.

• Verify that coefficients and bounds are reasonably sized in your problem.

• See if there are any obvious contradictions, for instance a variable is bounded both in the variables and constraints section, and the bounds are contradictory.

• Consider replacing suspicious equality constraints by inequalities. For instance, instead of \(x_{12} = 200\) see what happens for \(x_{12}\geq 200\) or \(x_{12}\leq 200\).

• Relax bounds of the suspicious constraints or variables.

• For integer problems, remove integrality constraints on some/all variables and see if the problem solves.

• Remember that variables without explicitly initialized bounds are fixed at zero.

• Form an elastic model: allow to violate constraints at a cost. Introduce slack variables and add them to the objective as penalty. For instance, suppose we have a constraint

  \[\begin{split}\begin{array}{lr} \minimize & c^Tx, \\ \st & a^Tx\leq b. \end{array}\end{split}\]

  which might be causing infeasibility. Then create a new variable \(y\) and form the problem which contains:

  \[\begin{split}\begin{array}{lr} \minimize & c^Tx+y, \\ \st & a^Tx\leq b+y. \end{array}\end{split}\]

  Solving this problem will reveal by how much the constraint needs to be relaxed in order to become feasible. This is equivalent to inspecting the infeasibility certificate but may be more intuitive.

• If you think you have a feasible solution or its part, fix all or some of the variables to those values. Presolve will propagate them through the model and potentially reveal more localized sources of infeasibility.

• Dump the problem in PTF or LP format and verify that the problem that was passed to the optimizer corresponds to the problem expressed in the high-level modeling language, if any such was used.

Dual infeasibility

When trying to understand what causes the unexpected dual infeasible status use the following hints:

• Verify that the objective coefficients are reasonably sized.

• Check if no bounds and constraints are missing, for example if all variables that should be nonnegative have been declared as such etc.

• Strengthen bounds of the suspicious constraints or variables.

• Remember that constraints without explicitly initialized bounds are free (no bound).

• Form an series of models with decreasing bounds on the objective, that is, instead of objective

  \[\minimize\ c^Tx\]

  solve the problem with an additional constraint such as

  \[c^Tx = -10^5\]

  and inspect the solution to figure out the mechanism behind arbitrarily decreasing objective values. This is equivalent to inspecting the infeasibility certificate but may be more intuitive.

• Dump the problem in PTF or LP format and verify that the problem that was passed to the optimizer corresponds to the problem expressed in the high-level modeling language, if any such was used.

Please note that modifying the problem to invalidate the reported certificate does not imply that the problem becomes feasible — the reason for infeasibility may simply move, resulting a problem that is still infeasible, but for a different reason. More often, the reported certificate can be used to give a hint about errors or inconsistencies in the model that produced the problem.