GLPK/Terminal output

By default, the GLPK library regularly prints to console to indicate progress towards a solution. The exact form of output depends on whether the underlying problem is LP or MIP and, in some cases, which solver method was invoked.

The same terminal output arises from both the GLPSOL utility and from the direct use of the GLPK API. The information on this page should therefore be of equal relevance to modelers using MathProg and to programmers using the GLPK callable library.

Controlling terminal output

GLPK provides modelers and programmers with added control over terminal output.

The terminal output of GLPSOL may be duplicated to a text file with command-line parameter --log. For example:

glpsol --model examples/tsp.mod --log tsp.log

Programmers using the GLPK API can enable and disable terminal output by calling glp_term_out. The hook function glp_term_hook can be used to intercept terminal output. Finer grain output control is also provided but is not covered here — consult the GLPK API manual instead.

Scaling output

Scaling is the process of applying linear transformations to the problem constraint matrix in order to improve its numerical properties. See the GLPK scaling page for technical details.

GLPK may scale a problem before attempting a solution, unless the modeler has explicitly disabled scaling. Conversely, the modeler may direct that scaling must occur and can optionally specify which method or methods to apply. Unfortunately the output to terminal syntax for scaling is not covered in the official documentation.

For instance, calling glp_scale_prob without an explicit method flag on a small MIP problem gave the following terminal output:

Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  8.000e+05  ratio =  8.000e+05
GM: min|aij| =  5.494e-01  max|aij| =  1.820e+00  ratio =  3.312e+00
EQ: min|aij| =  3.096e-01  max|aij| =  1.000e+00  ratio =  3.230e+00

where, in general:

• A indicates the condition of the original constraint matrix, A = (a_ij)
• GM indicates that geometric mean scaling occurred
• EQ indicates that equilibration scaling occurred
• 2N indicates that round scale factors to nearest power of two occurred

Note that the problem is first "unscaled" — meaning that any previous scaling is removed — and then metrics for the original constraint matrix are reported. This is followed by the results of any scaling methods applied in the order of application.

If scaling is not required, you should get the message:

Scaling...
Problem data seem to be well scaled

In the first example, GM and EQ scaling have been applied. The min|aij| and max|aij| indicate the minimum and maximum absolute values of the non-zero elements of A and their ratio is given by simple division.

Scaling is on by default under GLPSOL, but can be explicitly disabled with the --noscale command-line option.

Simplex output

The simplex method output syntax is fully explained in the "Terminal output" subsection of the glp_simplex call documentation in doc/glpk.pdf (for GLPK 4.55 this is section 2.8.1).

For example, the line:

* 1200: obj = 7.860174791e-03 infeas = 2.810e-29 (1)

indicates that due to the asterisk (*) the solver is currently searching for an optimal solution using the primal simplex, 1200 iterations have been completed, the current objective value is 0.00786, the current sum of primal or dual infeasibilities is 2.81×10⁻²⁹ (near zero), and the current number of fixed basic variables is 1.

The asterisk (*) could also be a blank ( ) meaning that the solver is searching for a primal feasible solution using the primal simplex or for a dual feasible solution using the dual simplex. Or a pipe (|) meaning that the solver is searching for an optimal solution using the dual simplex.

Interior-point output

The interior-point output syntax is fully explained in the "Terminal output" subsection of the glp_interior call documentation in doc/glpk.pdf (for GLPK 4.55 this is section 2.9.1).

For example, the line:

19: obj = 5.522746942e+03; rpi = 2.2e-06; rdi = 4.0e-08; gap = 6.7e-03

indicates that 19 iterations have been completed, the current objective value is approximately 5523 (in the case of maximization, the sign is wrong), the current relative primal infeasibility is 0.0000022, the current relative dual infeasibility is 0.00000004, and the current primal-dual gap is 0.0067.

MIP branch-and-cut output

The MIP branch-and-cut output syntax is explained in the "Terminal output" subsection of the glp_intopt call documentation in doc/glpk.pdf (for GLPK 4.55 this is section 2.10.5).

For example, the line:

+ 73068: mip = -5.000000000e-001 <= -2.500000000e-001  50.0% (107; 10024)

indicates that 10024 nodes in the branch-and-bound tree have been rejected and 107 unexplored nodes remain that could lead to an improved MIP solution. The best solution to date is −0.50. There can be no better solution (the LP relaxation) than −0.25, which results in a gap of 50% (not printed for large values). The routine ios_relative_gap computes the relative mip gap as

$gap={\frac {\left|best\_mip-best\_bound\right|}{\left|best\_mip\right|+\epsilon }}$

The number of simplex iterations thus far is 73068. The plus (+) currently has no meaning.

Additional lines of information can occur for the same simplex iteration. This information is currently undocumented.

Numerical instability warnings

If the basic solution is not primal/dual feasible to within tolerance, one of these warning messages will be displayed:

Warning: numerical instability (primal simplex, phase I)
Warning: numerical instability (primal simplex, phase II)
Warning: numerical instability (dual simplex, phase I)
Warning: numerical instability (dual simplex, phase II)

The tolerances are passed to the simplex solver by the structure glp_smcp as fields tol_bnd and tol_dj, both of which default to 1.0e-07. Users are able to modify these tolerances, but should do so only if they fully understand the implications.

These warning are not fatal — rather they indicate that the solver is about to change its solution strategy and can, in may cases, return a satisfactory solution. Further technical details are given in the material on troubleshooting.

Such instabilities may be caused by a poorly scaled model, for instance, when utilizing an excessive value for M under the big M approach. Or when round-off errors during automatic model generation produce close-to-zero coefficients. It is strongly recommended that the underlying cause of poor scaling is tracked down and fixed.

Memory management

The stand-alone solver GLPSOL checks if all memory blocks are released before deleting the environment. If unreleased memory blocks remain, the following error message is issued:

Error: x memory block(s) were lost

This can be an indication of an error from within the GLPK library. Or it may be caused by a client program calling the non-API function glp_main — the use of which is strictly discouraged.