# 11 Analyzing Infeasible Problems¶

When developing and implementing a new optimization model, the first attempts will often be either infeasible, due to specification of inconsistent constraints, or unbounded, if important constraints have been left out.

In this section we will

- go over an example demonstrating how to locate infeasible constraints using the
**MOSEK**infeasibility report tool, - discuss in more general terms which properties may cause infeasibilities, and
- present the more formal theory of infeasible and unbounded problems.

## 11.1 Example: Primal Infeasibility¶

A problem is said to be *primal infeasible* if no solution exists that satisfies all the constraints of the problem.

As an example of a primal infeasible problem consider the problem of 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. 1.

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

exceeds the total supply

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:

Solving problem (1) using **MOSEK** will result in a solution, a solution status and a problem status. Among the log output from the execution of **MOSEK** on the above problem are the lines:

```
Basic solution
Problem status : PRIMAL_INFEASIBLE
Solution status : PRIMAL_INFEASIBLE_CER
```

The first line indicates that the problem status is primal infeasible. The second line says that a *certificate of the infeasibility* was found. The certificate is returned in place of the solution to the problem.

## 11.2 Locating the cause of Primal Infeasibility¶

Usually a primal infeasible problem status is caused by a mistake in formulating the problem and therefore the question arises: *What is the cause of the infeasible status?* When trying to answer this question, it is often advantageous to follow these steps:

- 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.
- Consider whether your problem has some 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.

If the problem is still primal infeasible, some of the constraints must be relaxed or removed completely. The **MOSEK** infeasibility report (Sec. 11.4 (The Infeasibility Report)) may assist you in finding the constraints causing the infeasibility.

Possible ways of relaxing your problem nclude:

- Increasing (decreasing) upper (lower) bounds on variables and constraints.
- Removing suspected constraints from the problem.

Returning to the transportation example, we discover that removing the fifth constraint

makes the problem feasible.

## 11.3 Locating the Cause of Dual Infeasibility¶

A problem may also be *dual infeasible*. In this case the primal problem is often unbounded, meaning that feasbile solutions exists such that the objective tends towards infinity. An example of a dual infeasible and primal unbounded problem is:

To resolve a dual infeasibility the primal problem must be made more restricted by

- Adding upper or lower bounds on variables or constraints.
- Removing variables.
- Changing the objective.

### 11.3.1 A cautionary note¶

The problem

is clearly infeasible. Moreover, if any one of the constraints is dropped, then the problem becomes feasible.

This illustrates the worst case scenario where all, or at least a significant portion of the constraints are involved in causing infeasibility. Hence, it may not always be easy or possible to pinpoint a few constraints responsible for infeasibility.

## 11.4 The Infeasibility Report¶

**MOSEK** includes functionality for diagnosing the cause of a primal or a dual infeasibility. It can be turned on by setting the `MSK_IPAR_INFEAS_REPORT_AUTO`

to `MSK_ON`

. This causes **MOSEK** to print a report on variables and constraints involved in the infeasibility.

The `MSK_IPAR_INFEAS_REPORT_LEVEL`

parameter controls the amount of information presented in the infeasibility report. The default value is \(1\).

### 11.4.1 Example: Primal Infeasibility¶

We will keep working with the problem (1) written in LP format:

```
\
\ An example of an infeasible linear problem.
\
minimize
obj: + 1 x11 + 2 x12
+ 5 x23 + 2 x24
+ 1 x31 + 2 x33 + 1 x34
st
s0: + x11 + x12 <= 200
s1: + x23 + x24 <= 1000
s2: + x31 + x33 + x34 <= 1000
d1: + x11 + x31 = 1100
d2: + x12 = 200
d3: + x23 + x33 = 500
d4: + x24 + x34 = 500
bounds
end
```

Using the command line (please remeber it accepts options following the C API format)

```
mosek -d MSK_IPAR_INFEAS_REPORT_AUTO MSK_ON infeas.lp
```

**MOSEK** produces the following infeasibility report:

```
MOSEK 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 2.000000e+002 0.000000e+000 1.000000e+000
2 s2 NONE 1.000000e+003 0.000000e+000 1.000000e+000
3 d1 1.100000e+003 1.100000e+003 1.000000e+000 0.000000e+000
4 d2 2.000000e+002 2.000000e+002 1.000000e+000 0.000000e+000
The following bound constraints are involved in the infeasibility.
Index Name Lower bound Upper bound Dual lower Dual upper
8 x33 0.000000e+000 NONE 1.000000e+000 0.000000e+000
10 x34 0.000000e+000 NONE 1.000000e+000 0.000000e+000
```

The infeasibility report is divided into two sections corresponding to constraints and variables. It is a selection of those lines from the problem solution (in this case the file `infeas.sol`

), which are important in understanding primal infeasibility. In this case the constraints `s0`

, `s2`

, `d1`

, `d2`

and variables `x33`

, `x34`

are of importance.

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. 7.1.2.1 (Primal Infeasible Problems)). Only the non-zero ones, which contribute to the optimization objective and thus are important for infeasibility, are shown.

It is also possible to obtain the infeasible subproblem. The command line

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

produces the files `rinfeas.bas.inf.lp`

. In this case the content of the file `rinfeas.bas.inf.lp`

is

```
minimize
obj: + 0 x11 + 0 x12 + 0 x13 + 0 x21 + 0 x22 + 0 x23
+ 0 x31 + 0 x32 + 0 x33 + 0 x24 + 0 x34
subject to
s0: + x11 + x12 <= 2e+02
s2: + x31 + x33 + x34 <= 1e+03
d1: + x11 + x31 = 1.1e+03
d2: + x12 = 2e+02
bounds
x11 free
x12 free
x13 free
x21 free
x22 free
x23 free
x31 free
x32 free
0 <= x33 <= +infinity
x24 free
0 <= x34 <= +infinity
end
```

which is an optimization problem. This problem is identical to (1), except that the objective and some of the constraints and bounds have been removed. Executing the command

```
mosek -d MSK_IPAR_INFEAS_REPORT_AUTO MSK_ON rinfeas.bas.inf.lp
```

demonstrates that the reduced problem is **primal infeasible**. Since the reduced problem is usually smaller than original problem, it should be easier to locate the cause of infeasibility in this rather than in the original (1).

### 11.4.2 Example: Dual Infeasibility¶

The following problem is dual to (1) and therefore it is dual infeasible.

```
maximize + 200 y1 + 1000 y2 + 1000 y3 + 1100 y4 + 200 y5 + 500 y6 + 500 y7
subject to
x11: y1+y4 < 1
x12: y1+y5 < 2
x23: y2+y6 < 5
x24: y2+y7 < 2
x31: y3+y4 < 1
x33: y3+y6 < 2
x34: y3+y7 < 1
bounds
-inf <= y1 < 0
-inf <= y2 < 0
-inf <= y3 < 0
y4 free
y5 free
y6 free
y7 free
end
```

This can be verified by proving that

is a certificate of dual infeasibility (see Sec. 7.1.2.2 (Dual Infeasible Problems)) as we can see from this report:

```
MOSEK DUAL INFEASIBILITY REPORT.
Problem status: The problem is dual infeasible
The following constraints are involved in the infeasibility.
Index Name Activity Objective Lower bound Upper bound
5 x33 -1.000000e+00 NONE 2.000000e+00
6 x34 -1.000000e+00 NONE 1.000000e+00
The following variables are involved in the infeasibility.
Index Name Activity Objective Lower bound Upper bound
0 y1 -1.000000e+00 2.000000e+02 NONE 0.000000e+00
2 y3 -1.000000e+00 1.000000e+03 NONE 0.000000e+00
3 y4 1.000000e+00 1.100000e+03 NONE NONE
4 y5 1.000000e+00 2.000000e+02 NONE NONE
Interior-point solution summary
Problem status : DUAL_INFEASIBLE
Solution status : DUAL_INFEASIBLE_CER
Primal. obj: 1.0000000000e+02 nrm: 1e+00 Viol. con: 0e+00 var: 0e+00
```

