MINOS File Output
Contents
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:
| ||||||||
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 d_{j}, the reduced cost (reduced gradient) of the variable jq selected by PRICE at the start of the present iteration. Algebraically, d_{j} = g_{j} - π^{T}a_{j} for j = jq, where g_{j} is the gradient of the current objective function, π is the vector of dual variables for the problem (or LC subproblem), and a_{j} 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 i_{1} and i_{2} are shown. They will remain zero for linear problems. If i_{1} = 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 i_{2} = 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 + vw^{T} for some vectors v and w. If an update fails for numerical reasons, i_{1} or i_{2} 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 10^{8} , and will probably fail to find a better solution if cond(H) reaches 10^{12} 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 C_{1} , C_{2} , C_{3} , C_{4} 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 C_{j} is as follows:
C_{1} is true if the change in x was sufficiently small; C_{2} is true if the change in the objective was sufficiently small; C_{3} is true if rg is smaller than some loose tolerance TOLRG; C_{4} is true if rg is smaller than some tighter tolerance. The test used is of the form if (C_{1} and C_{2} and C_{3} ) or C_{4} 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 B_{S} = ( B S )^{T} is factorized. Note that B_{S} 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 PLP^{T} 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.
- 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.
- 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.
- 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 x_{B} , given the present values of the superbasic and nonbasic variables. A step of "iterative refinement" has also been applied to increase the accuracy of x_{B} . 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 x_{j} " 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 (±10^{20} 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 d_{j} will be reversed.
The ROWS section
General linear constraints take the form . The ith constraint is therefore of the form
and the value of a^{T}x 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 s_{i} 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) + a^{T}x rather than from s_{i} .
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.
A key is sometimes printed before the State to give some additional information about the state of the slack variable.
| ||||||||||||||||
Activity | The row value a^{T}x (or F_{i} (x) + a^{T}x 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 B^{T}p = g_{B} , 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" x_{j} , 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 x_{j}in the iteration log. | ||||||||||||||||||||
Column | The name of x_{j} . | ||||||||||||||||||||
State | The state of xj relative to the bounds a and ß. The various states possible are as follows.
A key is sometimes printed before the State to give some additional information about the state of x_{j}.
| ||||||||||||||||||||
Activity | The value of the variable x_{j} . | ||||||||||||||||||||
Obj Gradient | g_{j}, the jth component of the gradient of the (linear or nonlinear) objective function. (If any x_{j} is infeasible, g_{j} is the gradient of the sum of infeasibilities.) | ||||||||||||||||||||
Lower limit | α, the lower bound on x_{j}. | ||||||||||||||||||||
Upper limit | β, the upper bound on x_{j} . | ||||||||||||||||||||
Reduced gradient | The reduced gradient d_{j} = g_{j} - π^{T}a_{j}, where a_{j} 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.