 |
[ Home | Support | Sales | Solvers | Documentation | Model Libraries | Search | Contact Us ] |
|---|
|
The log file of MINOS (the "screen output") is not fully documented in the GAMS manual. This note will help you to decipher that output.
MINOS writes different logs for LPs, NLPs with linear constraints and NLPs with nonlinear constraints. We will show a sample log file for each case, and we will explain the messages that appear there.
The log file is usually connected to the screen, but with the command
gams mexls logline=1 logoption=2 logfile=mexls.log
the log file will be redirected to the file mexls.log. The logline option tells GAMS not to update the line counter the way it is doing on the screen, and logoption=2 means "write log to a file", with the file name being specified by the logfile option.
MINOS uses a standard two-phase Simplex method for LPs. In the first phase, the sum of the infeasibilities at each iteration is minimized. Once feasibility is attained, MINOS switches to phase 2 where it minimizes (or maximizes) the original objective function. The different objective functions are called the phase 1 and phase 2 objectives. Notice that the marginals in phase 1 are with respect to the phase 1 objective. This means that if MINOS interrupts in phase 1, the marginals are "wrong" in the sense that they do not reflect your original objective.
The log for the problem MEXLS is:
GAMS 2.25.060 (c) Copyright 1992 GAMS Development Corp. All rights reserved
Licensee: Erwin G920429-2010CX-AIX
GAMS
--- Starting compilation
--- mexls.gms(1242)
--- Starting execution
--- mexls.gms(1241)
--- Generating model ONE
--- mexls.gms(1242)
--- 353 rows, 578 columns, and 1873 non-zeroes.
--- Executing MINOS5
Work space allocated -- .21 Mb
Reading data...
Itn Nopt Ninf Sinf,Objective
1 1 74 1.62609255E+01
20 14 74 1.62609255E+01
40 4 67 1.40246211E+01
60 14 55 1.10065392E+01
80 12 42 8.35651175E+00
Itn Nopt Ninf Sinf,Objective
100 6 31 7.21650054E+00
120 21 20 6.65998885E+00
140 13 11 5.77113823E+00
160 1 8 2.35537706E+00
180 4 5 9.58810903E-01
Itn Nopt Ninf Sinf,Objective
200 9 2 3.16184199E-01
Itn 208 -- Feasible solution. Objective = 4.283788540E+04
220 2 0 4.11169434E+04
240 25 0 3.88351313E+04
260 1 0 3.77495457E+04
280 11 0 3.66399964E+04
Itn Nopt Ninf Sinf,Objective
300 2 0 3.30955215E+04
320 2 0 3.09919632E+04
340 5 0 2.84521363E+04
360 1 0 2.76671551E+04
380 2 0 2.76055456E+04
Itn 392 -- 80 nonbasics set on bound, basics recomputed
Itn 392 -- Feasible solution. Objective = 2.756959890E+04
EXIT -- OPTIMAL SOLUTION FOUND
Major, Minor itns 1 392
Objective function 2.7569598897150E+04
Degenerate steps 83 21.17
Norm X, Norm PI 2.10E+01 4.49E+04
Norm X, Norm PI 8.05E+03 1.06E+02 (unscaled)
--- Restarting execution
--- mexls.gms(1242)
--- Reading solution for model ONE
--- All done
Let us consider the various sections of the log file shown above in order.
-------------------------------------------------------------------- Work space allocated -- .21 Mb Reading data... --------------------------------------------------------------------
First when we load MINOS we estimate how much memory is needed. This estimate is based on statistics like the number of rows, columns and non-zeros. We then allocate this amount of memory and start loading the problem.
The memory estimate can be overwritten by the WORKSPACE model suffix as follows:
MODEL M /ALL/;
M.WORKSPACE = 10; { ask for 10 megabytes }
SOLVE M USING NLP MINIMIZING Z;
Next, let us examine the iteration log that Minos writes out, In the beginning, MINOS has not found a feasible solution, and the screen log during this phase of the search looks like:
--------------------------------------------------------------------
Itn Nopt Ninf Sinf,Objective
1 1 74 1.62609255E+01
--------------------------------------------------------------------
The first column gives the iteration count. A simplex iteration corresponds to a basis change. Nopt means "Number of non-optimalities", and Ninf means "Number of infeasibilities". Nopts are the number of marginals that do not have the correct sign: they do not satisfy the optimality conditions. The last column gives the "Sum of infeasibilities" in phase 1 (when Ninf>0) or the Objective in phase 2.
As soon as MINOS finds a feasible solution, it returns a message similar to the one below that appears for the example discussed:
-------------------------------------------------------------------- Itn 208 -- Feasible solution. Objective = 4.283788540E+04 --------------------------------------------------------------------
MINOS found a feasible solution and will switch from phase 1 to phase 2. During phase 2 (or the search once feasibility has been reached), MINOS returns a message that looks like
-------------------------------------------------------------------- Itn 392 -- 80 nonbasics set on bound, basics recomputed --------------------------------------------------------------------
MINOS sets all the nonbasics to their bounds and recomputes the basics.
Even nonbasic variables may not be exactly on their bounds during the optimization phase. MINOS uses a sliding tolerance scheme to fight stalling as a result of degeneracy. Before it terminates it wants to get the "real" solution. The nonbasics are therefore reset to their bounds and the basic variables are recomputed to satisfy the constraints Ax = b. If the resulting solution is infeasible or non-optimal, MINOS will continue iterating. If necessary, this process is repeated one more time. Fortunately, optimality is usually confirmed very soon after the first "reset".
-------------------------------------------------------------------- Itn 392 -- Feasible solution. Objective = 2.756959890E+04 --------------------------------------------------------------------
Still feasible after this exercise. That is good.
-------------------------------------------------------------------- Major, Minor itns 1 392 Objective function 2.7569598897150E+04 Degenerate steps 83 21.17 Norm X, Norm PI 2.10E+01 4.49E+04 Norm X, Norm PI 8.05E+03 1.06E+02 (unscaled) --------------------------------------------------------------------
For an LP, the number of major iterations is always one. The number of minor iterations is the number of Simplex iterations.
Degenerate steps are ones where a Simplex iteration did not do much other than a basis change: two variables changed from basic to nonbasic and vice versa, but none of the activity levels changed. In this example there were 83 degenerate iterations, or 21.17% of 392.
The norms ||x||, ||pi|| are also printed both before and after the model is unscaled. Ideally the scaled ||x|| should be about 1 (say in the range 0.1 to 100), and ||pi|| should be greater than 1. If the scaled ||x|| is closer to 1 than the final ||x||, then scaling was probably helpful. Otherwise, the model might solve more efficiently without scaling.
If ||x|| or ||pi|| are several orders of magnitude different before and after scaling, you may be able to help MINOS by scaling certain sets of variables or constraints yourself (for example, by choosing different units for variables whose final values are very large.)
An example of a problem with a nonlinear objective and linear constraints is WEAPONS. Here the screen output that results from solving this model with MINOS.
GAMS 2.25.060 (c) Copyright 1992 GAMS Development Corp. All rights reserved
Licensee: Erwin G920429-2010CX-AIX
GAMS
--- Starting compilation
--- weapons.gms(59)
--- Starting execution
--- weapons.gms(57)
--- Generating model WAR
--- weapons.gms(59)
--- 13 rows, 66 columns, and 156 non-zeroes.
--- Executing MINOS5
Work space allocated -- .06 Mb
Reading data...
Reading nonlinear code...
Itn Nopt Ninf Sinf,Objective Nobj NSB
1 -1 3 9.75000000E+01 3 64
Itn 6 -- Feasible solution. Objective = 1.511313490E+03
20 5 0 1.70385909E+03 23 45
40 3 0 1.73088173E+03 63 30
60 1 0 1.73381961E+03 109 25
80 1 0 1.73518225E+03 155 20
Itn Nopt Ninf Sinf,Objective Nobj NSB
100 0 0 1.73555465E+03 201 17
EXIT -- OPTIMAL SOLUTION FOUND
Major, Minor itns 1 119
Objective function 1.7355695798562E+03
FUNOBJ, FUNCON calls 245 0
Superbasics, Norm RG 18 2.18E-08
Degenerate steps 2 1.68
Norm X, Norm PI 2.74E+02 1.00E+00
Norm X, Norm PI 2.74E+02 1.00E+00 (unscaled)
--- Restarting execution
--- weapons.gms(59)
--- Reading solution for model WAR
--- All done
The parts decribed in the LP example will not be repeated. We will discuss only the new additions is:
-------------------------------------------------------------------- Reading nonlinear code... --------------------------------------------------------------------
Besides reading the matrix we now also read the instructions that allow the interpreter to calculate nonlinear function values and their derivatives.
The iteration log looks slightly different and has a couple of additional columns
--------------------------------------------------------------------
Itn Nopt Ninf Sinf,Objective Nobj NSB
1 -1 3 9.75000000E+01 3 64
--------------------------------------------------------------------
The column Nobj gives the number of times MINOS calculated the objective and its gradient. The column NSB contains the number of superbasics. In MINOS, variables are basic, nonbasic or superbasic. The number of superbasics is a measure of "how nonlinear" the problem is, once the number settles down. (There may be rather more at the beginning of a run.) The final number of superbasics will never exceed the number of nonlinear variables, and in practice will often be much less (in most cases less than a few hundred).
There is not much that a modeler can do in this regard, but it is worth remembering that MINOS works with a dense triangular matrix R of that dimension. (This is used to approximate the reduced Hessian.) Optimization time and memory requirements will be significant if there are more than two or three hundred superbasics.
-------------------------------------------------------------------- Major, Minor itns 1 119 --------------------------------------------------------------------
With linear constraints there is always one major iteration. Each iteration of the reduced-gradient method is called a minor iteration.
-------------------------------------------------------------------- FUNOBJ, FUNCON calls 245 0 --------------------------------------------------------------------
FUNOBJ is the number of times MINOS asked the interpreter to evaluate the objective function and its gradients. FUNCON means the same for the nonlinear constraints. As this model has only linear constraints, the number is zero.
NOTE: If you know that your model has linear constraints but FUNCON turns out to be positive, your nonlinear objective function is being regarded as a nonlinear constraint. You can improve MINOS's efficiency by following some easy rules. Please see "Objective: special treatment of in NLP" in the index for the GAMS User's Guide.
-------------------------------------------------------------------- Superbasics, Norm RG 18 2.18E-08 --------------------------------------------------------------------
The number of superbasic variables in the final solution is reported and also the norm of the reduced gradient (which should be close to zero for an optimal solution).
For models with nonlinear constraints the log is more complicated. CAMCGE is an example of such a model and the screen output looks as follows:
GAMS 2.25.060 (c) Copyright 1992 GAMS Development Corp. All rights reserved
Licensee: Erwin G920429-2010CX-AIX
GAMS
--- Starting compilation
--- camcge.gms(444)
--- Starting execution
--- camcge.gms(435)
--- Generating model CAMCGE
--- camcge.gms(444)
--- 243 rows, 280 columns, and 1356 non-zeroes.
--- Executing MINOS5
Work space allocated -- .36 Mb
Reading data...
Reading nonlinear code...
Major Minor Ninf Sinf,Objective Viol RG NSB Ncon Penalty Step
1 0 1 0.00000000E+00 1.3E+02 0.0E+00 184 3 6.8E-01 1.0E+00
2 40T 30 0.00000000E+00 8.8E+01 7.3E+02 145 4 6.8E-01 1.0E+00
3 40T 30 0.00000000E+00 8.8E+01 1.7E+01 106 5 6.8E-01 1.0E+00
4 40T 30 0.00000000E+00 8.8E+01 2.1E+01 66 6 6.8E-01 1.0E+00
5 40T 25 0.00000000E+00 8.8E+01 1.7E+01 26 7 6.8E-01 1.0E+00
6 29 0 1.91734197E+02 2.6E-03 0.0E+00 0 9 6.8E-01 1.0E+00
7 0 0 1.91734624E+02 2.3E-08 0.0E+00 0 10 1.4E+00 1.0E+00
8 0 0 1.91734624E+02 4.5E-13 0.0E+00 0 11 1.4E+00 1.0E+00
9 0 0 1.91734624E+02 6.8E-13 0.0E+00 0 12 0.0E+00 1.0E+00
EXIT -- OPTIMAL SOLUTION FOUND
Major, Minor itns 9 189
Objective function 1.9173462423688E+02
FUNOBJ, FUNCON calls 8 12
Superbasics, Norm RG 0 0.00E+00
Degenerate steps 0 .00
Norm X, Norm PI 1.37E+03 2.88E+01
Norm X, Norm PI 8.89E+02 7.01E+01 (unscaled)
Constraint violation 6.82E-13 7.66E-16
--- Restarting execution
--- camcge.gms(444)
--- Reading solution for model CAMCGE
--- All done
Note that the iteration log is different from the two cases discussed above. A small section of this log is shown below.
--------------------------------------------------------------------
Major Minor Ninf Sinf,Objective Viol RG NSB Ncon Penalty Step
1 0 1 0.00000000E+00 1.3E+02 0.0E+00 184 3 6.8E-01 1.0E+00
2 40T 30 0.00000000E+00 8.8E+01 7.3E+02 145 4 6.8E-01 1.0E+00
--------------------------------------------------------------------
We see here that we have major and minor iterations. The columns will now be discussed in greater detail.
-------------------------------------------------------------------- Constraint violation 6.82E-13 7.66E-16 --------------------------------------------------------------------
The first number is the largest violation of any of the nonlinear constraints (the final value of Viol). The second second number is the relative violation, Viol/(1.0 + ||x||). It may be more meaningful if the solution vector x is very large.
For an optimal solution, these numbers must be small.
Note: The CAMCGE model (like many CGE models or other almost square systems) can better be solved with the MINOS option START ASSIGNED NONLINEARS BASIC. In the log you see that the algorithm starts out with lots of super basics (corresponding to the non-linear variables). MINOS starts with removing these superbasics, and only then starts working towards an optimal solution.
Thanks to Michael Saunders (Stanford University, author of MINOS) and Arne Drud (ARKI, author of CONOPT) for their contribution.