MINOS File Output

From TomWiki
Jump to navigationJump to search

The PRINT file

The following information is output to the PRINT file during the solution process. The longest line of output is 124 characters.

  • A listing of the SPECS file, if any.
  • The selected options.
  • An estimate of the storage needed and the amount available.
  • Some statistics about the problem data.
  • The storage available for the LU factors of the basis matrix.
  • A log from the scaling procedure, if Scaleoption > 0.
  • Notes about the initial basis obtained from CRASH or a BASIS file.
  • The major iteration log.
  • The minor iteration log.
  • Basis factorization statistics.
  • The EXIT condition and some statistics about the solution obtained.
  • The printed solution, if requested.

The last five items are described in the following sections.

The major iteration log

Problems with nonlinear constraints require several major iterations to reach a solution, each involving the so- lution of an LC subproblem (a linearly constrained subproblem that generates search directions for x and λ). If Printlevel = 0, one line of information is output to the PRINT file each major iteration. An example log is shown in <xr id="fig:exampleLog" />.

<figure id="fig:exampleLog">

Major minor   total ninf step     objective     Feasible Optimal  nsb   ncon     LU penalty BSwap
     1     1T      1    0 0.0E+00  0.00000000E+00 0.0E+00 1.2E+01    8      4     31 1.0E-01     0
     2    13      14    0 1.0E+00  2.67011596E+00 4.4E-06 2.8E-03    7     23     56 1.0E-01     8
 Completion Full    now requested
     3     3      17    0 1.0E+00  2.67009870E+00 3.1E-08 1.4E-06    7     29     41 1.0E-01     0
     4     0      17    0 1.0E+00  2.67009863E+00 5.6E-17 1.4E-06    7     30     41 1.0E-02     0

The Major Iteration log </figure>

Label Description
Major The current major iteration number.
minor is the number of iterations required by both the feasibility and optimality phases of the QP sub- problem. Generally, Mnr will be 1 in the later iterations, since theoretical analysis predicts that the correct active set will be identified near the solution.
total The total number of minor iterations.
ninf The number of infeasibilities in the LC subproblem. Normally 0, because the bounds on the linearized constraints are relaxed in several stages until the constraints are "feasible".
step The step length a taken along the current search direction p. The variables x have just been changed to x + ap. On reasonably well-behaved problems, step = 1.0 as the solution is approached, meaning the new estimate of (x, ?) is the solution of the LC subproblem.
objective The value of true objective function.
Feasible The value of rowerr, the maximum component of the scaled nonlinear constraint residual. The solution is regarded as acceptably feasible if Feasbl is less than the Row tolerance.
Optimal The value of maxgap, the maximum complementarity gap. It is an estimate of the degree of nonop- timality of the reduced costs. Both Feasible and Optimal are small in the neighborhood of a solution.
nsb The current number of superbasic variables.
ncon The number of times subroutine funcon has been called to evaluate the nonlinear constraint functions. The Jacobian has been evaluated or approximated essentially the same number of times. (Function evaluations needed to estimate the Jacobian by finite differences are not included.)
LU The number of nonzeros in the sparse LU factors of the basis matrix on completion of the LC subproblem. (The factors are computed at the start of each major iteration, and updated during minor iterations whenever a basis change occurs.)

As the solution is approached and the minor iterations decrease towards zero, LU reflects the number of nonzeros in the LU factors at the start of the LC subproblem.

penalty The penalty parameter ρk used in the modified augmented Lagrangian that defines the objective function for the LC subproblem.
BSwap The number of columns of the basis matrix B that were swapped with columns of S to improve the condition of B. The swaps are determined by an LU factorization of the rectangular matrix BS = ( B S )T with stability being favored more than sparsity.

<figure id="fig:minorIterLog">

    Itn ph pp     rg    +sbs  -sbs   -bs  step    pivot   ninf  sinf,objective     L     U ncp  nobj  ncon  nsb Hmod cond(H) conv
      1  1  1 -1.0E+00     2     2     1 3.0E+01  1.0E+00    1  1.35000000E+02     0    19   0
      2  1  1 -1.0E+00    27    27   102 7.0E+01  1.0E+00    1  1.05000000E+02     0    19   0
      3  1  1 -1.0E+00     3     3    27 3.0E+01 -1.0E+00    1  3.50000000E+01     1    19   0
      4  1  1 -1.0E+00    28    28    26 4.9E-11  1.0E+00    1  5.00000000E+00     1    20   0
      5  1  1 -1.0E+00    47    47     2 4.9E-11  1.0E+00    1  5.00000000E+00     1    20   0
      6  1  1  1.0E+00    27    27   101 5.0E+00 -1.0E+00    1  5.00000000E+00     2    20   0

 Itn      6 -- feasible solution.  Objective =  -1.818044887E+02

      7  3  1 -1.7E+01    87     0     0 1.0E+00  0.0E+00    0 -2.77020571E+02     4    21   0     6     0    1  1 0 1.0E+00 FFTT
      8  3  1 -1.7E+01    72     0     0 1.9E-01  0.0E+00    0 -3.05336895E+02     4    21   0     8     0    2  1 0 5.5E+00 FFTT
      9  3  1 -2.3E+01    41     0     0 1.0E+00  0.0E+00    0 -4.43743832E+02     4    21   0     9     0    3  1 0 6.5E+00 FFFF
     10  4  1  6.6E-01     0     0     0 6.0E+00  0.0E+00    0 -5.64075338E+02     4    21   0    11     0    3  1 0 3.5E+00 FFTT
