Outdated egg!

This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for the CHICKEN 5 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

glpk

GNU Linear Programming Kit (GLPK).

Outdated egg!
glpk
Usage
Documentation
Examples
About this egg

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.

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))))

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

Outdated egg!

glpk

Usage