glpk

GNU Linear Programming Kit (GLPK).

  1. glpk
  2. Usage
  3. Documentation
    1. Problem constructors and predicates
    2. Problem accessors and modifiers
    3. Problem control parameters
    4. Scaling & solver procedures
  4. Examples
  5. About this egg
    1. Author
    2. Version history
    3. License

Usage

(require-extension glpk)

Documentation

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

The Chicken GLPK library 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.

'(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?:: 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))))

About this egg

Author

Ivan Raikov

Version history

1.4
Using assert in unit test
1.3
Documentation converted to wiki format
1.2
Ported to Chicken 4
1.1
Added chicken-glpk.h to file manifest
1.0
Initial release

License

Copyright 2008-2011 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/>.