...

    Itn ph pp     rg    +sbs  -sbs   -bs  step    pivot   ninf  sinf,objective     L     U ncp  nobj  ncon  nsb Hmod cond(H) conv
    161  4  1  8.8E-03     0    73    71 4.2E+00  1.0E+00    0 -1.73532497E+03     4    20   0   340     0   17  1 1 9.6E+00 TTTF
    162  3  1 -3.5E-02     6     0     0 1.5E+00  0.0E+00    0 -1.73533264E+03     4    20   0   342     0   18  1 0 1.3E+02 TTFF
    163  4  1  2.9E-02     0     0     0 4.5E+00  0.0E+00    0 -1.73533617E+03     4    20   0   344     0   18  1 0 2.0E+01 TTFF
    164  4  1  2.1E-02     0     0     0 2.3E+01  0.0E+00    0 -1.73538331E+03     4    20   0   347     0   18  1 0 9.8E+00 TTFF
    165  4  1  3.0E-02     0     0     0 5.0E+00  0.0E+00    0 -1.73552261E+03     4    20   0   349     0   18  1 0 2.1E+01 TTFF
    166  4  1  1.2E-02     0     0     0 1.0E+00  0.0E+00    0 -1.73556089E+03     4    20   0   350     0   18  1 0 2.2E+01 TTTF
 tolrg  reduced to  1.162E-03      lvltol = 1
    167  4  1  2.3E-03     0     0     0 1.0E+00  0.0E+00    0 -1.73556922E+03     4    20   0   351     0   18  1 0 2.2E+01 TTFF
    168  4  1  1.2E-03     0     0     0 7.9E-01  0.0E+00    0 -1.73556953E+03     4    20   0   353     0   18  1 0 2.1E+01 TTFF
    169  4  1  1.0E-04     0     0     0 1.0E+00  0.0E+00    0 -1.73556958E+03     4    20   0   354     0   18  1 0 2.0E+01 TTTT
 tolrg  reduced to  1.013E-05      lvltol = 1
    170  4  1  2.9E-05     0     0     0 1.1E+00  0.0E+00    0 -1.73556958E+03     4    20   0   356     0   18  1 0 1.7E+01 TTFF
    171  4  1  1.0E-05     0     0     0 1.0E+00  0.0E+00    0 -1.73556958E+03     4    20   0   357     0   18  1 0 1.7E+01 TTFF
    172  4  1  1.5E-06     0     0     0 1.2E+00  0.0E+00    0 -1.73556958E+03     4    20   0   359     0   18  1 0 1.7E+01 TTTF
 tolrg  reduced to  1.000E-06      lvltol = 2
    173  4  1  2.4E-07     0     0     0 1.0E+00  0.0E+00    0 -1.73556958E+03     4    20   0   360     0   18  1 0 1.7E+01 TTTF

 Biggest dj =  3.583E-03 (variable     25)   norm rg =  2.402E-07   norm pi =  1.000E+00

The Minor Iteration log </figure>

The minor iteration log

If Printlevel = 1, one line of information is output to the PRINT file every kth minor iteration, where k is the specified Print frequency (default k = 100). A heading is printed periodically. Problem t5weapon gives the log shown in <xr id="fig:minorIterLog" />.

Label Description
Itn The current minor iteration number.
ph The current phase of the solution procedure:
1 Phase 1 simplex method, trying to satisfy the linear constraints. The current solution is an infeasible vertex.
2 Phase 2 simplex method, solving a linear program.
3 Reduced-gradient method. A nonbasic variable has just become superbasic.
4 Reduced-gradient method, optimizing the current set of superbasic variables.
pp The Partial Price indicator. The variable selected by the last PRICE operation came from the ppth partition of A and I . pp is set to zero when the basis is refactored.

A PRICE operation is defined to be the process by which a nonbasic variable is selected to become a new superbasic. The selected variable is denoted by jq. Variable jq often becomes basic immediately.

Otherwise it remains superbasic, unless it reaches its opposite bound and becomes nonbasic again. If Partial price is in effect, variable jq is selected from App or Ipp , the ppth segments of the constraint matrix ( A I ).

rg In Phase 1, 2 or 3, this is dj, the reduced cost (reduced gradient) of the variable jq selected by PRICE at the start of the present iteration. Algebraically, dj = gj - πTaj for j = jq, where gj is the gradient of the current objective function, π is the vector of dual variables for the problem (or LC subproblem), and aj is the jth column of the current ( A I ).

In Phase 4, rg is the largest reduced gradient among the superbasic variables.