Let \(y^*\) denote the reported primal solution. **MOSEK** states

- that the problem is
*dual infeasible*, - that the reported solution is a certificate of dual infeasibility, and
- that the infeasibility measure for \(y^*\) is approximately zero.

Since the original objective was maximization, we have that \(c^T y^* >0\). See Sec. 7.1.2 (Infeasibility for Linear Optimization) for how to interpret the parameter values in the infeasibility report for a linear program. We see that the variables `y1`

, `y3`

, `y4`

, `y5`

and the constraints `x33`

and `x34`

contribute to infeasibility with non-zero values in the `Activity`

column.

One possible strategy to *fix* the infeasibility is to modify the problem so that the certificate of infeasibility becomes invalid. In this case we could do one the following things:

- Add a lower bound on
`y3`

. This will directly invalidate the certificate of dual infeasibility. - Increase the object coefficient of
`y3`

. Changing the coefficients sufficiently will invalidate the inequality \(c^Ty^*>0\) and thus the certificate. - Add lower bounds on
`x11`

or`x31`

. This will directly invalidate the certificate of infeasibility.

Please note that modifying the problem to invalidate the reported certificate does *not* imply that the problem becomes dual 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.

## 11.5 Theory Concerning Infeasible Problems¶

This section discusses the theory of infeasibility certificates and how **MOSEK** uses a certificate to produce an infeasibility report. In general, **MOSEK** solves the problem

where the corresponding dual problem is

We use the convension that for any bound that is not finite, the corresponding dual variable is fixed at zero (and thus will have no influence on the dual problem). For example

## 11.6 The Certificate of Primal Infeasibility¶

A certificate of primal infeasibility is *any* solution to the homogenized dual problem

with a positive objective value. That is, \((s_l^{c*},s_u^{c*},s_l^{x*},s_u^{x*})\) is a certificate of primal infeasibility if

and

The well-known *Farkas Lemma* tells us that (2) is infeasible if and only if a certificate of primal infeasibility exists.

Let \((s_l^{c*},s_u^{c*},s_l^{x*},s_u^{x*})\) be a certificate of primal infeasibility then

implies that the lower (upper) bound on the \(i\) th constraint is important for the infeasibility. Furthermore,

implies that the lower (upper) bound on the \(j\) th variable is important for the infeasibility.

## 11.7 The certificate of dual infeasibility¶

A certificate of dual infeasibility is *any* solution to the problem

with negative objective value, where we use the definitions

and

Stated differently, a certificate of dual infeasibility is any \(x^*\) such that

The well-known Farkas Lemma tells us that (3) is infeasible if and only if a certificate of dual infeasibility exists.

Note that if \(x^*\) is a certificate of dual infeasibility then for any \(j\) such that

variable \(j\) is involved in the dual infeasibility.

Given the assumption that all weights are 1 then the command

```
mosek -primalrepair -d MSK_IPAR_LOG_FEAS_REPAIR 3 feasrepair.lp
```

will form the repaired problem and solve it. The parameter `MSK_IPAR_LOG_FEAS_REPAIR`

controls the amount of log output from the repair. A value of 2 causes the optimal repair to printed out.

The output from running the above command is:

```
Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com
Open file 'feasrepair.lp'
Read summary
Type : LO (linear optimization problem)
Objective sense : min
Constraints : 4
Scalar variables : 2
Matrix variables : 0
Time : 0.0
Computer
Platform : Windows/64-X86
Cores : 4
Problem
Name :
Objective sense : min
Type : LO (linear optimization problem)
Constraints : 4
Cones : 0
Scalar variables : 2
Matrix variables : 0
Integer variables : 0
Primal feasibility repair started.
Optimizer started.
Interior-point optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Total number of eliminations : 2
Eliminator terminated.
Eliminator - tries : 1 time : 0.00
Eliminator - elim's : 2
Lin. dep. - tries : 1 time : 0.00
Lin. dep. - number : 0
Presolve terminated. Time: 0.00
Optimizer - threads : 1
Optimizer - solved problem : the primal
Optimizer - Constraints : 2
Optimizer - Cones : 0
Optimizer - Scalar variables : 6 conic : 0
Optimizer - Semi-definite variables: 0 scalarized : 0
Factor - setup time : 0.00 dense det. time : 0.00
Factor - ML order time : 0.00 GP order time : 0.00
Factor - nonzeros before factor : 3 after factor : 3
Factor - dense dim. : 0 flops : 5.40e+001
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 2.7e+001 1.0e+000 4.8e+000 1.00e+000 4.195228609e+000 0.000000000e+000 1.0e+000 0.00
1 2.4e+001 8.6e-001 1.5e+000 0.00e+000 1.227497414e+001 1.504971820e+001 2.6e+000 0.00
2 2.6e+000 9.7e-002 1.7e-001 -6.19e-001 4.363064729e+001 4.648523094e+001 3.0e-001 0.00
3 4.7e-001 1.7e-002 3.1e-002 1.24e+000 4.256803136e+001 4.298540657e+001 5.2e-002 0.00
4 8.7e-004 3.2e-005 5.7e-005 1.08e+000 4.249989892e+001 4.250078747e+001 9.7e-005 0.00
5 8.7e-008 3.2e-009 5.7e-009 1.00e+000 4.249999999e+001 4.250000008e+001 9.7e-009 0.00
6 8.7e-012 3.2e-013 5.7e-013 1.00e+000 4.250000000e+001 4.250000000e+001 9.7e-013 0.00
Basis identification started.
Primal basis identification phase started.
ITER TIME
0 0.00
Primal basis identification phase terminated. Time: 0.00
Dual basis identification phase started.
ITER TIME
0 0.00
Dual basis identification phase terminated. Time: 0.00
Basis identification terminated. Time: 0.00
Interior-point optimizer terminated. Time: 0.00.
Optimizer terminated. Time: 0.03
Basic solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: 4.2500000000e+001 Viol. con: 1e-013 var: 0e+000
Dual. obj: 4.2500000000e+001 Viol. con: 0e+000 var: 5e-013
Optimal objective value of the penalty problem: 4.250000000000e+001
Repairing bounds.
Increasing the upper bound -2.25e+001 on constraint 'c4' (3) with 1.35e+002.
Decreasing the lower bound 6.50e+002 on variable 'x2' (4) with 2.00e+001.
Primal feasibility repair terminated.
Optimizer started.
Interior-point optimizer started.
Presolve started.
Presolve terminated. Time: 0.00
Interior-point optimizer terminated. Time: 0.00.
Optimizer terminated. Time: 0.00
Interior-point solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: -5.6700000000e+003 Viol. con: 0e+000 var: 0e+000
Dual. obj: -5.6700000000e+003 Viol. con: 0e+000 var: 0e+000
Basic solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: -5.6700000000e+003 Viol. con: 0e+000 var: 0e+000
Dual. obj: -5.6700000000e+003 Viol. con: 0e+000 var: 0e+000
Optimizer summary
Optimizer - time: 0.00
Interior-point - iterations : 0 time: 0.00
Basis identification - time: 0.00
Primal - iterations : 0 time: 0.00
Dual - iterations : 0 time: 0.00
Clean primal - iterations : 0 time: 0.00
Clean dual - iterations : 0 time: 0.00
Clean primal-dual - iterations : 0 time: 0.00
Simplex - time: 0.00
Primal simplex - iterations : 0 time: 0.00
Dual simplex - iterations : 0 time: 0.00
Primal-dual simplex - iterations : 0 time: 0.00
Mixed integer - relaxations: 0 time: 0.00
```

reports the optimal repair. In this case it is to increase the upper bound on constraint `c4`

by 1.35e2 and decrease the lower bound on variable `x2`

by 20.