The problem analyzer prints a detailed survey of the model's
In the initial stages of model formulation the problem analyzer may be used as a quick way of verifying that the model has been built or imported correctly. In later stages it can help revealing special structures within the model that may be used to tune the optimizer's performance or to identify the causes of numerical difficulties.
The problem analyzer is run from the command line using the -anapro argument and produces something similar to the following (this is the problemanalyzer's survey of the aflow30a problem from the MIPLIB 2003 collection, see Appendix B for more examples):
Analyzing the problem
Constraints Bounds Variables
upper bd: 421 ranged : all cont: 421
fixed : 58 bin : 421
-------------------------------------------------------------------------------
Objective, min cx
range: min |c|: 0.00000 min |c|>0: 11.0000 max |c|: 500.000
distrib: |c| vars
0 421
[11, 100) 150
[100, 500] 271
-------------------------------------------------------------------------------
Constraint matrix A has
479 rows (constraints)
842 columns (variables)
2091 (0.518449%) nonzero entries (coefficients)
Row nonzeros, A_i
range: min A_i: 2 (0.23753%) max A_i: 34 (4.038%)
distrib: A_i rows rows% acc%
2 421 87.89 87.89
[8, 15] 20 4.18 92.07
[16, 31] 30 6.26 98.33
[32, 34] 8 1.67 100.00
Column nonzeros, A|j
range: min A|j: 2 (0.417537%) max A|j: 3 (0.626305%)
distrib: A|j cols cols% acc%
2 435 51.66 51.66
3 407 48.34 100.00
A nonzeros, A(ij)
range: min |A(ij)|: 1.00000 max |A(ij)|: 100.000
distrib: A(ij) coeffs
[1, 10) 1670
[10, 100] 421
-------------------------------------------------------------------------------
Constraint bounds, lb <= Ax <= ub
distrib: |b| lbs ubs
0 421
[1, 10] 58 58
Variable bounds, lb <= x <= ub
distrib: |b| lbs ubs
0 842
[1, 10) 421
[10, 100] 421
-------------------------------------------------------------------------------
The survey is divided into six different sections, each described below. To keep the presentation short with focus on key elements the analyzer generally attempts to display information on issues relevant for the current model only: E.g., if the model does not have any conic constraints (this is the case in the example above) or any integer variables, those parts of the analysis will not appear.
The first part of the survey consists of a brief summary of the model's linear and quadratic constraints (indexed by i) and variables (indexed by j). The summary is divided into three subsections:
Constraints
upper bd: The number of upper bounded constraints,
lower bd: The number of lower bounded constraints,
ranged : The number of ranged constraints,
fixed : The number of fixed constraints,
free : The number of free constraints
Bounds
upper bd: The number of upper bounded variables,
lower bd: The number of lower bounded variables,
ranged : The number of ranged variables,
fixed : The number of fixed variables,
free : The number of free variables
Variables
cont: The number of continuous variables,
bin : The number of binary variables,
int : The number of general integer variables,
Only constraints, bounds and domains actually in the model will be reported on, cf. appendix B; if all entities in a section turn out to be of the same kind, the number will be replaced by all for brevity.
The second part of the survey focuses on (the linear part of) the objective, summarizing the optimization sense and the coefficients' absolute value range and distribution. The number of 0 (zero) coefficients is singled out (if any such variables are in the problem).
The range is displayed using three terms:
min |c|: The minimum absolute value among all coeffecients
min |c|>0: The minimum absolute value among the nonzero coefficients
max |c|: The maximum absolute value among the coefficients
If some of these extrema turn out to be equal, the display is shortened accordingly:
The absolute value distribution is displayed as a table summarizing the numbers by orders of magnitude (with a ratio of 10). Again, the number of variables with a coefficient of 0 (if any) is singled out. Each line of the table is headed by an interval (half-open intervals including their lower bounds), and is followed by the number of variables with their objective coefficient in this interval. Intervals with no elements are skipped.
The third part of the survey displays information on the nonzero coefficients of the linear constraint matrix.
Following a brief summary of the matrix dimensions and the number of nonzero coefficients in total, three sections provide further details on how the nonzero coefficients are distributed by row-wise count (A_i), by column-wise count (A|j), and by absolute value (|A(ij)|). Each section is headed by a brief display of the distribution's range (min and max), and for the row/column-wise counts the corresponding densities are displayed too (in parentheses).
The distribution tables single out three particularly interesting counts: zero, one, and two nonzeros per row/column; the remaining row/column nonzeros are displayed by orders of magnitude (ratio 2). For each interval the relative and accumulated relative counts are also displayed.
Note that constraints may have both linear and quadratic terms, but the empty rows and columns reported in this part of the survey relate to the linear terms only. If empty rows and/or columns are found in the linear constraint matrix, the problem is analyzed further in order to determine if the corresponding constraints have any quadratic terms or the corresponding variables are used in conic or quadratic constraints; cf. the last two examples of appendix B.
The distribution of the absolute values, |A(ij)|, is displayed just as for the objective coefficients described above.
The fourth part of the survey displays distributions for the absolute values of the finite lower and upper bounds for both constraints and variables. The number of bounds at 0 is singled out and, otherwise, displayed by orders of magnitude (with a ratio of 10).
The fifth part of the survey displays distributions for the nonzero elements in the gradient of the quadratic constraints, i.e. the nonzero row counts for the column vectors Qx. The table is similar to the tables for the linear constraints' nonzero row and column counts described in the survey's third part.
Note: Quadratic constraints may also have a linear part, but that will be included in the linear constraints survey; this means that if a problem has one or more pure quadratic constraints, part three of the survey will report an equal number of linear constraint rows with 0 (zero) nonzeros, cf. the last example in appendix B. Likewise, variables that appear in quadratic terms only will be reported as empty columns (0 nonzeros) in the linear constraint report.
The last part of the survey summarizes the model's conic constraints. For each of the two types of cones, quadratic and rotated quadratic, the total number of cones are reported, and the distribution of the cones' dimensions are displayed using intervals. Cone dimensions of 2, 3, and 4 are singled out.
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 chapter we will
Furthermore, chapter 11 contains a discussion on a specific method for repairing infeasibility problems where infeasibilities are caused by model parameters rather than errors in the model or the implementation.
A problem is said to be primal infeasible if no solution exists that satisfy 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 figure 10.1.
The problem represented in figure 10.1 is infeasible, since the total demand
![]() |
(10.2.1) |
exceeds the total supply
![]() |
(10.2.2) |
If we denote the number of transported goods from plant i to store j by , the problem can be formulated as the LP:
![]() |
(10.2.3) |
Solving the problem (10.2.3) 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.
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:
If the problem is still primal infeasible, some of the constraints must be relaxed or removed completely. The MOSEK infeasibility report (Section 10.2.4) may assist you in finding the constraints causing the infeasibility.
Possible ways of relaxing your problem include:
Returning to the transportation example, we discover that removing the fifth constraint
![]() |
(10.2.4) |
makes the problem feasible.
A problem may also be dual infeasible. In this case the primal problem is often unbounded, mening that feasbile solutions exists such that the objective tends towards infinity. An example of a dual infeasible and primal unbounded problem is:
![]() |
(10.2.5) |
To resolve a dual infeasibility the primal problem must be made more restricted by
The problem
![]() |
(10.2.6) |
is clearly infeasible. Moreover, if any one of the constraints are dropped, then the problem becomes feasible.
This illustrates the worst case scenario that all, or at least a significant portion, of the constraints are involved in the infeasibility. Hence, it may not always be easy or possible to pinpoint a few constraints which are causing the infeasibility.
MOSEK includes functionality for diagnosing the cause of a primal or a dual infeasibility. It can be turned on by setting the mosek.iparam.infeas_report_auto to mosek.onoffkey.on. This causes MOSEK to print a report on variables and constraints involved in the infeasibility.
The mosek.iparam.infeas_report_level parameter controls the amount of information presented in the infeasibility report. The default value is 1.
We will reuse the example (10.2.3) located in infeas.lp:
\ \ An example of an infeasible linear problem. \ minimize obj: + 1 x11 + 2 x12 + 1 x13 + 4 x21 + 2 x22 + 5 x23 + 4 x31 + 1 x32 + 2 x33 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
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 where the first section shows which constraints that are important for the infeasibility. In this case the important constraints are the ones named s0, s2, d1, and d2. The values in the columns “Dual lower” and “Dual upper” are also useful, since a non-zero dual lower value for a constraint implies that the lower bound on the constraint is important for the infeasibility. Similarly, a non-zero dual upper value implies that the upper bound on the constraint is important for the infeasibility.
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: + CFIXVAR st s0: + x11 + x12 <= 200 s2: + x31 + x33 + x34 <= 1e+003 d1: + x11 + x31 = 1.1e+003 d2: + x12 = 200 bounds x11 free x12 free x13 free x21 free x22 free x23 free x31 free x32 free x24 free CFIXVAR = 0e+000 end
which is an optimization problem. This problem is identical to (10.2.3), 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 the infeasibility in this rather than in the original (10.2.3).
The example problem
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 x44: y3+y7 < 1 bounds y1 < 0 y2 < 0 y3 < 0 y4 free y5 free y6 free y7 free end
is dual infeasible. This can be verified by proving that
y1=-1, y2=-1, y3=0, y4=1, y5=1
is a certificate of dual infeasibility. In this example the following infeasibility report is produced (slightly edited):
The following constraints are involved in the infeasibility.
Index Name Activity Objective Lower bound Upper bound
0 x11 -1.000000e+00 NONE 1.000000e+00
4 x31 -1.000000e+00 NONE 1.000000e+00
The following variables are involved in the infeasibility.
Index Name Activity Objective Lower bound Upper bound
3 y4 -1.000000e+00 -1.100000e+03 NONE NONE
Interior-point solution
Problem status : DUAL_INFEASIBLE
Solution status : DUAL_INFEASIBLE_CER
Primal - objective: 1.1000000000e+03 eq. infeas.: 0.00e+00 max bound infeas.: 0.00e+00 cone infeas.: 0.00e+00
Dual - objective: 0.0000000000e+00 eq. infeas.: 0.00e+00 max bound infeas.: 0.00e+00 cone infeas.: 0.00e+00
Let denote the reported primal solution. MOSEK states
Since it was an maximization problem, this implies that
![]() |
(10.2.7) |
For a minimization problem this inequality would have been reversed — see (10.2.19).
From the infeasibility report we see that the variable y4, and the constraints x11 and x33 are involved in the infeasibility since these appear 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 may do one the the following things:
Please note that modifying the problem to invalidate the reported certificate does not imply that the problem becomes dual feasible — the infeasibility may simply “move”, resulting in a new infeasibility.
More often, the reported certificate can be used to give a hint about errors or inconsistencies in the model that produced the problem.
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
![]() |
(10.2.8) |
where the corresponding dual problem is
![]() |
(10.2.9) |
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
![]() |
(10.2.10) |
A certificate of primal infeasibility is any solution to the homogenized dual problem
![]() |
(10.2.11) |
with a positive objective value. That is, is a certificate of primal infeasibility if
![]() |
(10.2.12) |
and
![]() |
(10.2.13) |
The well-known Farkas Lemma tells us that (10.2.8) is infeasible if and only if a certificate of primal infeasibility exists.
Let be a certificate of primal infeasibility then
![]() |
(10.2.14) |
implies that the lower (upper) bound on the ith constraint is important for the infeasibility. Furthermore,
![]() |
(10.2.15) |
implies that the lower (upper) bound on the jth variable is important for the infeasibility.
A certificate of dual infeasibility is any solution to the problem
![]() |
(10.2.16) |
with negative objective value, where we use the definitions
![]() |
(10.2.17) |
and
![]() |
(10.2.18) |
Stated differently, a certificate of dual infeasibility is any such that
![]() |
(10.2.19) |
The well-known Farkas Lemma tells us that (10.2.9) is infeasible if and only if a certificate of dual infeasibility exists.
Note that if is a certificate of dual infeasibility then for any j such that
![]() |
(10.2.20) |
variable j is involved in the dual infeasibility.