+sbs The variable jq selected by PRICE to be added to the superbasic set.
-sbs The variable chosen to leave the set of superbasics. It has become basic if the entry under -bs is nonzero; otherwise it has become nonbasic.
-bs The variable removed from the basis (if any) to become nonbasic.
step The step length a taken along the current search direction p. The variables x have just been changed to x + ap.
pivot If column aq replaces the rth column of the basis B, pivot is the rth element of a vector y satisfying By = aq . Wherever possible, step is chosen to avoid extremely small values of pivot (because they cause the basis to be nearly singular). In rare cases, it may be necessary to increase the Pivot tolerance to exclude very small elements of y from consideration during the computation of step.
ninf The number of infeasibilities before the present iteration. This number decreases monotonically.
sinf,objective If ninf > 0, this is sinf, the sum of infeasibilities before the present iteration. It usually decreases at each nonzero step, but if ninf decreases by 2 or more, sinf may occasionally increase.

Otherwise it is the value of the current objective function after the present iteration. For linear programs, it means the true linear objective function. For problems with linear constraints, it means the sum of the linear objective and the value returned by subroutine funobj. For problems with nonlinear constraints, it is the quantity just described if Lagrangian = No; otherwise it is the value of the augmented Lagrangian for the current major iterations (which tends to the true objective as convergence is approached).

L The number of nonzeros representing the basis factor L. Immediately after a basis factorization B = LU , this is lenL, the number of subdiagonal elements in the columns of a lower triangular matrix. Further nonzeros are added to L when various columns of B are later replaced. (Thus, L increases monotonically.)
U The number of nonzeros in the basis factor U . Immediately after a basis factorization, this is lenU, the number of diagonal and superdiagonal elements in the rows of an upper-triangular matrix. As columns of B are replaced, the matrix U is maintained explicitly (in sparse form). The value of U may fluctuate up or down; in general it will tend to increase.
ncp The number of compressions required to recover storage in the data structure for U . This includes the number of compressions needed during the previous basis factorization. Normally ncp should increase very slowly. If not, the amount of workspace available to MINOS should be increased by a significant amount. As a suggestion, the work array z(*) should be extended by 2(L + U) elements.

The following items are printed if the problem is nonlinear or if the superbasic set is non-empty (i.e., if the current solution is not a vertex).

Label Description
nobj The number of times subroutine funobj has been called.
ncon The number of times subroutine funcon has been called.
nsb The current number of superbasic variables.
Hmod An indication of the type of modifications made to the triangular matrix R that is used to approximate the reduced Hessian matrix. Two integers i1 and i2 are shown. They will remain zero for linear problems. If i1 = 1, a BFGS quasi-Newton update has been made to R, to account for a move within the current subspace. (This will not occur if the solution is infeasible.) If i2 = 1, R has been modified to account for a change in basis. This will sometimes occur even if the solution is infeasible (if a feasible point was obtained at some earlier stage).

Both updates are implemented by triangularizing the matrix R + vwT for some vectors v and w. If an update fails for numerical reasons, i1 or i2 will be set to 2, and the resulting R will be nearly singular. (However, this is highly unlikely.)

cond(H) An estimate of the condition number of the reduced Hessian. It is the square of the ratio of the largest and smallest diagonals of the upper triangular matrix R-a lower bound on the condition number of the matrix RTR that approximates the reduced Hessian. cond(H) gives a rough indication of whether or not the optimization procedure is having difficulty. The reduced-gradient algorithm will make slow progress if cond(H) becomes as large as 108 , and will probably fail to find a better solution if cond(H) reaches 1012 or more.

To guard against high values of cond(H), attention should be given to the scaling of the variables and the constraints. In some cases it may be necessary to add upper or lower bounds to certain variables to keep them a reasonable distance from singularities in the nonlinear functions or their derivatives.

conv A set of four logical variables C1 , C2 , C3 , C4 that are used to determine when to discontinue optimization in the current subspace (Phase 4) and consider releasing a nonbasic variable from its bound (the PRICE operation of Phase 3). Let rg be the norm of the reduced gradient, as described above. The meaning of the variables Cj is as follows:

C1 is true if the change in x was sufficiently small;

C2 is true if the change in the objective was sufficiently small;

C3 is true if rg is smaller than some loose tolerance TOLRG;

C4 is true if rg is smaller than some tighter tolerance.

The test used is of the form

if (C1 and C2 and C3 ) or C4 then go to Phase 3.

At present, tolrg = t|dj|, where t is the Subspace tolerance (nominally 0.5) and dj is the reduced- gradient norm at the most recent Phase 3 iteration. The "tighter tolerance" is the maximum of 0.1 tolrg and 10-7||π|| . Only the tolerance t can be altered at run-time.

Crash statistics

The following items are output to the PRINT file when no warm start is used. They refer to the number of columns that the CRASH procedure selects during several passes through A while searching for a triangular basis matrix.

Label Description
Slacks is the number of slacks selected initially.
Free cols is the number of free columns in the basis, including those whose bounds are rather far apart.
Preferred is the number of "preferred" columns in the basis (i.e., hs(j) = 3 for some j <= n). It will be a subset of the columns for which hs(j) = 3 was specified.
Unit is the number of unit columns in the basis.
Double is the number of columns in the basis containing 2 nonzeros.
Triangle is the number of triangular columns in the basis with 3 or more nonzeros.
Pad is the number of slacks used to pad the basis (to make it a nonsingular triangle).

