M L
GNU Linear Programming Kit
Reference Manual
for GLPK Version 4.58
(DRAFT, February 2016)
J K
The GLPK package is part of the GNU Project released under the aegis of GNU.
Copyright
c
2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2013, 2014,
2015, 2016 Andrew Makhorin, Department for Applied Informatics, Moscow Aviation Institute,
Moscow, Russia. All rights reserved.
Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
Permission is granted to make and distribute verbatim copies of this manual provided the copyright
notice and this permission notice are preserved on all copies.
Permission is granted to copy and distribute modified versions of this manual under the conditions
for verbatim copying, provided also that the entire resulting derived work is distributed under the
terms of a permission notice identical to this one.
Permission is granted to copy and distribute translations of this manual into another language,
under the above conditions for modified versions.
2
Contents
1 Intro duction 9
1.1 LP problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 MIP problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Using the package . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1 Brief example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.2 Compiling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3.3 Linking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Basic API Routines 14
2.1 General conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.1 Library header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.2 Error handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.3 Thread safety . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.4 Array indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Problem object . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.1 Problem segment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.2 Basis segment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.3 Interior-p oint segment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.4 MIP segment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Problem creating and modifying routines . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1 glp create prob — create problem object . . . . . . . . . . . . . . . . . . . . . 18
2.3.2 glp set prob name — assign (change) problem name . . . . . . . . . . . . . . 18
2.3.3 glp set obj name — assign (change) objective function name . . . . . . . . . 18
2.3.4 glp set obj dir — set (change) optimization direction flag . . . . . . . . . . . 19
2.3.5 glp add rows — add new rows to problem object . . . . . . . . . . . . . . . . 19
2.3.6 glp add cols — add new columns to problem object . . . . . . . . . . . . . . 19
2.3.7 glp set row name — assign (change) row name . . . . . . . . . . . . . . . . . 20
2.3.8 glp set col name — assign (change) column name . . . . . . . . . . . . . . . . 20
2.3.9 glp set row bnds — set (change) row bounds . . . . . . . . . . . . . . . . . . 20
2.3.10 glp set col bnds — set (change) column bounds . . . . . . . . . . . . . . . . . 21
2.3.11 glp set obj coef — set (change) objective coefficient or constant term . . . . . 21
2.3.12 glp set mat row — set (replace) row of the constraint matrix . . . . . . . . . 22
2.3.13 glp set mat col — set (replace) column of the constraint matrix . . . . . . . . 22
2.3.14 glp load matrix — load (replace) the whole constraint matrix . . . . . . . . . 23
2.3.15 glp check dup — check for duplicate elements in sparse matrix . . . . . . . . 23
2.3.16 glp sort matrix — sort elements of the constraint matrix . . . . . . . . . . . 24
2.3.17 glp del rows — delete rows from problem object . . . . . . . . . . . . . . . . 24
3
2.3.18 glp del cols — delete columns from problem object . . . . . . . . . . . . . . . 24
2.3.19 glp copy prob — copy problem object content . . . . . . . . . . . . . . . . . . 25
2.3.20 glp erase prob — erase problem object content . . . . . . . . . . . . . . . . . 25
2.3.21 glp delete prob — delete problem object . . . . . . . . . . . . . . . . . . . . . 25
2.4 Problem retrieving routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.1 glp get prob name — retrieve problem name . . . . . . . . . . . . . . . . . . 26
2.4.2 glp get obj name — retrieve objective function name . . . . . . . . . . . . . . 26
2.4.3 glp get obj dir — retrieve optimization direction flag . . . . . . . . . . . . . . 26
2.4.4 glp get num rows — retrieve number of rows . . . . . . . . . . . . . . . . . . 26
2.4.5 glp get num cols — retrieve number of columns . . . . . . . . . . . . . . . . . 27
2.4.6 glp get row name — retrieve row name . . . . . . . . . . . . . . . . . . . . . 27
2.4.7 glp get col name — retrieve column name . . . . . . . . . . . . . . . . . . . . 27
2.4.8 glp get row type — retrieve row type . . . . . . . . . . . . . . . . . . . . . . 27
2.4.9 glp get row lb — retrieve row lower bound . . . . . . . . . . . . . . . . . . . 28
2.4.10 glp get row ub — retrieve row upper bound . . . . . . . . . . . . . . . . . . . 28
2.4.11 glp get col type — retrieve column type . . . . . . . . . . . . . . . . . . . . . 28
2.4.12 glp get col lb — retrieve column lower bound . . . . . . . . . . . . . . . . . . 28
2.4.13 glp get col ub — retrieve column upper bound . . . . . . . . . . . . . . . . . 29
2.4.14 glp get obj coef — retrieve objective coefficient or constant term . . . . . . . 29
2.4.15 glp get num nz — retrieve number of constraint coefficients . . . . . . . . . . 29
2.4.16 glp get mat row — retrieve row of the constraint matrix . . . . . . . . . . . . 29
2.4.17 glp get mat col — retrieve column of the constraint matrix . . . . . . . . . . 30
2.5 Row and column searching routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.5.1 glp create index — create the name index . . . . . . . . . . . . . . . . . . . . 31
2.5.2 glp find row — find row by its name . . . . . . . . . . . . . . . . . . . . . . . 32
2.5.3 glp find col — find column by its name . . . . . . . . . . . . . . . . . . . . . 32
2.5.4 glp delete index — delete the name index . . . . . . . . . . . . . . . . . . . . 32
2.6 Problem scaling routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.6.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.6.2 glp set rii — set (change) row scale factor . . . . . . . . . . . . . . . . . . . . 33
2.6.3 glp set sjj — set (change) column scale factor . . . . . . . . . . . . . . . . . . 33
2.6.4 glp get rii — retrieve row scale factor . . . . . . . . . . . . . . . . . . . . . . 34
2.6.5 glp get sjj — retrieve column scale factor . . . . . . . . . . . . . . . . . . . . 34
2.6.6 glp scale prob — scale problem data . . . . . . . . . . . . . . . . . . . . . . . 34
2.6.7 glp unscale prob — unscale problem data . . . . . . . . . . . . . . . . . . . . 34
2.7 LP basis constructing routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.7.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.7.2 glp set row stat — set (change) row status . . . . . . . . . . . . . . . . . . . 35
2.7.3 glp set col stat — set (change) column status . . . . . . . . . . . . . . . . . . 36
2.7.4 glp std basis — construct standard initial LP basis . . . . . . . . . . . . . . . 36
2.7.5 glp adv basis — construct advanced initial LP basis . . . . . . . . . . . . . . 36
2.7.6 glp cpx basis — construct Bixby’s initial LP basis . . . . . . . . . . . . . . . 37
2.8 Simplex method routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.8.1 glp simplex — solve LP problem with the primal or dual simplex method . . 39
2.8.2 glp exact — solve LP problem in exact arithmetic . . . . . . . . . . . . . . . 45
2.8.3 glp init smcp — initialize simplex solver control parameters . . . . . . . . . . 46
2.8.4 glp get status — determine generic status of basic solution . . . . . . . . . . 46
2.8.5 glp get prim stat — retrieve status of primal basic solution . . . . . . . . . . 46
4
2.8.6 glp get dual stat — retrieve status of dual basic solution . . . . . . . . . . . . 47
2.8.7 glp get obj val — retrieve objective value . . . . . . . . . . . . . . . . . . . . 47
2.8.8 glp get row stat — retrieve row status . . . . . . . . . . . . . . . . . . . . . . 47
2.8.9 glp get row prim — retrieve row primal value . . . . . . . . . . . . . . . . . . 47
2.8.10 glp get row dual — retrieve row dual value . . . . . . . . . . . . . . . . . . . 48
2.8.11 glp get col stat — retrieve column status . . . . . . . . . . . . . . . . . . . . 48
2.8.12 glp get col prim — retrieve column primal value . . . . . . . . . . . . . . . . 48
2.8.13 glp get col dual — retrieve column dual value . . . . . . . . . . . . . . . . . . 48
2.8.14 glp get unbnd ray — determine variable causing unboundedness . . . . . . . 49
2.9 Interior-p oint method routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.9.1 glp interior — solve LP problem with the interior-point method . . . . . . . . 51
2.9.2 glp init iptcp — initialize interior-point solver control parameters . . . . . . . 55
2.9.3 glp ipt status — determine solution status . . . . . . . . . . . . . . . . . . . . 55
2.9.4 glp ipt obj val — retrieve objective value . . . . . . . . . . . . . . . . . . . . 55
2.9.5 glp ipt row prim — retrieve row primal value . . . . . . . . . . . . . . . . . . 55
2.9.6 glp ipt row dual — retrieve row dual value . . . . . . . . . . . . . . . . . . . 56
2.9.7 glp ipt col prim — retrieve column primal value . . . . . . . . . . . . . . . . 56
2.9.8 glp ipt col dual — retrieve column dual value . . . . . . . . . . . . . . . . . . 56
2.10 Mixed integer programming routines . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.10.1 glp set col kind — set (change) column kind . . . . . . . . . . . . . . . . . . 57
2.10.2 glp get col kind — retrieve column kind . . . . . . . . . . . . . . . . . . . . . 57
2.10.3 glp get num int — retrieve number of integer columns . . . . . . . . . . . . . 57
2.10.4 glp get num bin — retrieve number of binary columns . . . . . . . . . . . . . 58
2.10.5 glp intopt — solve MIP problem with the branch-and-cut method . . . . . . 58
2.10.6 glp init iocp — initialize integer optimizer control parameters . . . . . . . . . 63
2.10.7 glp mip status — determine status of MIP solution . . . . . . . . . . . . . . . 63
2.10.8 glp mip obj val — retrieve objective value . . . . . . . . . . . . . . . . . . . . 63
2.10.9 glp mip row val — retrieve row value . . . . . . . . . . . . . . . . . . . . . . 64
2.10.10 glp mip col val — retrieve column value . . . . . . . . . . . . . . . . . . . . . 64
2.11 Additional routines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
2.11.1 glp check kkt — check feasibility/optimality conditions . . . . . . . . . . . . 65
3 Utility API routines 69
3.1 Problem data reading/writing routines . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.1.1 glp read mps — read problem data in MPS format . . . . . . . . . . . . . . . 69
3.1.2 glp write mps — write problem data in MPS format . . . . . . . . . . . . . . 70
3.1.3 glp read lp — read problem data in CPLEX LP format . . . . . . . . . . . . 70
3.1.4 glp write lp — write problem data in CPLEX LP format . . . . . . . . . . . 71
3.1.5 glp read prob — read problem data in GLPK format . . . . . . . . . . . . . . 71
3.1.6 glp write prob — write problem data in GLPK format . . . . . . . . . . . . . 76
3.2 Routines for processing MathProg models . . . . . . . . . . . . . . . . . . . . . . . . 77
3.2.1 Intro duction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.2.2 glp mpl alloc wksp — allocate the translator workspace . . . . . . . . . . . . 80
3.2.3 glp mpl init rand — initialize pseudo-random number generator . . . . . . . 80
3.2.4 glp mpl read model — read and translate model section . . . . . . . . . . . . 80
3.2.5 glp mpl read data — read and translate data section . . . . . . . . . . . . . . 81
3.2.6 glp mpl generate — generate the model . . . . . . . . . . . . . . . . . . . . . 81
3.2.7 glp mpl build prob — build problem instance from the model . . . . . . . . . 81
5
