15.1 Problem Analyzer¶

The problem analyzer prints a detailed survey of the

• linear constraints and objective
• conic constraints
• variables

of the model.

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 MSK_analyzeproblem. It produces output similar to the one below (this is the problem survey of the aflow30a problem from the MIPLIB 2003 collection).

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.

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, $$\sum_{j=0}^{n-1} a_{ij} x_j\leq u_i^c$$
• lower bd The number of lower bounded constraints, $$l_i^c\leq \sum_{j=0}^{n-1} a_{ij} x_j$$
• ranged The number of ranged constraints, $$l_i^c\leq \sum_{j=0}^{n-1} a_{ij} x_j\leq u_i^c$$
• fixed The number of fixed constraints, $$l_i^c = \sum_{j=0}^{n-1} a_{ij} x_j= u_i^c$$
• free The number of free constraints

Bounds

• upper bd The number of upper bounded variables, $$x_j \leq u_j^x$$
• lower bd The number of lower bounded variables, $$l_k^x\leq x_j$$
• ranged The number of ranged variables, $$l_k^x\leq x_j\leq u_j^x$$
• fixed The number of fixed variables, $$l_k^x = x_j = u_j^x$$
• free The number of free variables

Variables

• cont The number of continuous variables, $$x_j\in \real$$
• bin The number of binary variables, $$x_j\in \{0,1\}$$
• int The number of general integer variables, $$x_j\in \integral$$

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

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.

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.

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

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

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.