((section 2 "Outdated egg!" (p "This is an egg for CHICKEN 4, the unsupported old release.  You're almost certainly looking for " (int-link "/eggref/5/glpk" "the CHICKEN 5 version of this egg") ", if it exists.") (p "If it does not exist, there may be equivalent functionality provided by another egg; have a look at the " (link "https://wiki.call-cc.org/chicken-projects/egg-index-5.html" "egg index") ". Otherwise, please consider porting this egg to the current version of CHICKEN.") (tags "egg")) (section 2 "glpk" (p "GNU Linear Programming Kit (GLPK).") (toc)) (section 2 "Usage" (p "(require-extension glpk)")) (section 2 "Documentation" (p (link "http://www.gnu.org/software/glpk/" "GLPK") " is a package for solving linear programming and mixed integer programming problems.") (p "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.") (section 3 "Problem constructors and predicates" (def (sig (procedure "lpx:empty-problem:: () -> LPX" (id lpx:empty-problem))) (p "This procedure creates a new problem that has no rows or columns.")) (def (sig (procedure "lpx:make-problem:: DIR * PBOUNDS * XBOUNDS * OBJCOEFS * CONSTRAINTS * [ORDER] -> LPX" (id lpx:make-problem))) (p "This procedure creates a new problem with the specified parameters.") (ul (li "Argument " (tt "DIR") " specifies the optimization direction flag. It can be one of " (tt "'maximize") " or  " (tt "'minimize") ". ") (li "Argument " (tt "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: ")) (table (@ (class "symbol-table")) (tr (td "'(unbounded)") (td "Free (unbounded) variable, " (tt "-Inf <= x <= +Inf"))) "\n" (tr (td "'(lower-bound LB)") (td "Variable with lower bound, " (tt "LB <= x <= +Inf"))) "\n" (tr (td "'(upper-bound UB)") (td "Variable with upper bound, " (tt "-Inf <= x <= UB"))) "\n" (tr (td "'(double-bounded LB UB)") (td "Double-bounded variable, " (tt "LB <= x <= UB"))) "\n" (tr (td "'(fixed LB UB)") (td "Fixed variable, " (tt "LB = x = UB")))) (ul (li "Argument " (tt "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 " (tt "PBOUNDS") ". ") (li "Argument " (tt "OBJCOEFS") " is a list that specifies the objective coefficients for each column (structural variable). This list must be of the same length as " (tt "XBOUNDS") ". ") (li "Argument " (tt "OBJCOEFS") " is a list that specifies the objective coefficients for each column (structural variable). ") (li "Argument " (tt "CONSTRAINTS") " is an SRFI-4 " (tt "f64vector") " that represents the problem's constraint matrix (in row-major or column-major order). ") (li "Optional argument " (tt "ORDER") " specifies the element order of the constraints matrix. It can be one of " (tt "'row-major") " or " (tt "'column-major") ". "))) (def (sig (procedure "lpx?:: OBJECT -> BOOL" (id lpx?))) (p "Returns true if the given object was created by " (tt "lpx:empty-problem") " or " (tt "lpx:make-problem") ", false otherwise."))) (section 3 "Problem accessors and modifiers" (def (sig (procedure "lpx:set-problem-name:: LPX * NAME -> LPX" (id lpx:set-problem-name))) (p "Sets problem name.")) (def (sig (procedure "lpx:get-problem-name:: LPX -> NAME" (id lpx:get-problem-name))) (p "Returns the name of the given problem.")) (def (sig (procedure "lpx:set-direction:: LPX * DIR -> LPX" (id lpx:set-direction))) (p "Specifies the optimization direction flag, which can be one of " (tt "'maximize") " or  " (tt "'minimize") ".")) (def (sig (procedure "lpx:get-direction:: LPX -> DIR" (id lpx:get-direction))) (p "Returns the optimization direction for the given problem.")) (def (sig (procedure "lpx:set-class:: LPX * CLASS -> LPX" (id lpx:set-class))) (p "Sets problem class (linear programming or mixed-integer programming. Argument " (tt "CLASS") " can be one of " (tt "'lp") " or " (tt "'mip") ".")) (def (sig (procedure "lpx:get-class:: LPX -> CLASS" (id lpx:get-class))) (p "Returns the problem class.")) (def (sig (procedure "lpx:add-rows:: LPX * N -> LPX" (id lpx:add-rows))) (p "This procedure adds " (tt "N") " rows (constraints) to the given problem. Each new row is initially unbounded and has an empty list of constraint coefficients.")) (def (sig (procedure "lpx:add-columns:: LPX * N -> LPX" (id lpx:add-columns))) (p "This procedure adds " (tt "N") " columns (structural variables) to the given problem.")) (def (sig (procedure "lpx:set-row-name:: LPX * I * NAME -> LPX" (id lpx:set-row-name))) (p "Sets the name of row " (tt "I") ".")) (def (sig (procedure "lpx:set-column-name:: LPX * J * NAME -> LPX" (id lpx:set-column-name))) (p "Sets the name of column " (tt "J") ".")) (def (sig (procedure "lpx:get-row-name:: LPX * I -> NAME" (id lpx:get-row-name))) (p "Returns the name of row " (tt "I") ".")) (def (sig (procedure "lpx:get-column-name:: LPX * J -> NAME" (id lpx:get-column-name))) (p "Returns the name of column " (tt "J") ".")) (def (sig (procedure "lpx:get-num-rows:: LPX -> N" (id lpx:get-num-rows))) (p "Returns the current number of rows in the given problem.")) (def (sig (procedure "lpx:get-num-columns:: LPX -> N" (id lpx:get-num-columns))) (p "Returns the current number of columns in the given problem.")) (def (sig (procedure "lpx:set-row-bounds:: LPX * I * BOUNDS -> LPX" (id lpx:set-row-bounds))) (p "Sets bounds for row " (tt "I") " in the given problem. Argument " (tt "BOUNDS") " specifies the type and bounds for the specified row. It can take one of the following forms:") (table (@ (class "symbol-table")) (tr (td "'(unbounded)") (td "Free (unbounded) variable, " (tt "-Inf <= x <= +Inf"))) "\n" (tr (td "'(lower-bound LB)") (td "Variable with lower bound, " (tt "LB <= x <= +Inf"))) "\n" (tr (td "'(upper-bound UB)") (td "Variable with upper bound, " (tt "-Inf <= x <= UB"))) "\n" (tr (td "'(double-bounded LB UB)") (td "Double-bounded variable, " (tt "LB <= x <= UB"))) "\n" (tr (td "'(fixed LB UB)") (td "Fixed variable, " (tt "LB = x = UB"))))) (def (sig (procedure "lpx:set-column-bounds:: LPX * J * BOUNDS -> LPX" (id lpx:set-column-bounds))) (p "Sets bounds for column " (tt "J") " in the given problem. Argument " (tt "BOUNDS") " specifies the type and bounds for the specified column. It can take one of the following forms:") (table (@ (class "symbol-table")) (tr (td "'(unbounded)") (td "Free (unbounded) variable, " (tt "-Inf <= x <= +Inf"))) "\n" (tr (td "'(lower-bound LB)") (td "Variable with lower bound, " (tt "LB <= x <= +Inf"))) "\n" (tr (td "'(upper-bound UB)") (td "Variable with upper bound, " (tt "-Inf <= x <= UB"))) "\n" (tr (td "'(double-bounded LB UB)") (td "Double-bounded variable, " (tt "LB <= x <= UB"))) "\n" (tr (td "'(fixed LB UB)") (td "Fixed variable, " (tt "LB = x = UB"))))) (def (sig (procedure "lpx:set-objective-coefficient:: LPX * J * COEF -> LPX" (id lpx:set-objective-coefficient))) (p "Sets the objective coefficient at column " (tt "J") " (structural variable).")) (def (sig (procedure "lpx:set-column-kind:: LPX * J * KIND -> LPX" (id lpx:set-column-kind))) (p "Sets the kind of column " (tt "J") " (structural variable). Argument " (tt "KIND") " can be one of the following:") (table (@ (class "symbol-table")) (tr (td "'iv") (td "integer variable")) "\n" (tr (td "'cv") (td "continuous variable")))) (def (sig (procedure "lpx:load-constraint-matrix:: LPX * F64VECTOR * NROWS * NCOLS [* ORDER] -> LPX" (id lpx:load-constraint-matrix))) (p "Loads the constraint matrix for the given problem. The constraints matrix is represented as an SRFI-4 " (tt "f64vector") " (in row-major or column-major order). Optional argument " (tt "ORDER") " specifies the element order of the constraints matrix. It can be one of " (tt "'row-major") " or " (tt "'column-major") ".")) (def (sig (procedure "lpx:get-column-primals:: LPX -> F64VECTOR" (id lpx:get-column-primals))) (p "Returns the primal values of all structural variables (columns).")) (def (sig (procedure "lpx:get-objective-value:: LPX -> NUMBER" (id lpx:get-objective-value))) (p "Returns the current value of the objective function."))) (section 3 "Problem control parameters" (p "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.") (def (sig (procedure "lpx:message_level:: LPX [ * (none | error | normal | full)] -> LPX | VALUE" (id lpx:message_level))) (p "Level of messages output by solver routines.")) (def (sig (procedure "lpx:scaling:: LPX [ * (none | equilibration | geometric-mean | geometric-mean+equilibration)] -> LPX | VALUE" (id lpx:scaling))) (p "Scaling option.")) (def (sig (procedure "lpx:use_dual_simplex:: LPX [ * BOOL] -> LPX | VALUE" (id lpx:use_dual_simplex))) (p "Dual simplex option.")) (def (sig (procedure "lpx:pricing:: LPX [ * (textbook | steepest-edge)] -> LPX | VALUE" (id lpx:pricing))) (p "Pricing option (for both primal and dual simplex).")) (def (sig (procedure "lpx:solution_rounding:: LPX [ * BOOL] -> LPX | VALUE" (id lpx:solution_rounding))) (p "Solution rounding option.")) (def (sig (procedure "lpx:iteration_limit:: LPX [ * INT] -> LPX | VALUE" (id lpx:iteration_limit))) (p "Simplex iteration limit.")) (def (sig (procedure "lpx:iteration_count:: LPX [ * INT] -> LPX | VALUE" (id lpx:iteration_count))) (p "Simplex iteration count.")) (def (sig (procedure "lpx:branching_heuristic:: LPX [ * (first | last | driebeck+tomlin)] -> LPX | VALUE" (id lpx:branching_heuristic))) (p "Branching heuristic option (for MIP only).")) (def (sig (procedure "lpx:backtracking_heuristic:: LPX [ * (dfs | bfs | best-projection | best-local-bound)] -> LPX | VALUE" (id lpx:backtracking_heuristic))) (p "Backtracking heuristic option (for MIP only).")) (def (sig (procedure "lpx:use_presolver:: LPX [ * BOOL] -> LPX | VALUE" (id lpx:use_presolver))) (p "Use the LP presolver.")) (def (sig (procedure "lpx:relaxation:: LPX [ * REAL] -> LPX | VALUE" (id lpx:relaxation))) (p "Relaxation parameter used in the ratio test.")) (def (sig (procedure "lpx:time_limit:: LPX [ * REAL] -> LPX | VALUE" (id lpx:time_limit))) (p "Searching time limit, in seconds."))) (section 3 "Scaling & solver procedures" (def (sig (procedure "lpx:scale-problem:: LPX -> LPX" (id lpx:scale-problem))) (p "This procedure performs scaling of of the constraints matrix in order to improve its numerical properties.")) (def (sig (procedure "lpx:simplex:: LPX -> STATUS" (id lpx:simplex))) (p "This procedure solves the given LP problem using the simplex method.  It can return one of the following status codes:") (table (@ (class "symbol-table")) (tr (td "LPX_E_OK") (td "the LP problem has been successfully solved")) "\n" (tr (td "LPX_E_BADB") (td "Unable to start\nthe search, because the initial basis specified in the problem object\nis invalid--the number of basic (auxiliary and structural) variables\nis not the same as the number of rows in the problem object. ")) "\n" (tr (td "LPX_E_SING") (td "Unable to start\nthe search, because the basis matrix corresponding to the initial\nbasis is singular within the working precision. ")) "\n" (tr (td "LPX_E_COND") (td "Unable to start\nthe search, because the basis matrix corresponding to the initial\nbasis is ill-conditioned, i.e. its condition number is too large. ")) "\n" (tr (td "LPX_E_BOUND") (td "Unable to start\nthe search, because some double-bounded (auxiliary or structural)\nvariables have incorrect bounds. ")) "\n" (tr (td "LPX_E_FAIL") (td "The search was\nprematurely terminated due to the solver failure. ")) "\n" (tr (td "LPX_E_OBJLL") (td "The search was\nprematurely terminated, because the objective function being maximized\nhas reached its lower limit and continues decreasing (the dual simplex\nonly). ")) "\n" (tr (td "LPX_E_OBJUL") (td "The search was\nprematurely terminated, because the objective function being minimized\nhas reached its upper limit and continues increasing (the dual simplex\nonly). ")) "\n" (tr (td "LPX_E_ITLIM") (td "The search was\nprematurely terminated, because the simplex iteration limit has been\nexceeded. ")) "\n" (tr (td "LPX_E_TMLIM") (td "The search was\nprematurely terminated, because the time limit has been exceeded. ")) "\n" (tr (td "LPX_E_NOPFS") (td "The LP problem\ninstance has no primal feasible solution (only if the LP presolver is used). ")) "\n" (tr (td "LPX_E_NODFS") (td "The LP problem\ninstance has no dual feasible solution (only if the LP presolver is used).")))) (def (sig (procedure "lpx:integer:: LPX -> STATUS" (id lpx:integer))) (p "Solves an MIP problem using the branch-and-bound method.")))) (section 2 "Examples" (pre ";;\n;; Two Mines Linear programming example from\n;;\n;; http://people.brunel.ac.uk/~mastjjb/jeb/or/basicor.html#twomines\n;; \n\n;; Two Mines Company\n;;\n;; The Two Mines Company owns two different mines that produce an ore\n;; which, after being crushed, is graded into three classes: high,\n;; medium and low-grade. The company has contracted to provide a\n;; smelting plant with 12 tons of high-grade, 8 tons of medium-grade\n;; and 24 tons of low-grade ore per week. The two mines have different\n;; operating characteristics as detailed below.\n;; \n;; Mine    Cost per day ($'000)    Production (tons/day)                \n;;                                High    Medium    Low\n;; X       180                     6       3         4\n;; Y       160                     1       1         6\n;;\n;;                                 Production (tons/week)\n;;                                High    Medium    Low\n;; Contract                       12       8        24\n;;\n;; How many days per week should each mine be operated to fulfill the\n;; smelting plant contract?\n;;\n\n(require-extension srfi-4)\n(require-extension glpk)\n\n;; (1) Unknown variables\n;;\n;;      x = number of days per week mine X is operated\n;;      y = number of days per week mine Y is operated\n;;\n;; (2) Constraints\n;;\n;;\n;;    * ore production constraints - balance the amount produced with\n;;      the quantity required under the smelting plant contract\n;;\n;;      High    6x + 1y >= 12\n;;      Medium  3x + 1y >= 8\n;;      Low     4x + 6y >= 24\n;;\n;; (3) Objective\n;;\n;;     The objective is to minimise cost which is given by 180x + 160y.\n;;\n;;     minimise  180x + 160y\n;;     subject to\n;;         6x + y >= 12\n;;         3x + y >= 8\n;;         4x + 6y >= 24\n;;         x <= 5\n;;         y <= 5\n;;         x,y >= 0\n;;\n;; (4) Auxiliary variables (rows)\n;;\n;;  p = 6x + y\n;;  q = 3x + y\n;;  r = 4x + 6y\n;;\n;;  12 <= p < +inf\n;;   8 <= q < +inf\n;;  24 <= r < +inf\n\n(define pbounds `((lower-bound 12) (lower-bound 8) (lower-bound 24)))\n\n;; (5) Structural variables (columns)\n;;\n;;  0 <= x <= 5\n;;  0 <= y <= 5\n\n(define xbounds  `((double-bounded 0 5) (double-bounded 0 5)))\n\n;; (6) Objective coefficients: 180, 160\n\n(define objcoefs (list 180 160))\n\n\n;; Constraints matrix (in row-major order)\n;; \n;;   6  1   \n;;   3  1   \n;;   4  6   \n\n(define constraints (f64vector 6 1 3 1 4 6))\n\n;; Create the problem definition & run the solver\n(let ((lpp (lpx:make-problem 'minimize pbounds xbounds objcoefs constraints)))\n  (lpx:scale-problem lpp)\n  (lpx:use_presolver lpp #t)\n  (let ((status (lpx:simplex lpp)))\n    (print \"solution status = \" status)\n    (print \"objective value = \" (lpx:get-objective-value lpp))\n    (print \"primals = \" (lpx:get-column-primals lpp))))\n")) (section 2 "About this egg" (section 3 "Author" (p (int-link "/users/ivan-raikov" "Ivan Raikov"))) (section 3 "Version history" (dl (dt "1.4") (dd "Using assert in unit test") (dt "1.3") (dd "Documentation converted to wiki format") (dt "1.2") (dd "Ported to Chicken 4") (dt "1.1") (dd "Added chicken-glpk.h to file manifest") (dt "1.0") (dd "Initial release"))) (section 3 "License" (pre "Copyright 2008-2011 Ivan Raikov and the Okinawa Institute of Science and Technology\n\nThis program is free software: you can redistribute it and/or modify\nit under the terms of the GNU General Public License as published by\nthe Free Software Foundation, either version 3 of the License, or (at\nyour option) any later version.\n\nThis program is distributed in the hope that it will be useful, but\nWITHOUT ANY WARRANTY; without even the implied warranty of\nMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU\nGeneral Public License for more details.\n\nA full copy of the GPL license can be found at\n<http://www.gnu.org/licenses/>."))))