GLPK/Solution information

From Wikibooks, open books for an open world
Jump to: navigation, search

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[edit]

GLPK 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[edit]

There 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[edit]

Assuming 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[edit]

A 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.

Rows
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
Columns
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 \sum a_j x_j. 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[edit]

For 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[edit]

GLPK 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[edit]

The 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 A \mathbf{x} = b the primal variables satisfy the original problem
KKT.PB \mathbf{x} \geq 0 the non-basic variables satisfy the bound constraints
KKT.DE A^\top \pi + \lambda = c  the objective function gradient is a particular linear combination of the constraint plane normals 
KKT.DB \lambda \geq 0 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[edit]

For 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[edit]

The 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[edit]

The 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[edit]

Several 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]

  1. 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.