Description

GNU Linear Programming Kit (GLPK)

Author

Ivan Raikov

Version

Requires

Usage

(require-extension glpk)

Download

glpk.egg

Documentation

GLPK is a package for solving linear programming and mixed integer programming problems.

The Chicken GLPK egg provides a Scheme interface to a large subset of the GLPK procedures for problem setup and solving. Below is a list of procedures that are included in this egg, along with brief descriptions. This egg has been tested with GLPK version 4.28.

Problem constructors and predicates

procedure: lpx:empty-problem:: () -> LPX

This procedure creates a new problem that has no rows or columns.

procedure: lpx:make-problem:: DIR * PBOUNDS * XBOUNDS * OBJCOEFS * CONSTRAINTS * [ORDER] -> LPX

This procedure creates a new problem with the specified parameters.

  • Argument DIR specifies the optimization direction flag. It can be one of 'maximize or 'minimize.
  • Argument PBOUNDS is a list that specifies the type and bounds for each row of the problem object. Each element of this list can take one of the following forms:
    '(unbounded) Free (unbounded) variable, -Inf <= x <= +Inf
    '(lower-bound LB) Variable with lower bound, LB <= x <= +Inf
    '(upper-bound UB) Variable with upper bound, -Inf <= x <= UB
    '(double-bounded LB UB) Double-bounded variable, LB <= x <= UB
    '(fixed LB UB) Fixed variable, LB = x = UB
  • Argument XBOUNDS is a list that specifies the type and bounds for each column (structural variable) of the problem object. Each element of this list can take one of the forms described for parameter PBOUNDS.
  • Argument OBJCOEFS is a list that specifies the objective coefficients for each column (structural variable). This list must be of the same length as XBOUNDS.
  • Argument OBJCOEFS is a list that specifies the objective coefficients for each column (structural variable).
  • Argument CONSTRAINTS is an SRFI-4 f64vector that represents the problem's constraint matrix (in row-major or column-major order).
  • Optional argument ORDER specifies the element order of the constraints matrix. It can be one of 'row-major or 'column-major.
procedure: lpx?:: OBJECT -> BOOL

Returns true if the given object was created by lpx:empty-problem or lpx:make-problem, false otherwise.

Problem accessors and modifiers

