GLPK/Solution information
This page explains how to recover and interpret solution information from GLPK. The information presented here should be relevant to both modelers using GLPSOL and programmers using the callable library APIs.
You must have made an attempt to solve your problem before the material on this page will apply — but the GLPK solution process need not have produced a usable answer. Answer or no, there are many reasons for seeking extra information about the solution process and/or solution.
Run-time reporting
editGLPK will normally print information during the solution process — the details of which can be found on the terminal output page.
Failure to solve to optimality
editThere are several reasons (software faults aside) as to why GLPK may fail to reach an optimal solution:
- the problem is empty and the solver returns
- the solver proves that the problem is unbounded and returns
- the solver proves that the problem is nonfeasible and returns
- the solver is unable to find a starting feasible solution within the allocated time or available memory
- the solver is unable to find an optimal solution within the allocated time or available memory
- the solver encounters numerical instability problems
Not all of these conditions are relevant to each of the { simplex, interior-point } × { LP, MIP } combinations, but this outline does give an indication of the kind of issues that can arise. The troubleshooting page offers some suggestions and fixes. Numerical instability warnings, in particular, may result from poor scaling. If you encounter a really puzzling problem and think it a bug in GLPK, please report the issue so it can be addressed.
If programming with GLPK, bear in mind that the solver, paradoxically perhaps, need not have found a solution to return success — it only needs to have completed its assigned tasks satisfactorily.
Solution recovery
editAssuming that GLPK provides an optimal solution, there are several methods for recovering the solution information using both standard calls and tailored methods. Some techniques may also accept and process non-optimal feasible solutions.
The MathProg language allows for tight control over the output of solution information. The language now supports suffixes for constraints and variables (but not parameters) — a feature that can be useful when seeking, for example, dual values. The section on close-to-zero rounding shows how to use a MathProg conditional to output true zeros instead of very small numbers.
GLPSOL offers the options --output and --write for obtaining solution information in human readable and machine parsible formats, respectively. Both may be used in the one command:
glpsol ... --output file.out --write file.wri
These two output formats are presented on the interoperability page. Terminal output can also be duplicated to a text file with the GLPSOL command-line option --log file.log. Conversely, the special filename /dev/stdout can be used to write "files" to the terminal instead of to a regular file. And both tactics can be used together.
The output produced by glp_print_sol is similar to that used by the IBM MPS/360 linear programming package, but altered a little, because GLPK uses auxiliary rather than slack/surplus variables. [1]
The various GLPK API calls that can be used to recover information are listed below. Elsewhere, the relevant function names are given to aid cross-referencing back to the GLPK API manual, where comprehensive technical descriptions can usually be found.
Sensitivity analysis report
editA problem solved to optimality with the simplex solver can be further subject to a sensitivity analysis. This feature is not available to solutions generated by the interior-point solver or for mixed-integer problems. The glp_print_ranges API call produces a sensitivity report in human readable format.
The GLPSOL --ranges option also produces this report (or issues a suitable warning if its use is inappropriate):
glpsol ... --ranges file.sen
The output produced by glp_print_ranges is identical to that used by the IBM MPS/360 linear programming package (see Murtagh 1981).
The description here is intentionally brief — details can be found in the official GLPK API manual, including an explanation of break points and objective coefficient sensitivities. The two following tables can be used to read a sensitivity analysis report.
| Header | Values | Comment |
|---|---|---|
| No | ordinal number of row, 1 … n | |
| Row name | symbolic name (blank if none) | |
| St | row status | |
| BS | constraint inactive | |
| NL | inequality constraint with lower RHS active | |
| NU | inequality constraint with upper RHS active | |
| NS | equality constraint active | |
| NF | free row active | |
| Activity | (primal) value of auxiliary variable | |
| Slack | (primal) value of slack variable | |
| Marginal | reduced cost (dual activity) of auxiliary variable | |
| Lower bound | lower bound of RHS (-Inf if open) | |
| Upper bound | upper bound of RHS (+Inf if open) | |
| Obj coeff range | range of objective coefficients related to row | |
| Obj value | objective value | |
| Limiting variable | name of limiting variable |
| Header | Values | Comment |
|---|---|---|
| No | ordinal number of column, 1 … m | |
| Column name | symbolic name (blank if none) | |
| St | column status | |
| BS | basic column | |
| NL | non-basic column with lower bound active | |
| NU | non-basic column with upper bound active | |
| NS | non-basic fixed column | |
| NF | non-basic free (unbounded) column | |
| Activity | (primal) value of structural variable | |
| Obj coeff | objective coefficient for structural variable | |
| Marginal | reduced cost (dual activity) of structural variable | |
| Lower bound | lower bound on structural variable (-Inf if open) | |
| Upper bound | upper bound on structural variable (+Inf if open) | |
| Obj value | objective value | |
| Limiting variable | name of limiting variable |
Abbreviations: RHS means right-hand side. Inf means infinity.
The official documentation (GLPK 4.45) explains that analysis of a row is the analysis of its auxiliary variable, which is equal to the row linear form . And the analysis of a column is the analysis of its corresponding structural variable. Formally, there is no innate difference between rows and columns when performing a sensitivity analysis.
Karush-Kuhn-Tucker optimality conditions
editFor pure linear programs (excluding mixed-integer programs), the Karush-Kuhn-Tucker optimality conditions are necessary and sufficient for the given solution to be a global optimum (assuming that some regularity conditions are also met). These KKT conditions are listed here as they apply to GLPK. Numerical solvers also use these KKT conditions to estimate the accuracy of their floating point calculations upon completion. GLPK can provide on request, a human readable report giving, among other things, the KKT conditions for any solution obtained using either the simplex or interior-point solvers.
KKT calculation
editGLPK provides the lpx_check_kkt routine to calculate and interpret the KKT optimality conditions for the current basic solution. This call fills a C struct LPXKKT instance, from which specific information can be recovered. Its use is documented in the official GLPK API manual and the call itself is also described in this wikibook.
KKT report
editThe GLPK glp_print_sol and glp_print_ipt calls print a report which contains both the solution and the KKT optimality conditions for that solution. The GLPSOL --output option also displays the same information for pure LP (non-MIP) problems (usage is not restricted).
glpsol ... --output file.out
The KKT conditions are most often used to estimate the effects of inaccurate floating point arithmetic on the quality of the reported solution (assuming that exact arithmetic has not been deployed). The description given here is intentionally brief — consult the official GLPK API manual for details. There are four reported tests, labeled KKT.PE thru KKT.DB. A typical report is shown — which is clean in this case!
KKT.PE: max.abs.err = 0.00e+00 on row 0
max.rel.err = 0.00e+00 on row 0
High quality
KKT.PB: max.abs.err = 0.00e+00 on row 0
max.rel.err = 0.00e+00 on row 0
High quality
KKT.DE: max.abs.err = 0.00e+00 on column 0
max.rel.err = 0.00e+00 on column 0
High quality
KKT.DB: max.abs.err = 0.00e+00 on row 0
max.rel.err = 0.00e+00 on row 0
High quality
The following three tables can be used to read a KKT report. The mathematical expressions given in the first table are described in detail here.
| Requirement | Mathematically | Interpretation |
|---|---|---|
| KKT.PE | the primal variables satisfy the original problem | |
| KKT.PB | the non-basic variables satisfy the bound constraints | |
| KKT.DE | the objective function gradient is a particular linear combination of the constraint plane normals | |
| KKT.DB | the original constraints prevent the solution from being "moved" along the objective function gradient |
| Attribute | Explanation |
|---|---|
| max.abs.err | maximum absolute error |
| max.rel.err | maximum relative error |
| Quality | Char | Explanation |
|---|---|---|
| High quality | H | high quality |
| Medium quality | M | medium quality |
| Low quality | L | low quality |
| various reports | ? | primal or dual solution is wrong or infeasible |
The char column above refers to the character values contained int the GLPK LPXKKT C-struct.
Interpretation
editFor a given problem, with scaling if operative, the GLPK 4.45 API manual states that "if all the indicators show high or medium quality … the user can be sure that the obtained basic solution is quite accurate."
Integer feasibility report
editThe first two KKT conditions KKT.PE and KKT.PB can also be calculated for the solution to a mixed-integer program and used to investigate the numerical accuracy of the resulting solution. These two tests alone do not guarantee optimality, but the solver will know if the branch-and-bound tree has been exhausted or not. See the preceding section for details.
The GLPK glp_print_mip call prints a report which contains both the solution and the integer feasibility conditions for that solution The GLPSOL --output option can be used to display this information for MIP problems (usage is not restricted).
glpsol ... --output file.out
Note too the GLPSOL option --nomip which allows an MIP problem to be solved as a pure LP by removing the integer restrictions.
Informational APIs
editThe following functions can be used to collect information directly (and should be used in preference to regexing text files):
| API | Comment |
| glp_get_row_prim | retrieve row primal value |
| glp_get_row_dual | retrieve row dual value |
| glp_get_row_stat | retrieve row status |
| glp_get_row_lb | retrieve row lower bound |
| glp_get_row_ub | retrieve row upper bound |
| glp_get_col_prim | retrieve column primal value |
| glp_get_col_dual | retrieve column dual value |
| glp_get_col_stat | retrieve column status |
| glp_get_col_lb | retrieve column lower bound |
| glp_get_col_ub | retrieve column upper bound |
| glp_get_obj_coef | retrieve objective coefficient or constant term |
| lpx_check_kkt | calculate KKT optimality conditions and fill LPXKKT C struct |
The following functions should produce human readable reports:
| API | Comment |
| glp_print_ranges | print human readable sensitivity analysis report |
| glp_print_sol | print human readable KKT conditions, along with the simplex LP solution |
| glp_print_ipt | print human readable KKT conditions, along with the interior-point LP solution |
| glp_print_mip | print human readable integer feasibility report, along with the MIP solution |
Adaptive use
editSeveral innovative projects use GLPK solution information in an adaptive context. Results from one run are used to generate the next model, and so on, until some predetermined condition is reached.
Note: more details needed.
References
edit- ↑ Murtagh, Bruce A (1981). Advanced linear programming : theory and practice. New York, USA: McGraw-Hill. ISBN 0-07-044095-6.
Request: if anyone develops some scripting to parse the human readable reports, can they either add it to this page or post it to the [help-glpk] list for inclusion here.