Basis factorization statistics

If Printlevel => 1, the following items are output to the PRINT file whenever the basis B or the rectangular matrix BS = ( B S )T is factorized. Note that BS may be factorized at the start of just some of the major iterations. It is immediately followed by a factorization of B itself.

Gaussian elimination is used to compute a sparse LU factorization of B or BS , where PLPT and PUQ are lower and upper triangular matrices for some permutation matrices P and Q.

Label Description
Factorize The number of factorizations since the start of the run.
Demand A code giving the reason for the present factorization.
Itn The current iteration number.
Nonlin The number of nonlinear variables in the current basis B.
Linear The number of linear variables in B.
Slacks The number of slack variables in B.
m The number of rows in the matrix being factorized (B or BS ).
n The number of columns in the matrix being factorized. Preceded by "=" if the matrix is B; by ">" if it is BS .
Elems The number of nonzero elements in B or BS .
Amax The largest nonzero in B or BS .
Density The density of the matrix (percentage of nonzeros).
Merit The average Markowitz merit count for the elements chosen to be the diagonals of PUQ. Each merit count is defined to be (c - 1)(r - 1) where c and r are the number of nonzeros in the column and row containing the element at the time it is selected to be the next diagonal. Merit is the average of m such quantities. It gives an indication of how much work was required to preserve sparsity during the factorization.
lenL The number of nonzeros in the factor L.
L+U The number of nonzeros in both L and U .
Cmprssns The number of times the data structure holding the partially factored matrix needed to be compressed to recover unused storage. Ideally this number should be zero. If it is more than 3 or 4, the amount of workspace available to MINOS should be increased for efficiency.
Incres The percentage increase in the number of nonzeros in L and U relative to the number of nonzeros in B or BS .
Utri The size of the "backward triangle" in B or BS . These top rows of U come directly from the matrix.
lenU The number of nonzeros in the factor U .
Ltol The maximum allowed size of nonzeros in L. Usually equal to the LU factor tolerance.
Umax The maximum nonzero in U .
Ugrwth The ratio Umax / Amax.
Ltri The size of the "forward triangle" in B or BS . These initial columns of L come directly from the matrix.
dense1 is the number of columns remaining when the density of the basis matrix being factorized reached 0.3.
Lmax The maximum nonzero in L (no larger than Ltol).
Akmax The maximum nonzero arising during the factorization. (Printed only if Threshold Complete Pivoting is in effect.)
Agrwth The ratio Akmax / Amax. (Printed only if Threshold Complete Pivoting is in effect.)
bump The number of columns of B or BS excluding Utri and Ltri.
dense2 The number of columns remaining when the density of the basis matrix being factorized reached 0.6.
DUmax The largest diagonal of U (really P U Q).
DUmin The smallest diagonal of U .
condU The ratio DUmax/DUmin. As long as Ltol is not large (say 10.0 or less), condU is an estimate of the condition number of B. If this number is extremely large, the basis is nearly singular and some numerical difficulties might occur. (However, an effort is made to avoid near-singularity by using slacks to replace columns of B that would have made Umin extremely small. Messages are issued to this effect, and the modified basis is refactored.)

EXIT conditions

When the solution procedure terminates, an EXIT -- message is printed to summarize the final result. Here we describe each message and suggest possible courses of action.

The number associated with each EXIT is the output value of the integer variable inform.

The following messages arise when the SPECS file is found to contain no further problems.

-2 	EXIT -- input error.

MINOS encountered end-of-file or an endrun card before finding a SPECS file.

Otherwise, the SPECS file may be empty, or cards containing the keywords Skip or Endrun may imply that all problems should be ignored.

-1    ENDRUN

This message is printed at the end of a run if MINOS terminates of its own accord. Otherwise, the operating system will have intervened for one of many possible reasons (excess time, missing file, arithmetic error in user routines, etc.).

The following messages arise when a solution exists (though it may not be optimal).

0	EXIT -- optimal solution  found

This is the message we all hope to see! It is certainly preferable to every other message, and we naturally want to believe what it says, because this is surely one situation where the computer knows best. There may be cause for celebration if the objective function has reached an astonishing new high (or low).

In all cases, a distinct level of caution is in order, even if it can wait until next morning. For example, if the objective value is much better than expected, we may have obtained an optimal solution to the wrong problem! Almost any item of data could have that effect if it has the wrong value. Verifying that the problem has been defined correctly is one of the more difficult tasks for a model builder. It is good practice in the function subroutines to print any data that is input during the first entry.

If nonlinearities exist, one must always ask the question: could there be more than one local optimum? When the constraints are linear and the objective is known to be convex (e.g., a sum of squares) then all will be well if we are minimizing the objective: a local minimum is a global minimum in the sense that no other point has a lower function value. (However, many points could have the same objective value, particularly if the objective is largely linear.) Conversely, if we are maximizing a convex function, a local maximum cannot be expected to be global, unless there are sufficient constraints to confine the feasible region.

