13. The analyzers


13.1. The problem analyzer

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 using the mosekopt('anapro') command and produces something similar to the following (this is the problemanalyzer's survey of the aflow30a problem from the MIPLIB 2003 collection, see Appendix G 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.

13.1.1. General characteristics

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, [[MathCmd 739]]

lower bd: The number of lower bounded constraints, [[MathCmd 740]]

ranged : The number of ranged constraints, [[MathCmd 741]]

fixed : The number of fixed constraints, [[MathCmd 742]]

free : The number of free constraints

Bounds

upper bd: The number of upper bounded variables, [[MathCmd 743]]

lower bd: The number of lower bounded variables, [[MathCmd 744]]

ranged : The number of ranged variables, [[MathCmd 745]]

fixed : The number of fixed variables, [[MathCmd 746]]

free : The number of free variables

Variables

cont: The number of continuous variables, [[MathCmd 747]]

bin : The number of binary variables, [[MathCmd 748]]

int : The number of general integer variables, [[MathCmd 749]]

Only constraints, bounds and domains actually in the model will be reported on, cf. appendix G; if all entities in a section turn out to be of the same kind, the number will be replaced by all for brevity.

13.1.2. Objective

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:

  • If min |c|is greater than zero, the min |c|>0 term is obsolete and will not be displayed
  • If only one or two different coefficients occur this will be displayed using all and an explicit listing of the coefficients

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.

13.1.3. Linear constraints

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 G.

The distribution of the absolute values, |A(ij)|, is displayed just as for the objective coefficients described above.

13.1.4. Constraint and variable bounds

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).

13.1.5. Quadratic constraints

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 G. Likewise, variables that appear in quadratic terms only will be reported as empty columns (0 nonzeros) in the linear constraint report.

13.1.6. Conic constraints

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.

13.2. 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 chapter we will

13.2.1. Example: Primal infeasibility

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 13.1.

Figure 13.1: Supply, demand and cost of transportation.

The problem represented in figure 13.1 is infeasible, since the total demand

\begin{math}\nonumber{}2300=1100+200+500+500\end{math} (13.2.1)

exceeds the total supply

\begin{math}\nonumber{}2200=200+1000+1000\end{math} (13.2.2)

If we denote the number of transported goods from plant i to store j by [[MathCmd 752]], the problem can be formulated as the LP:

\begin{math}\nonumber{}\begin{array}{lccccccccccccccl}\nonumber{}\mbox{minimize} & x_{{11}} & + & 2x_{{12}} & + & 5x_{{23}} & + & 2x_{{24}} & + & x_{{31}} & + & 2x_{{33}} & + & x_{{34}} &  & \\\nonumber{}\mbox{subject to} & x_{{11}} & + & x_{{12}} &  &  &  &  &  &  &  &  &  &  & \leq{} & 200,\\\nonumber{} &  &  &  &  & x_{{23}} & + & x_{{24}} &  &  &  &  &  &  & \leq{} & 1000,\\\nonumber{} &  &  &  &  &  &  &  &  & x_{{31}} & + & x_{{33}} & + & x_{{34}} & \leq{} & 1000,\\\nonumber{} & x_{{11}} &  &  &  &  &  &  & + & x_{{31}} &  &  &  &  & = & 1100,\\\nonumber{} &  &  & x_{{12}} &  &  &  &  &  &  &  &  &  &  & = & 200,\\\nonumber{} &  &  &  &  & x_{{23}} & + &  &  &  &  & x_{{33}} &  &  & = & 500,\\\nonumber{} &  &  &  &  &  &  & x_{{24}} & + &  &  &  &  & x_{{34}} & = & 500,\\\nonumber{} & x_{{ij}}\geq{}0. &  &  &  &  &  &  &  &  &  &  &  &  &  &\end{array}\end{math} (13.2.3)

