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. __FORCETOC__ Run-time reporting 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 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 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. Murtagh Bruce A Advanced linear programming : theory and practice McGraw-Hill New York, USA 1981 0-07-044095-6 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 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 . 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 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 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 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 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 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 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 The following functions can be used to collect information directly (and should be used in preference to regexing text files): <tr style="font-weight: bold; background-color: lightgray;;"> API Comment <tr> glp_get_row_prim retrieve row primal value <tr> glp_get_row_dual retrieve row dual value <tr> glp_get_row_stat retrieve row status <tr> glp_get_row_lb retrieve row lower bound <tr> glp_get_row_ub retrieve row upper bound <tr> glp_get_col_prim retrieve column primal value <tr> glp_get_col_dual retrieve column dual value <tr> glp_get_col_stat retrieve column status <tr> glp_get_col_lb retrieve column lower bound <tr> glp_get_col_ub retrieve column upper bound <tr> glp_get_obj_coef retrieve objective coefficient or constant term <tr> lpx_check_kkt calculate KKT optimality conditions and fill LPXKKT C struct The following functions should produce human readable reports: <tr style="font-weight: bold; background-color: lightgray;;"> API Comment <tr> glp_print_ranges print human readable sensitivity analysis report <tr> glp_print_sol print human readable KKT conditions, along with the simplex LP solution <tr> glp_print_ipt print human readable KKT conditions, along with the interior-point LP solution <tr> glp_print_mip print human readable integer feasibility report, along with the MIP solution Adaptive use 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 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.