GLPK/Troubleshooting

This page discusses problems that are occasionally encountered when using GLPK. And, where possible, provides typical GLPK warning messages to aid diagnosis.

Continuous solution to mixed-integer problem

You successfully solve your MIP problem with a call to glp_intopt and then find that the optimal solution is not integer-valued where expected.

Check that you are seeking information with the correct routines. You should use glp_mip_col_val, glp_mip_row_val, and glp_mip_obj_val to recover the MIP solution. In contrast, the routines glp_get_col_prim and glp_get_row_prim return the solution to the LP relaxation.

MPS formats and OBJSENSE

Strange as it may seem, the specification for the MPS linear program problem format does not contain a specifier for the objective sense. Neither is there a standard default — be it minimize or maximize. But GLPK assumes the objective is minimization in the case of MPS files. Some solvers accept the non-standard OBJSENSE specifier as an extension to the MPS specification, but GLPK silently ignores this keyword.

If using GLPSOL, the objective sense can be set on the command-line via --min or --max. Strictly speaking though, the use of --min is redundant. If you do not wish to use --max then you can multiply your objective function coefficients by −1. The solution will be correctly reported but the objective value will retain the wrong sign.

If your objective value is zero and you were expecting something else, then you may be inadvertently deploying the wrong objective sense.

Objective shift term ignored when exported

The constant term in an objective function is called the "shift" term in GLPK. If you run your model under GLPK, this term is taken into account. But if you export your model to the CPLEX LP and MPS formats, this term is not transferred. This will result in the variable values being correct but the objective value will differ by the "shift" term.

In the following model the constant term of the objective is 5.

var x, >=0; 
minimize obj : x + 5;

This file can be exported to the CPLEX format with

glpsol -m test.mod --wlp test.lp --check

The console output includes a warning

glp_mpl_build_prob: row obj; constant term 5 ignored

The exported file contains a comment with the constant term.

\* Problem: test *\

Minimize
 obj: + x
\* constant term = 5 *\

Subject To

End

To circumvent the problem an additional variable and constraint can be introduced [1].

var x, >=0; 
var v_dummy;
s.t. c_dummy : v_dummy = x + 5;
minimize obj : v_dummy;

Insufficient memory

Memory, rather than processing power, can be the system constraint for some optimization problems. If GLPK cannot get a request for RAM memory serviced by the operating system, it should report (and then fail):

umalloc: size = 166550392; no memory available

This message means that a GLPK routine attempted to gain a memory block of 166.6 Mb from the system, but the attempt failed — that is, a system call to malloc returned NULL. This means that you have insufficient RAM for your problem (or that memory is leaking from some process, but not likely from GLPK).

Moreover, if GLPK terminates abnormally because of insufficient memory, it always prints a message to standard out. If no message appears, the abnormal termination is not caused by GLPK (bugs in GLPK notwithstanding).

The following thread discusses the use of memory by GLPK and may provide a useful starting point for some calculations on memory consumption.

Some background

The glp_prob problem object, at the API level, requires additional memory to store auxiliary information for use by various GLPK routines. For example, one constraint matrix element (of type double) stored in a glp_prob object requires 32 bytes (on a 32-bit platform) rather than 8 bytes. Thus, an LP instance being stored in a glp_prob object takes about four times more memory than if it were represented by a set of plain arrays, and about ten times more memory when the LP preprocessor has been deployed.

Job splitting with GLPSOL

To reduce the memory requirement when using GLPSOL, you can split the job as follows:

Translate the model and write it to foo.glp:

glpsol --model foo.mod --data foo.dat --check --wglp foo.glp

Solve the translated model and write its solution to foo.sol:

glpsol --glp foo.glp --write foo.sol

Process the model using the previously found solution:

glpsol --model foo.mod --data foo.dat --read foo.sol

Note also that the data file foo.dat is optional and that foo.mod and foo.dat (if present) must remain unchanged between steps one and three.

Using memory judiciously with APIs

LP problems are normally built using sparse matrices. The most commonly used problem build API calls are glp_set_mat_row, glp_set_mat_col, and glp_load_matrix. To minimize memory consumption:

• only copy in non-zero values
• delete temporary arrays and vectors after use

The following example utilizes the Java wrapper to GLPK — rather than the native C language interface:

ind = GLPK.new_intArray(3);
GLPK.intArray_setitem(ind, 1, 1);
GLPK.intArray_setitem(ind, 2, 2);
val = GLPK.new_doubleArray(3);
GLPK.doubleArray_setitem(val, 1, 1.);
GLPK.doubleArray_setitem(val, 2, -1.);
GLPK.glp_set_mat_row(lp, 1, 2, ind, val);
GLPK.delete_doubleArray(val);
GLPK.delete_intArray(ind);

Adding physical memory

The other strategy is, of course, to increase your system memory. Adding DRAM is clearly the best option. The alternative is to check your swap partition and increase it to 8 × your DRAM capacity and/or migrate to a solid state drive.

Numerical instability

One user reports occasionally encountering the following console message when solving millions of tiny automatically generated LPs using the GLPK API:

Warning: numerical instability (primal simplex, phase II)

This means that the simplex solver detected that the current basic solution has became infeasible due to excessive round-off errors. In this case, the solver automatically switches to phase I to recover feasibility and then continues the search. If the solver routine returns 0, the solution can be considered accurate to within the current working precision. The GLPK routine lpx_check_kkt can subsequently be used to check whether the solution satisfies the various conditions for feasibility and optimality, as described here and here. See this thread for more information.

Provisionally from GLPK 4.46 onward, a more robust strategy for dealing with numerical instability is planned. This new version will mean that these instability warnings will no longer occur. See this April 2011 posting for some details.

Interior point solver

Users should be aware that the interior point solver sometimes prematurely terminates its search for a solution due to numerical instabilities when solving a Newtonian system. In which case, the more robust simplex solver should be used. This 2011 posting contains more details.

Slow models

Sometimes a modeler will create a problem that is hard to solve. This is more likely with pure (IP) and mixed-integer (MIP) models than with strictly linear (LP) models. On the other hand, the branch and bound method used by GLPK can be run in different ways and switching to another variant may yield a success.

Most of these variants can be accessed through GLPSOL using its command-line options. The API, not surprisingly, offers greater flexibility. As an example, switching from the default GLPSOL options to --gomory—pcost for a glass manufacturing model produced a solution in 2 minutes, for a model that was otherwise painfully slow.

Alternatively, a model may be able to be reformulated to improve its tractability or reduce its size.

The last option is to try another solver. It could be that your class of problem would better fit a specialist solver. Finally, the high-profile commercial solvers are generally acknowledged to be faster and more robust than their free software counterparts.

Constraint programming problems

MIP solvers usually perform poorly on constraint programming problems. GLPK is no exception.

If your instance is pure 0–1 and the constraint coefficients are integer, try the MiniSat solver. This specialist solver is supported by GLPSOL and is also available through the GLPK APIs. MiniSat itself is described here.

Invoke the --minisat option if using GLPSOL, in which case GLPK transforms your instance to a satisfiability problem and solves this with the minisat solver. Details are given in the GLPK reference manuals. An example model — the "paint-by-numbers" puzzle — can be found in the subdirectory glpk/examples/pbn. You can use the --objbnd option in addition to identify better integer-feasible solutions. The bound argument on this option introduces an additional inequality constraint on the objective. Check the --help message for usage details.

One user reports that a problem that took 15 hours conventionally, was solved "almost instantaneously" with the MiniSat solver.

Hyperthreading hardware

Somewhat paradoxically, powerful multicore hyperthreading hardware may result in degraded performance by GLPK. HyperThreading may be able to be disabled by changing your BIOS settings. Indeed, this might double your speed. See this posting from early 2013 for more information.

Solution ordering

Use the following command if you need a quick listing of the rows and columns in the order that GLPSOL would process them:

glpsol --output quick.out --tmlim 1

System time synchronization bug

Prior to version 4.47, a GLPK assert would fails whenever the system clock was read twice and the newly read timestamp was less than the previously read timestamp — a situation that can occur when the operating system synchronizes with an NTP server during a GLPK run. See here for the original bug report and here for some more traffic on the topic. This bug is now fixed from version 4.47 onwards.

Database and spreadsheet issues

Please see the ODBC page.

Compile-time issues

Some troubleshooting hints are given here.

Precompiled binaries

Make sure you use the 64-bit binary on 64-bit systems and the 32-bit binary on 32-bit systems. This seems to be more of a problem with Windows users.