Solving the problem (13.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.

13.2.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 infeasible status but simplifies the problem, eliminating any possibility of problems 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 (Section 13.2.4) may assist you in finding the constraints causing the infeasibility.

Possible ways of relaxing your problem include:

  • 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

\begin{math}\nonumber{}x_{{12}}=200\end{math} (13.2.4)

makes the problem feasible.

13.2.3. Locating the cause of dual infeasibility

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:

\begin{math}\nonumber{}\begin{array}{lcl}\nonumber{}\mbox{minimize} & x_{1} & \\\nonumber{}\mbox{subject to} & x_{1}\leq{}5. &\end{array}\end{math} (13.2.5)

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.

13.2.3.1. A cautious note

The problem

\begin{math}\nonumber{}\begin{array}{lcl}\nonumber{}\mbox{minimize} & 0 & \\\nonumber{}\mbox{subject to} & 0\leq{}x_{1}, & \\\nonumber{} & x_{j}\leq{}x_{{j+1}}, & j=1,\dots ,n-1,\\\nonumber{} & x_{n}\leq{}-1 &\end{array}\end{math} (13.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.

13.2.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.

13.2.4.1. Example: Primal infeasibility

We will reuse the example (13.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 (13.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 (13.2.3).

13.2.4.2. Example: Dual infeasibility

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 [[MathCmd 657]] 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 [[MathCmd 657]] is approximately zero.

Since it was an maximization problem, this implies that

\begin{math}\nonumber{}c^{t}x^{*}>0.\end{math} (13.2.7)

For a minimization problem this inequality would have been reversed — see (13.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:

  • Put a lower bound in y3. This will directly invalidate the certificate of dual infeasibility.
  • Increase the object coefficient of y3. Changing the coefficients sufficiently will invalidate the inequality (13.2.7) and thus the certificate.
  • Put 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 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.

13.2.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

\begin{math}\nonumber{}\begin{array}{lccccl}\nonumber{}\mbox{minimize} &  &  & c^{T}x+c^{f} &  & \\\nonumber{}\mbox{subject to} & l^{c} & \leq{} & Ax & \leq{} & u^{c},\\\nonumber{} & l^{x} & \leq{} & x & \leq{} & u^{x}\end{array}\end{math} (13.2.8)

where the corresponding dual problem is

\begin{math}\nonumber{}\begin{array}{lccl}\nonumber{}\mbox{maximize} & (l^{c})^{T}s_{l}^{c}-(u^{c})^{T}s_{u}^{c} &  & \\\nonumber{} & +(l^{x})^{T}s_{l}^{x}-(u^{x})^{T}s_{u}^{x}+c^{f} &  & \\\nonumber{}\mbox{subject to} & A^{T}y+s_{l}^{x}-s_{u}^{x} & = & c,\\\nonumber{} & -y+s_{l}^{c}-s_{u}^{c} & = & 0,\\\nonumber{} & s_{l}^{c},s_{u}^{c},s_{l}^{x},s_{u}^{x}\geq{}0. &  &\end{array}\end{math} (13.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

\begin{math}\nonumber{}l_{j}^{x}=-\infty ~\Rightarrow ~(s_{l}^{x})_{j}=0\end{math} (13.2.10)

13.2.6. The certificate of primal infeasibility

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

\begin{math}\nonumber{}\begin{array}{lccl}\nonumber{}\mbox{maximize} & (l^{c})^{T}s_{l}^{c}-(u^{c})^{T}s_{u}^{c} &  & \\\nonumber{} & +(l^{x})^{T}s_{l}^{x}-(u^{x})^{T}s_{u}^{x} &  & \\\nonumber{}\mbox{subject to} & A^{T}y+s_{l}^{x}-s_{u}^{x} & = & 0,\\\nonumber{} & -y+s_{l}^{c}-s_{u}^{c} & = & 0,\\\nonumber{} & s_{l}^{c},s_{u}^{c},s_{l}^{x},s_{u}^{x}\geq{}0. &  &\end{array}\end{math} (13.2.11)

with a positive objective value. That is, [[MathCmd 764]] is a certificate of primal infeasibility if

\begin{math}\nonumber{}(l^{c})^{T}s_{l}^{{c*}}-(u^{c})^{T}s_{u}^{{c*}}+(l^{x})^{T}s_{l}^{{x*}}-(u^{x})^{T}s_{u}^{{x*}}>0\end{math} (13.2.12)

and

\begin{math}\nonumber{}\begin{array}{lcl}\nonumber{}A^{T}y+s_{l}^{{x*}}-s_{u}^{{x*}} & = & 0,\\\nonumber{}-y+s_{l}^{{c*}}-s_{u}^{{c*}} & = & 0,\\\nonumber{}s_{l}^{{c*}},s_{u}^{{c*}},s_{l}^{{x*}},s_{u}^{{x*}}\geq{}0. &  &\end{array}\end{math} (13.2.13)

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

Let [[MathCmd 764]] be a certificate of primal infeasibility then

\begin{math}\nonumber{}(s_{l}^{{c*}})_{i}>0\quad{}((s_{u}^{{c*}})_{i}>0)\end{math} (13.2.14)

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

\begin{math}\nonumber{}(s_{l}^{{x*}})_{j}>0\quad{}((s_{u}^{{x*}})_{i}>0)\end{math} (13.2.15)

implies that the lower (upper) bound on the jth variable is important for the infeasibility.

13.2.7. The certificate of dual infeasibility

A certificate of dual infeasibility is any solution to the problem

\begin{math}\nonumber{}\begin{array}{lccccl}\nonumber{}\mbox{minimize} &  &  & c^{T}x &  & \\\nonumber{}\mbox{subject to} & \bar{l}^{c} & \leq{} & Ax & \leq{} & \bar{u}^{c},\\\nonumber{} & \bar{l}^{x} & \leq{} & x & \leq{} & \bar{u}^{x}\end{array}\end{math} (13.2.16)

with negative objective value, where we use the definitions

\begin{math}\nonumber{}\bar{l}_{i}^{c}:=\left\lbrace{}\begin{array}{ll}\nonumber{}0, & l_{i}^{c}>-\infty ,\\\nonumber{}-\infty , & \mbox{otherwise},\end{array}\right.\quad{}\bar{u}_{i}^{c}:=\left\lbrace{}\begin{array}{ll}\nonumber{}0, & u_{i}^{c}<\infty ,\\\nonumber{}\infty , & \mbox{otherwise},\end{array}\right.\end{math} (13.2.17)

and

\begin{math}\nonumber{}\bar{l}_{i}^{x}:=\left\lbrace{}\begin{array}{ll}\nonumber{}0, & l_{i}^{x}>-\infty ,\\\nonumber{}-\infty , & \mbox{otherwise},\end{array}\right.\mbox{ and }\bar{u}_{i}^{x}:=\left\lbrace{}\begin{array}{ll}\nonumber{}0, & u_{i}^{x}<\infty ,\\\nonumber{}\infty , & \mbox{otherwise}.\end{array}\right.\end{math} (13.2.18)

Stated differently, a certificate of dual infeasibility is any [[MathCmd 657]] such that

\begin{math}\nonumber{}\begin{array}{lcccl}\nonumber{} &  & c^{T}x^{*} & < & 0,\\\nonumber{}\bar{l}^{c} & \leq{} & Ax^{*} & \leq{} & \bar{u}^{c},\\\nonumber{}\bar{l}^{x} & \leq{} & x^{*} & \leq{} & \bar{u}^{x}\end{array}\end{math} (13.2.19)

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

Note that if [[MathCmd 657]] is a certificate of dual infeasibility then for any j such that

\begin{math}\nonumber{}x_{j}^{*}\not=0,\end{math} (13.2.20)

variable j is involved in the dual infeasibility.

Wed Feb 29 16:16:55 2012