glpk

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.

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

lpx:empty-problem:procedure: This procedure creates a new problem that has no rows or columns.

lpx:make-problem:procedure

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.

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

Problem accessors and modifiers

lpx:set-problem-name:procedure: Sets problem name.

lpx:get-problem-name:procedure: Returns the name of the given problem.

lpx:set-direction:procedure: Specifies the optimization direction flag, which can be one of 'maximize or 'minimize.

lpx:get-direction:procedure: Returns the optimization direction for the given problem.

lpx:set-class:procedure: Sets problem class (linear programming or mixed-integer programming. Argument CLASS can be one of 'lp or 'mip.

lpx:get-class:procedure: Returns the problem class.

lpx:add-rows:procedure: This procedure adds N rows (constraints) to the given problem. Each new row is initially unbounded and has an empty list of constraint coefficients.

lpx:add-columns:procedure: This procedure adds N columns (structural variables) to the given problem.

lpx:set-row-name:procedure: Sets the name of row I.

lpx:set-column-name:procedure: Sets the name of column J.

lpx:get-row-name:procedure: Returns the name of row I.

lpx:get-column-name:procedure: Returns the name of column J.

lpx:get-num-rows:procedure: Returns the current number of rows in the given problem.

lpx:get-num-columns:procedure: Returns the current number of columns in the given problem.

lpx:set-row-bounds:procedure

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`

lpx:set-column-bounds:procedure

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`

lpx:set-objective-coefficient:procedure: Sets the objective coefficient at column J (structural variable).

lpx:set-column-kind:procedure

Sets the kind of column J (structural variable). Argument KIND can be one of the following:

'iv	integer variable
'cv	continuous variable

lpx:load-constraint-matrix:procedure: 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.

lpx:get-column-primals:procedure: Returns the primal values of all structural variables (columns).

lpx:get-objective-value:procedure: 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.

lpx:message_level:procedure: Level of messages output by solver routines.

lpx:scaling:procedure: Scaling option.

lpx:use_dual_simplex:procedure: Dual simplex option.

lpx:pricing:procedure: Pricing option (for both primal and dual simplex).

lpx:solution_rounding:procedure: Solution rounding option.

lpx:iteration_limit:procedure: Simplex iteration limit.

lpx:iteration_count:procedure: Simplex iteration count.

lpx:branching_heuristic:procedure: Branching heuristic option (for MIP only).

lpx:backtracking_heuristic:procedure: Backtracking heuristic option (for MIP only).

lpx:use_presolver:procedure: Use the LP presolver.

lpx:relaxation:procedure: Relaxation parameter used in the ratio test.

lpx:time_limit:procedure: Searching time limit, in seconds.

Scaling & solver procedures

lpx:scale-problem:procedure: This procedure performs scaling of of the constraints matrix in order to improve its numerical properties.

lpx:simplex:procedure

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

lpx:integer:procedure: 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/>.

chickadee » glpk

Identifier search

Outdated egg!

TOC »

Usage

Documentation

Problem constructors and predicates

Problem accessors and modifiers

Problem control parameters

Scaling & solver procedures

Examples

About this egg

Author

Version history

License

Contents »