A Common Lisp library for solving linear programs.

CL-GLPK should work on any Lisp/OS/machine combination, as long as CFFI, Trivial-Garbage, Iterate, and GLPK work.

CL-GLPK has been tested on SBCL 1.0.2 / Mac OS X (10.4) / PPC and CCL trunk / Mac OS X (10.6) / x86-64.

Load the ASDF system. The low-level FFI bindings are implicitly documented by the GLPK manual. For the (partial) high-level API, see examples/sample.lisp. The highest-level API allows you to express linear programs like:

(make-linear-program
 :maximize (+ (* (- 12 2) x1) (* 6 x2) (* 4 x3))
 :subject-to ((<= (+ x1 x2 x3) 100)
              (<= (+ (* (+ 2 2) x2) (* 10 x1) (* 5 x3)) (+ 200 400))
              (<= (+ (* 2 x1) (* 2 x2) (* 6 x3)) 300))
 :bounds ((>= x3 10)))

Any of the :BOUNDS constraints could be in the :SUBJECT-TO list instead, but I'm not yet sure what impact that will have on performance, so until I can identify (and if necessary, prevent) that, I pull my variable bounds into a separate parameter.

Then you can solve the program and get results with

(simplex *)
(format t "z = ~a, x1 = ~a, x2 = ~a, x3 = ~a~%"
        (objective-value **)
        (column-primal-value ** 1)
        (column-primal-value ** 2)
        (column-primal-value ** 3))

There are still a lot of improvements to build into this high-level API before it's really complete.

BSD sans advertising clause (see file COPYING)

Currently error handling is done by either (ERROR ...) or (ASSERT ...).

This is partially completed in MAKE-LINEAR-PROGRAM.