Irreducible Infeasible Subsets

When an optimization problem is infeasible it is common to ask for the reason for infeasibility. It is very typical that the model is infeasible because it contains a set of mutually contradicting constraints which is relatively small compared to the total size of the problem. Locating and analyzing such a subset is usually helpful in understanding the reasons for infeasibility.

Such considerations have led the OR community to come up with the notion of Irreducible Infeasible Set (IIS) - a subset of constraints which is infeasible but cannot be reduced to a smaller infeasible set (all its proper subsets are already feasible). Every infeasible problem has an IIS - possibly many, possibly of different sizes. For example the problem bgdbg1 (see below) has a few hundred bounds but its infeasibility is caused already by the small segment

X104_JY >= 0.0
X104_JH >= 36.0
X104_JY + X104_JH <= 6.0

consisting of 3 bounds, which is an IIS. In fact the same model has also another IIS

X199_CM1 >= 96.0
X199_CM1 <= 86.0

with just 2 bounds (it doesn't get any better - a single linear bound is always feasible on its own).

An IIS can be found by a simple iterative algorithm which tries to remove one bound at a time and checks if the problem remains infeasible. We have implemented it for linear and mixed-integer linear problems in a recently published python notebook, where you can also read more details of the algorithm and its implementation. You can also download the python code directly. 

Below are the results produced by our sample code on the infeasible problems from NETLIB. We report the number of bounds in the problem, the size of the (Farkas) infeasibility certificate (these are the bounds that will appear in the infeasibility report or in the task.getinfeasiblesubproblem() function) and finally the size of the smallest IIS out of 5 runs of the algorithm (the IIS found depends on an ordering of the bounds, which we randomize).

bgdbg1.gz: OK, all bounds = 926, Farkas size = 2, IIS size = 2
bgetam.gz: OK, all bounds = 1577, Farkas size = 31, IIS size = 25
bgindy.gz: OK, all bounds = 14694, Farkas size = 196, IIS size = 154
bgprtr.gz: OK, all bounds = 68, Farkas size = 12, IIS size = 10
box1.gz: OK, all bounds = 723, Farkas size = 10, IIS size = 9
ceria3d.gz: OK, all bounds = 3576, Farkas size = 117, IIS size = 198
chemcom.gz: OK, all bounds = 1416, Farkas size = 86, IIS size = 37
cplex2.gz: numerical issues, all bounds = 733, Farkas size = 177, IIS size = 715
ex72a.gz: OK, all bounds = 609, Farkas size = 61, IIS size = 60
ex73a.gz: OK, all bounds = 597, Farkas size = 28, IIS size = 25
forest6.gz: OK, all bounds = 196, Farkas size = 96, IIS size = 92
galenet.gz: OK, all bounds = 26, Farkas size = 5, IIS size = 5
gosh.gz: OK, all bounds = 15353, Farkas size = 9, IIS size = 9
gran.gz: OK, all bounds = 8386, Farkas size = 2, IIS size = 2
grbeai.gz: OK, all bounds = 10402, Farkas size = 93, IIS size = 54
itest2.gz: OK, all bounds = 13, Farkas size = 3, IIS size = 3
itest6.gz: OK, all bounds = 21, Farkas size = 3, IIS size = 3
klein1.gz: OK, all bounds = 108, Farkas size = 55, IIS size = 54
klein2.gz: OK, all bounds = 531, Farkas size = 57, IIS size = 55
klein3.gz: numerical issues, all bounds = 1082, Farkas size = 97, IIS size = 192
mondou2.gz: OK, all bounds = 1832, Farkas size = 24, IIS size = 23
pang.gz: OK, all bounds = 942, Farkas size = 34, IIS size = 32
pilot4i.gz: OK, all bounds = 1886, Farkas size = 43, IIS size = 47
qual.gz: OK, all bounds = 1360, Farkas size = 217, IIS size = 370
reactor.gz: OK, all bounds = 1652, Farkas size = 15, IIS size = 9
refinery.gz: OK, all bounds = 1360, Farkas size = 206, IIS size = 120
vol1.gz: OK, all bounds = 1360, Farkas size = 275, IIS size = 196
woodinfe.gz: OK, all bounds = 173, Farkas size = 2, IIS size = 2

The work reported here and in the notebook was carried out by Adam Bosák during his student internship at MOSEK. Thanks!

Elementary intro to infeasibility certificates

We occasionally receive support questions asking about the meaning and practical use of infeasibility certificates, usually when the user expected the problem to be feasible. While an infeasibility certificate is a well-defined mathematical object based on Farkas' lemma, it is not intuitive for everyone how to use it to address the basic question of "What is wrong with my problem formulation?". We will try to explain this on a very simple example.

In this post we don't even consider optimization, but restrict to elementary linear algebra. Suppose we want to find a solution to a system of linear equations:

$$
\begin{array}{llllllllllll}
& 2x_1 & - & x_2 & + & x_3 & - & 3x_4 & + & x_5 & = & 1, \\
& & & x_2 & -& 2x_3 & & & +& x_5 & = & -1,\\
& 3x_1 &  & & - & x_3 & - & x_4 & & & = & 2, \\
& 2x_1 & + & x_2 & - & 3x_3 & - & 3x_4 & + & 3x_5 & = & -0.5.
\end{array}
$$

This system of linear equations is in fact infeasible (has no solution). One way to see it is to multiply the equations by coefficients given on the right-hand side and add them up:

$$
\begin{array}{lllllllllllll}
& 2x_1 & - & x_2 & + & x_3 & - & 3x_4 & + & x_5 & = & 1 & / \cdot (-1) \\
& & & x_2 & -& 2x_3 & & & +& x_5 & = & -1 & / \cdot (-2) \\
& 3x_1 &  & & - & x_3 & - & x_4 & & & = & 2 & / \cdot 0 \\
& 2x_1 & + & x_2 & - & 3x_3 & - & 3x_4 & + & 3x_5 & = & -0.5 & / \cdot 1 \\
\hline
&  &  &  &  &  &  &  &  & 0 & = & 0.5. &
\end{array}
$$

We get an obvious contradiction, which proves the system has no solution. The vector

$$ y = [-1, -2, 0, 1] $$

of weights used above is therefore a proof (certificate) of infeasibility. MOSEK produces such a certificate automatically. Here is a simple script in MATLAB that computes precisely that vector:


As output we get:


Here are a few comments:

• General theory guarantees that the dual variable y is a convenient place that can store the certificate.
• When a system of equations has no solution then an appropriate certificate is guaranteed to exist. This is a basic variant of Farkas' lemma, but it should be intuitively clear: your favorite method of solving linear systems (for instance Gaussian elimination) boils down to taking  successive linear combinations of equations, a process which ends up either with a solution or with an "obvious" contradiction of the form $0=1$.

Using the certificate to debug a model 

In the example above $y_3=0$ which means that the third equation does not matter: infeasibility is caused already by some combination of the 1st, 2nd and 4th equation. In many practical situations the infeasibility certificate $y$ will have very few nonzeros, and those nonzeros determine a subproblem (subset of equations) which alone cause infeasibility. The user can configure MOSEK to print an infeasibility report, which in our example will look like:

This report is nothing else than a listing of equations with nonzero entries in $y$, and $y$ is the difference between Dual lower and Dual upper. Analyzing this set (which hopefully is much smaller than the full problem) can help locate a possible modeling error which makes the problem infeasible.

To conclude, let us now phrase the above discussion in matrix notation. A linear equation system

$$ Ax=b $$

is infeasible if and only if there is a vector $y$ such that

$$ A^Ty = 0 \quad \mbox{and}\quad b^Ty \neq 0. $$

The situation is analogous for linear problems with inequality constraints. We will look at an example of that in another blog post.

What NOT to do when an optimization problem is infeasible!

Given your optimization problem is infeasible then what should do?

A common practice is to look at the infeasible solution returned by the optimizer e.g. MOSEK and then relax the bounds that are violated by the reported solution. This practice is rooted in the fact that in the good old days all linear optimization problems was optimized using the primal simplex algorithm employing a phase 1 and phase 2 approach as described in textbooks. The purpose of the phase 1 is to find a feasible solution and then in phase 2 to locate an optimal solution starting from the phase 1 solution. The implication is if no feasible solution exists, then the reported solution will be as close to as feasible solution as possible in a well defined sense. Therefore, it make sense to relax the problem based on the solution reported by the phase 1 because that leads to the smallest possible relaxation that make the problem feasible.

However, nowadays this does not work in most cases for the following reasons:

1. Most optimizers apply a presolve to the problem before optimizing. Now finding an optimal phase 1 solution to the presolved problem is almost never the same as finding an optimal phase 1 solution to the original problem  if the problem is infeasible. Therefore, if the presolve has been effective the reported solution is likely to be far from an optimal phase 1 solution to the original problem.
2. Moreover, if the problem is found to be infeasible during the presolve, then the phase 1 problem is not solved at all and hence the optimal solution to the phase 1 problem is not available.  
3. Interior-point based optimizers does not use a phase 1 and phase 2 approach, Therefore, the primal solution returned by an interior-point optimizer for infeasible problems is usually not very informative and definitely not close to an optimal solution to a phase 1 problem.
4. The dual simplex algorithm never solves the phase 1 problem. Rather in case of an infeasible problem it produce a Farkas certificate of the infeasibility.  

The main recomodation is if an optimization problem is diagnosed infeasible by an optimizer e.g. MOSEK, then do NOT use the primal solution for anything unless you are absolutely sure it is an optimal solution to a phase 1 problem. 

Then what should you do? Assuming the problem is a continuous linear or convex optimization problem then there is a so called Farkas certificate that proves the problem is infeasible. Some optimizes like MOSEK will report the Farkas certificate as the dual solution. Such a Farkas certificate can be used to repair the problem as discussed in the technical report.  

Alternatively a phase 1 problem can be formed explicitly and solved if you want to do the traditional repair procedure. By the way the optimal dual solution to the phase 1 problem will be a Farkas certificate of the infeasible status. Hence, the phase 1 problem can seen as computing a Farkas certificate if one is available.

New technical report about infeasible linear problems.

A new technical report about linear infeasible problems has been made available at the MOSEK website. The report is useful to  MOSEK users who wants to know more about the MOSEK infeasibility reports.