procedure: lpx:set-problem-name:: LPX * NAME -> LPX
Sets problem name.
procedure: lpx:get-problem-name:: LPX -> NAME
Returns the name of the given problem.
procedure: lpx:set-direction:: LPX * DIR -> LPX
Specifies the optimization direction flag, which can be one of 'maximize or 'minimize.
procedure: lpx:get-direction:: LPX -> DIR
Returns the optimization direction for the given problem.
procedure: lpx:set-class:: LPX * CLASS -> LPX
Sets problem class (linear programming or mixed-integer programming. Argument CLASS can be one of 'lp or 'mip.
procedure: lpx:get-class:: LPX -> CLASS
Returns the problem class.
procedure: lpx:add-rows:: LPX * N -> LPX
This procedure adds N rows (constraints) to the given problem. Each new row is initially unbounded and has an empty list of constraint coefficients.
procedure: lpx:add-columns:: LPX * N -> LPX
This procedure adds N columns (structural variables) to the given problem.
procedure: lpx:set-row-name:: LPX * I * NAME -> LPX
Sets the name of row I.
procedure: lpx:set-column-name:: LPX * J * NAME -> LPX
Sets the name of column J.
procedure: lpx:get-row-name:: LPX * I -> NAME
Returns the name of row I.
procedure: lpx:get-column-name:: LPX * J -> NAME
Returns the name of column J.
procedure: lpx:get-num-rows:: LPX -> N
Returns the current number of rows in the given problem.
procedure: lpx:get-num-columns:: LPX -> N
Returns the current number of columns in the given problem.
procedure: lpx:set-row-bounds:: LPX * I * BOUNDS -> LPX
Sets bounds for row I in the given problem. Argument BOUNDS specifies the type and bounds for the specified row. It can take one of the following forms:
'(unbounded) Free (unbounded) variable, -Inf <= x <= +Inf
'(lower-bound LB) Variable with lower bound, LB <= x <= +Inf
'(upper-bound UB) Variable with upper bound, -Inf <= x <= UB
'(double-bounded LB UB) Double-bounded variable, LB <= x <= UB
'(fixed LB UB) Fixed variable, LB = x = UB
procedure: lpx:set-column-bounds:: LPX * J * BOUNDS -> LPX
Sets bounds for column J in the given problem. Argument BOUNDS specifies the type and bounds for the specified column. It can take one of the following forms:
'(unbounded) Free (unbounded) variable, -Inf <= x <= +Inf
'(lower-bound LB) Variable with lower bound, LB <= x <= +Inf
'(upper-bound UB) Variable with upper bound, -Inf <= x <= UB
'(double-bounded LB UB) Double-bounded variable, LB <= x <= UB
'(fixed LB UB) Fixed variable, LB = x = UB
procedure: lpx:set-objective-coefficient:: LPX * J * COEF -> LPX
Sets the objective coefficient at column J (structural variable).
procedure: lpx:set-column-kind:: LPX * J * KIND -> LPX
Sets the kind of column J (structural variable). Argument KIND can be one of the following:
'iv integer variable
'cv continuous variable
procedure: lpx:load-constraint-matrix:: LPX * F64VECTOR * NROWS * NCOLS [* ORDER] -> LPX
Loads the constraint matrix for the given problem. The constraints matrix is represented as an SRFI-4 f64vector (in row-major or column-major order). Optional argument ORDER specifies the element order of the constraints matrix. It can be one of 'row-major or 'column-major.
procedure: lpx:get-column-primals:: LPX -> F64VECTOR
Returns the primal values of all structural variables (columns).
procedure: lpx:get-objective-value:: LPX -> NUMBER
Returns the current value of the objective function.

Problem control parameters

The procedures in this section retrieve or set control parameters of GLPK problem object. If a procedure is invoked only with a problem object as an argument, it will return the value of its respective control parameter. If it is invoked with an additional argument, that argument is used to set a new value for the control parameter.

procedure: lpx:message_level:: LPX [ * (none | error | normal | full)] -> LPX | VALUE
Level of messages output by solver routines.
procedure: lpx:scaling:: LPX [ * (none | equilibration | geometric-mean | geometric-mean+equilibration)] -> LPX | VALUE
Scaling option.
procedure: lpx:use_dual_simplex:: LPX [ * BOOL] -> LPX | VALUE
Dual simplex option.
procedure: lpx:pricing:: LPX [ * (textbook | steepest-edge)] -> LPX | VALUE
Pricing option (for both primal and dual simplex).
procedure: lpx:solution_rounding:: LPX [ * BOOL] -> LPX | VALUE
Solution rounding option.
procedure: lpx:iteration_limit:: LPX [ * INT] -> LPX | VALUE
Simplex iteration limit.
procedure: lpx:iteration_count:: LPX [ * INT] -> LPX | VALUE
Simplex iteration count.
procedure: lpx:branching_heuristic:: LPX [ * (first | last | driebeck+tomlin)] -> LPX | VALUE
Branching heuristic option (for MIP only).
procedure: lpx:backtracking_heuristic:: LPX [ * (dfs | bfs | best-projection | best-local-bound)] -> LPX | VALUE
Backtracking heuristic option (for MIP only).
procedure: lpx:use_presolver:: LPX [ * BOOL] -> LPX | VALUE
Use the LP presolver.
procedure: lpx:relaxation:: LPX [ * REAL] -> LPX | VALUE
Relaxation parameter used in the ratio test.
procedure: lpx:time_limit:: LPX [ * REAL] -> LPX | VALUE
Searching time limit, in seconds.

Scaling & solver procedures

procedure: lpx:scale-problem:: LPX -> LPX
This procedure performs scaling of of the constraints matrix in order to improve its numerical properties.
procedure: lpx:simplex:: LPX -> STATUS
This procedure solves the given LP problem using the simplex method. It can return one of the following status codes:
LPX_E_OK the LP problem has been successfully solved
LPX_E_BADB Unable to start the search, because the initial basis specified in the problem object is invalid--the number of basic (auxiliary and structural) variables is not the same as the number of rows in the problem object.
LPX_E_SING Unable to start the search, because the basis matrix corresponding to the initial basis is singular within the working precision.
LPX_E_COND Unable to start the search, because the basis matrix corresponding to the initial basis is ill-conditioned, i.e. its condition number is too large.
LPX_E_BOUND Unable to start the search, because some double-bounded (auxiliary or structural) variables have incorrect bounds.
LPX_E_FAIL The search was prematurely terminated due to the solver failure.
LPX_E_OBJLL The search was prematurely terminated, because the objective function being maximized has reached its lower limit and continues decreasing (the dual simplex only).
LPX_E_OBJUL The search was prematurely terminated, because the objective function being minimized has reached its upper limit and continues increasing (the dual simplex only).
LPX_E_ITLIM The search was prematurely terminated, because the simplex iteration limit has been exceeded.
LPX_E_TMLIM The search was prematurely terminated, because the time limit has been exceeded.
LPX_E_NOPFS The LP problem instance has no primal feasible solution (only if the LP presolver is used).
LPX_E_NODFS The LP problem instance has no dual feasible solution (only if the LP presolver is used).
procedure: lpx:integer:: LPX -> STATUS
Solves an MIP problem using the branch-and-bound method.

Examples

;;
;; Two Mines Linear programming example from
;;
;; http://people.brunel.ac.uk/~mastjjb/jeb/or/basicor.html#twomines
;; 

;; Two Mines Company
;;
;; The Two Mines Company owns two different mines that produce an ore
;; which, after being crushed, is graded into three classes: high,
;; medium and low-grade. The company has contracted to provide a
;; smelting plant with 12 tons of high-grade, 8 tons of medium-grade
;; and 24 tons of low-grade ore per week. The two mines have different
;; operating characteristics as detailed below.
;; 
;; Mine    Cost per day ($'000)    Production (tons/day)                
;;                                High    Medium    Low
;; X       180                     6       3         4
;; Y       160                     1       1         6
;;
;;                                 Production (tons/week)
;;                                High    Medium    Low
;; Contract                       12       8        24
;;
;; How many days per week should each mine be operated to fulfill the
;; smelting plant contract?
;;

(require-extension srfi-4)
(require-extension glpk)

;; (1) Unknown variables
;;
;;      x = number of days per week mine X is operated
;;      y = number of days per week mine Y is operated
;;
;; (2) Constraints
;;
;;
;;    * ore production constraints - balance the amount produced with
;;      the quantity required under the smelting plant contract
;;
;;      High    6x + 1y >= 12
;;      Medium  3x + 1y >= 8
;;      Low     4x + 6y >= 24
;;
;; (3) Objective
;;
;;     The objective is to minimise cost which is given by 180x + 160y.
;;
;;     minimise  180x + 160y
;;     subject to
;;         6x + y >= 12
;;         3x + y >= 8
;;         4x + 6y >= 24
;;         x <= 5
;;         y <= 5
;;         x,y >= 0
;;
;; (4) Auxiliary variables (rows)
;;
;;  p = 6x + y
;;  q = 3x + y
;;  r = 4x + 6y
;;
;;  12 <= p < +inf
;;   8 <= q < +inf
;;  24 <= r < +inf

(define pbounds `((lower-bound 12) (lower-bound 8) (lower-bound 24)))

;; (5) Structural variables (columns)
;;
;;  0 <= x <= 5
;;  0 <= y <= 5

(define xbounds  `((double-bounded 0 5) (double-bounded 0 5)))

;; (6) Objective coefficients: 180, 160

(define objcoefs (list 180 160))


;; Constraints matrix (in row-major order)
;; 
;;   6  1   
;;   3  1   
;;   4  6   

(define constraints (f64vector 6 1 3 1 4 6))

;; Create the problem definition & run the solver
(let ((lpp (lpx:make-problem 'minimize pbounds xbounds objcoefs constraints)))
  (lpx:scale-problem lpp)
  (lpx:use_presolver lpp #t)
  (let ((status (lpx:simplex lpp)))
    (print "solution status = " status)
    (print "objective value = " (lpx:get-objective-value lpp))
    (print "primals = " (lpx:get-column-primals lpp))))

License

Copyright Ivan Raikov and the Okinawa Institute of Science and Technology.

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or (at
your option) any later version.

This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

A full copy of the GPL license can be found at
<http://www.gnu.org/licenses/>.