GLPK/Troubleshooting

This page discusses problems that are occasionally encountered when using GLPK. And, where possible, provides typical GLPK warning messages to aid diagnosis. __FORCETOC__ 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 . 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.