Similar statements could be made about nonlinear constraints defining convex or concave regions. However, the functions of a problem are more likely to be neither convex nor concave. Always specify a good starting point if possible, especially for nonlinear variables, and include reasonable upper and lower bounds on the variables to confine the solution to the specific region of interest. We expect modelers to know something about their problem, and to make use of that knowledge as well as they can.

One other caution about "Optimal solution"s. Some of the variables or slacks may lie outside their bounds more than desired, especially if scaling was requested. Max Primal infeas refers to the largest bound infeasibility and which variable (or slack) is involved. If it is too large, consider restarting with a smaller Feasibility tolerance (say 10 times smaller) and perhaps Scale option 0.

Similarly, Max Dual infeas indicates which variable is most likely to be at a non-optimal value. Broadly speaking, if

MaxDualinfeas/Normofpi = 10-d,

then the objective function would probably change in the dth significant digit if optimization could be continued. If d seems too large, consider restarting with smaller Optimality tolerances.

Finally, Nonlinear constraint violn shows the maximum infeasibility for nonlinear rows. If it seems too large, consider restarting with a smaller Row tolerance.

1	EXIT -- the  problem  is infeasible

When the constraints are linear, this message can probably be trusted. Feasibility is measured with respect to the upper and lower bounds on the variables and slacks. Among all the points satisfying the general constraints Ax+s = 0, there is apparently no point that satisfies the bounds on x and s. Violations as small as the Feasibility tolerance are ignored, but at least one component of x or s violates a bound by more than the tolerance.

When nonlinear constraints are present, infeasibility is much harder to recognize correctly. Even if a feasible solution exists, the current linearization of the constraints may not contain a feasible point. In an attempt to deal with this situation, when solving each linearly constrained (LC) subproblem, MINOS is prepared to relax the bounds on the slacks associated with nonlinear rows.

If an LC subproblem proves to be infeasible or unbounded (or if the Lagrange multiplier estimates for the nonlinear constraints become large), MINOS enters so-called "nonlinear elastic" mode. The subproblem includes the original QP objective and the sum of the infeasibilities-suitably weighted using the Elastic weight parameter. In elastic mode, some of the bounds on the nonlinear rows "elastic"-i.e., they are allowed to violate their specified bounds. Variables subject to elastic bounds are known as elastic variables. An elastic variable is free to violate one or both of its original upper or lower bounds. If the original problem has a feasible solution and the elastic weight is sufficiently large, a feasible point eventually will be obtained for the perturbed constraints, and optimization can continue on the subproblem. If the nonlinear problem has no feasible solution, MINOS will tend to determine a "good" infeasible point if the elastic weight is sufficiently large. (If the elastic weight were infinite, MINOS would locally minimize the nonlinear constraint violations subject to the linear constraints and bounds.)

Unfortunately, even though MINOS locally minimizes the nonlinear constraint violations, there may still exist other regions in which the nonlinear constraints are satisfied. Wherever possible, nonlinear constraints should be defined in such a way that feasible points are known to exist when the constraints are linearized.

2	EXIT -- the  problem  is unbounded	(or badly  scaled)
	EXIT -- violation limit exceeded -- the  problem  may  be unbounded

For linear problems, unboundedness is detected by the simplex method when a nonbasic variable can apparently be increased or decreased by an arbitrary amount without causing a basic variable to violate a bound. A message prior to the EXIT message will give the index of the nonbasic variable. Consider adding an upper or lower bound to the variable. Also, examine the constraints that have nonzeros in the associated column, to see if they have been formulated as intended.

Very rarely, the scaling of the problem could be so poor that numerical error will give an erroneous indication of unboundedness. Consider using the Scale option.

For nonlinear problems, MINOS monitors both the size of the current objective function and the size of the change in the variables at each step. If either of these is very large (as judged by the Unbounded parameters, the problem is terminated and declared UNBOUNDED. To avoid large function values, it may be necessary to impose bounds on some of the variables in order to keep them away from singularities in the nonlinear functions.

The second message indicates an abnormal termination while enforcing the limit on the constraint violations. This exit implies that the objective is not bounded below in the feasible region defined by expanding the bounds by the value of the Violation limit.

3	EXIT -- major  iteration limit exceeded EXIT -- minor  iteration limit exceeded EXIT -- too  many  iterations

Either the Iterations limit or the Major iterations limit was exceeded before the required solution could be found. Check the iteration log to be sure that progress was being made. If so, restart the run using WarmDefSOL at the end of the run.

4	EXIT -- requested  accuracy  could  not  be achieved

A feasible solution has been found, but the requested accuracy in the dual infeasibilities could not be achieved. An abnormal termination has occurred, but MINOS is within 10-2 of satisfying the Major optimality tolerance. Check that the Major optimality tolerance is not too small.

5	EXIT -- the  superbasics limit is too  small:	nnn

The problem appears to be more nonlinear than anticipated. The current set of basic and superbasic variables have been optimized as much as possible and a PRICE operation is necessary to continue, but there are already nnn superbasics (and no room for any more).

In general, raise the Superbasics limit s by a reasonable amount, bearing in mind the storage needed for the reduced Hessian (about 1 s2 double words).

6	EXIT --  constraint and objective values  could  not  be calculated

This exit occurs if a value mode = -1 is set during some call to funobj or funcon. MINOS assumes that you want the problem to be abandoned forthwith.

In some environments, this exit means that your subroutines were not successfully linked to MINOS. If the default versions of funobj and funcon are ever called, they issue a warning message and then set mode to terminate the run.

7	EXIT -- subroutine funobj seems to  be giving incorrect  gradients

A check has been made on some individual elements of the objective gradient array at the first point that satisfies the linear constraints. At least one component gObj(j) is being set to a value that disagrees markedly with a forward-difference estimate of ?f /?xj . (The relative difference between the computed and estimated values is 1.0 or more.) This exit is a safeguard, since MINOS will usually fail to make progress when the computed gradients are seriously inaccurate. In the process it may expend considerable effort before terminating with EXIT 9 below.

Check the function and gradient computation very carefully in funobj. A simple omission (such as forgetting to divide fObj by 2) could explain everything. If fObj or gObj(j) is very large, then give serious thought to scaling the function or the nonlinear variables.

If you feel certain that the computed gObj(j) is correct (and that the forward-difference estimate is therefore wrong), you can specify Verify level 0 to prevent individual elements from being checked. However, the optimization procedure may have difficulty.

8	EXIT -- subroutine funcon  seems to  be giving incorrect  gradients

This is analogous to the preceding exit. At least one of the computed Jacobian elements is significantly different from an estimate obtained by forward-differencing the constraint vector F (x). Follow the advice given above, trying to ensure that the arrays fCon and gCon are being set correctly in funcon.

9	EXIT -- the  current point cannot  be improved  upon

Several circumstances could lead to this exit.

  1. Subroutines funobj or funcon could be returning accurate function values but inaccurate gradients (or vice versa). This is the most likely cause. Study the comments given for EXIT 7 and 8, and do your best to ensure that the coding is correct.
  2. The function and gradient values could be consistent, but their precision could be too low. For example, accidental use of a real data type when double precision was intended would lead to a relative function precision of about 10-6 instead of something like 10-15 . The default Optimality tolerance of 10-6 would need to be raised to about 10-3 for optimality to be declared (at a rather suboptimal point). Of course, it is better to revise the function coding to obtain as much precision as economically possible.
  3. If function values are obtained from an expensive iterative process, they may be accurate to rather few significant figures, and gradients will probably not be available. One should specify
Function precision t
Major optimality tolerance

but even then, if t is as large as 10-5 or 10-6 (only 5 or 6 significant figures), the same exit condition may occur. At present the only remedy is to increase the accuracy of the function calculation.

10   EXIT -- cannot  satisfy the  general  constraints

An LU factorization of the basis has just been obtained and used to recompute the basic variables xB , given the present values of the superbasic and nonbasic variables. A step of "iterative refinement" has also been applied to increase the accuracy of xB . However, a row check has revealed that the resulting solution does not satisfy the current constraints Ax - s = 0 sufficiently well.

This probably means that the current basis is very ill-conditioned. Try Scale option 1 if scaling has not yet been used and there are some linear constraints and variables.

For certain highly structured basis matrices (notably those with band structure), a systematic growth may occur in the factor U . Consult the description of Umax, Umin and Growth in #Basis factorization statistics, and set the LU factor tolerance to 2.0 (or possibly even smaller, but not less than 1.0).

12   EXIT -- terminated from  subroutine s1User

The user has set the value iAbort = 1 in subroutine s1User. MINOS assumes that you want the problem to be abandoned forthwith.

If the following exits occur during the first basis factorization, the primal and dual variables x and pi will have their original input values. BASIS files will be saved if requested, but certain values in the printed solution will not be meaningful.

20   EXIT -- not  enough integer/real storage  for the  basis  factors

The main integer or real storage array iw(*) or rw(*) is apparently not large enough for this problem. The routine declaring iw and rw should be recompiled with a larger dimensions for those arrays. The new values should also be assigned to leniw and lenrw.

An estimate of the additional storage required is given in messages preceding the exit.

21   EXIT -- error in basis  package

A preceding message will describe the error in more detail. One such message says that the current basis has more than one element in row i and column j. This could be caused by a corresponding error in the input parameters a(*), ha(*), and ka(*).

22   EXIT -- singular basis  after nnn factorization attempts

This exit is highly unlikely to occur. The first factorization attempt will have found the basis to be structurally or numerically singular. (Some diagonals of the triangular matrix U were respectively zero or smaller than a certain tolerance.) The associated variables are replaced by slacks and the modified basis is refactorized, but singularity persists. This must mean that the problem is badly scaled, or the LU factor tolerance is too much larger than 1.0.

If the following messages arise, either an OLD BASIS file could not be loaded properly, or some fatal system error has occurred. New BASIS files cannot be saved, and there is no solution to print. The problem is abandoned.

30   EXIT -- the  basis  file dimensions  do not  match this problem

On the first line of the OLD BASIS file, the dimensions labeled m and n are different from those associated with the problem that has just been defined. You have probably loaded a file that belongs to another problem.

Remember, if you have added rows or columns to a(*), ha(*) and ka(*), you will have to alter m and n and the map beginning on the third line (a hazardous operation). It may be easier to restart with a PUNCH or DUMP file from an earlier version of the problem.

31   EXIT -- the  basis  file state vector does not  match this problem

For some reason, the OLD BASIS file is incompatible with the present problem, or is not consistent within itself. The number of basic entries in the state vector (i.e., the number of 3's in the map) is not the same as m on the first line, or some of the 2's in the map did not have a corresponding "j xj " entry following the map.

32   EXIT -- system error.  Wrong no.  of  basic  variables:   nnn

This exit should never happen. It may indicate that the wrong MINOS source files have been compiled, or incorrect parameters have been used in the call to subroutine minoss.

Check that all integer variables and arrays are declared integer in your calling program (including those beginning with h!), and that all "real" variables and arrays are declared consistently. (They should be double precision on most machines.)

The following messages arise if additional storage is needed to allow optimization to begin. The problem is abandoned.

42   EXIT -- not  enough 8-character storage  to  start  solving the  problem

The main character storage array cw(*) is not large enough.

43   EXIT -- not  enough integer storage  to  start  solving the  problem

The main integer storage array iw(*) is not large enough to provide workspace for the optimization procedure. See the advice given for Exit 20.

44   EXIT -- not  enough real storage  to  start  solving the  problem

The main storage array rw(*) is not large enough to provide workspace for the optimization procedure. Be sure that the Superbasics limit is not unreasonably large. Otherwise, see the advice for EXIT 20.

Solution output

At the end of a run, the final solution is output to the PRINT file in accordance with the Solution keyword. Some header information appears first to identify the problem and the final state of the optimization procedure. A ROWS section and a COLUMNS section then follow, giving one line of information for each row and column. The format used is similar to certain commercial systems, though there is no industry standard.

An example of the printed solution is given in #top. In general, numerical values are output with format f16.5. The maximum record length is 111 characters, including the first (carriage-control) character.

To reduce clutter, a dot "." is printed for any numerical value that is exactly zero. The values ±1 are also printed specially as 1.0 and -1.0. Infinite bounds (±1020 or larger) are printed as None.

Note : If two problems are the same except that one minimizes an objective f (x) and the other maximizes -f (x), their solutions will be the same but the signs of the dual variables πi and the reduced gradients dj will be reversed.

The ROWS section

General linear constraints take the form . The ith constraint is therefore of the form

and the value of aTx is called the row activity. Internally, the linear constraints take the form Ax - s = 0, where the slack variables s should satisfy the bounds . For the ith "row", it is the slack variable si that is directly available, and it is sometimes convenient to refer to its state. Slacks may be basic or nonbasic (but not superbasic).

Nonlinear constraints are treated similarly, except that the row activity and degree of infeasibility are computed directly from Fi (x) + aTx rather than from si .

Label Description
Number The value n + i. This is the internal number used to refer to the ith slack in the iteration log.
Row The name of the ith row.
State The state of the ith row relative to the bounds αand β. The various states possible are as follows.
LL The row is at its lower limit, α.
UL The row is at its upper limit, β.
EQ The limits are the same (α = β).
BS The constraint is not binding. si is basic.

A key is sometimes printed before the State to give some additional information about the state of the slack variable.

A Alternative optimum possible. The slack is nonbasic, but its reduced gradient is essen- tially zero. This means that if the slack were allowed to start moving from its current value, there would be no change in the objective function. The values of the basic and superbasic variables might change, giving a genuine alternative solution. The values of the dual variables might also change.
D Degenerate. The slack is basic, but it is equal to (or very close to) one of its bounds.
I Infeasible. The slack is basic and is currently violating one of its bounds by more than the Feasibility tolerance.
N Not precisely optimal. The slack is nonbasic. Its reduced gradient is larger than the Optimality tolerance.

Note: If Scaleoption > 0, the tests for assigning A, D, I, N are made on the scaled problem, since the keys are then more likely to be meaningful.

Activity The row value aTx (or Fi (x) + aTx for nonlinear rows).
Slack activity The amount by which the row differs from its nearest bound. (For free rows, it is taken to be minus the Activity.)
Lower limit α, the lower bound on the row.
Upper limit β, the upper bound on the row.
Dual activity The value of the dual variable pi , often called the shadow price (or simplex multiplier) for the ith constraint. The full vector p always satisfies BTp = gB , where B is the current basis matrix and gB contains the associated gradients for the current objective function.
I The constraint number, i.

The COLUMNS section

Here we talk about the "column variables" xj , j = 1 : n. We assume that a typical variable has bounds .

Label Description
Number The column number, j. This is the internal number used to refer to xjin the iteration log.
Column The name of xj .
State The state of xj relative to the bounds a and ß. The various states possible are as follows.
LL xj is nonbasic at its lower limit, α.
UL xj is nonbasic at its upper limit, β.
EQ xj is nonbasic and fixed at the value α = β.
FR xj is nonbasic at some value strictly between its bounds: α < xj < β.
BS xj is basic. Usually α < xj < β.
SBS xj is superbasic. Usually α < xj < β.

A key is sometimes printed before the State to give some additional information about the state of xj.

A Alternative optimum possible. The variable is nonbasic, but its reduced gradient is essentially zero. This means that if xj were allowed to start moving from its current value, there would be no change in the objective function. The values of the basic and superbasic variables might change, giving a genuine alternative solution. The values of the dual variables might also change.
D Degenerate. xj is basic, but it is equal to (or very close to) one of its bounds.
I Infeasible. xj is basic and is currently violating one of its bounds by more than the Feasibility tolerance.
N Not precisely optimal. xj is nonbasic. Its reduced gradient is larger than the Optimality tolerance .

Note: If Scaleoption > 0, the tests for assigning A, D, I, N are made on the scaled problem, since the keys are then more likely to be meaningful.

Activity The value of the variable xj .
Obj Gradient gj, the jth component of the gradient of the (linear or nonlinear) objective function. (If any xj is infeasible, gj is the gradient of the sum of infeasibilities.)
Lower limit α, the lower bound on xj.
Upper limit β, the upper bound on xj .
Reduced gradient The reduced gradient dj = gj - πTaj, where aj is the jth column of the constraint matrix (or the jth column of the Jacobian at the start of the final major iteration).
M+J The value m + j.

The SUMMARY file

If Summaryfile > 0, the following information is output to the SUMMARY file. (It is a brief form of the PRINT file.) All output lines are less than 72 characters.

  • The Begin line from the SPECS file, if any.
  • The basis file loaded, if any.
  • A brief Major iteration log.
  • A brief Minor iteration log.
  • The EXIT condition and a summary of the final solution.

The following SUMMARY file is from example problem t6wood using Print level 0 and Major damping parameter 0.5.

      ==============================
      M I N O S  5.51     (Nov 2002)
      ==============================

 Begin t6wood   (WOPLANT test problem; optimal obj = -15.55716)

 Name   WOPLANT
 ===>  Note:  row  OBJ       selected as linear part of objective.
 Rows          9
 Columns      12
 Elements     73

 Scale option  2,    Partial price   1

 Itn      0 -- linear constraints satisfied.

 This is problem t6wood.  Derivative level =  3

 funcon  sets      36   out of      50   constraint gradients.

 Major minor  step     objective  Feasible Optimal  nsb   ncon penalty BSwap
     1     0T 0.0E+00  0.00000E+00 5.9E-01 1.1E+01    0      4 1.0E+00     0
     2    22  5.0E-01 -1.56839E+01 2.7E-01 1.6E+01    3     47 1.0E+00     0
     3    10  6.0E-01 -1.51527E+01 1.5E-01 9.9E+00    2     68 1.0E+00     2
     4    21  5.7E-01 -1.53638E+01 6.4E-02 3.6E+00    3    113 1.0E+00     1
     5    15  1.0E+00 -1.55604E+01 2.7E-02 1.4E-01    3    144 1.0E+00     0
     6     5  1.0E+00 -1.55531E+01 6.4E-03 2.2E-01    3    154 1.0E+00     0
     7     4  1.0E+00 -1.55569E+01 3.1E-04 7.0E-04    3    160 1.0E-01     0
     8     2  1.0E+00 -1.55572E+01 1.6E-08 1.1E-04    3    163 1.0E-02     0
     9     1  1.0E+00 -1.55572E+01 5.1E-14 2.2E-06    3    165 1.0E-03     0

 EXIT -- optimal solution found

 Problem name                 WOPLANT
 No. of iterations                  80   Objective value     -1.5557160112E+01
 No. of major iterations             9   Linear objective    -1.5557160112E+01
 Penalty parameter            0.000100   Nonlinear objective  0.0000000000E+00
 No. of calls to funobj              0   No. of calls to funcon            165
 No. of superbasics                  3   No. of basic nonlinears             6
 No. of degenerate steps             0   Percentage                       0.00
 Norm of x   (scaled)          9.8E-01   Norm of pi  (scaled)          1.8E+02
 Norm of x                     3.2E+01   Norm of pi                    1.6E+01
 Max Prim inf(scaled)        0 0.0E+00   Max Dual inf(scaled)        1 2.2E-06
 Max Primal infeas           0 0.0E+00   Max Dual infeas             1 5.8E-08
 Nonlinear constraint violn    5.1E-14



 Solution printed on file   9

 funcon called with nstate =   2

 Time for MPS input                           0.00 seconds
 Time for solving problem                     0.04 seconds
 Time for solution output                     0.00 seconds
 Time for constraint functions                0.00 seconds
 Time for objective function                  0.00 seconds

The following information is output to the PRINT file during the solution process. The longest line of output is 124 characters.

  • A listing of the SPECS file, if any.
  • The selected options.
  • An estimate of the storage needed and the amount available.
  • Some statistics about the problem data.
  • The storage available for the LU factors of the basis matrix.
  • A log from the scaling procedure, if Scaleoption > 0.
  • Notes about the initial basis obtained from CRASH or a BASIS file.
  • The major iteration log.
  • The minor iteration log.
  • Basis factorization statistics.
  • The EXIT condition and some statistics about the solution obtained.
  • The printed solution, if requested.

The last five items are described in the following sections.