Skip to content
A Common Lisp library for solving linear programming problems
Common Lisp NewLisp
Branch: master
Clone or download
Latest commit f16e9e5 Jul 18, 2019

README.md

Common Lisp Linear Programming

Travis Build Status Appveyor Build status Coverage Status

MIT License GitHub release Current documentation

This is a Common Lisp library for solving linear programming problems. It is implemented in pure Common Lisp, instead of calling a high performance library. This has the advantage of being dependent on only a couple community standard libraries (ASDF, Alexandria, Iterate). However, it limits the performance of solving larger problems. If there is interest in a high performance backend, let me know; it shouldn't be hard to make the backend replaceable.

Installation

The linear-programming library is not yet in the main Quicklisp distribution, just Ultralisp. The Ultralisp dist can be added by running (ql-dist:install-dist "http://dist.ultralisp.org/" :prompt nil). Then, this library can be loaded with (ql:quickload :linear-programming). You can check that it works by running (asdf:test-system :linear-programming).

If you are not using Quicklisp, place this repository, Alexandria, and Iterate somewhere where ASDF can find them. Then, it can be loaded with (asdf:load-system :linear-programming) and tested as above.

Usage

See neil-lindquist.github.io/linear-programming/ for further documentation.

Consider the following linear programming problem.

maximize x + 4y + 3z
such that

  • 2x + y <= 8
  • y + z <= 7

First, the problem needs to be specified. Problems are specified with a simple DSL, as described in the syntax reference.

(use-package :linear-programming)

(defvar problem (parse-linear-problem '(max (= w (+ x (* 4 y) (* 3 z))))
                                      '((<= (+ (* 2 x) y) 8)
                                        (<= (+ y z) 7))))

Once the problem is created, it can be solved with the simplex method.

(defvar solution (solve-problem problem))

Finally, the optimal tableau can be inspected to get the resulting objective function, decision variables, and shadow prices.

(format t "Objective value solution: ~A~%" (solution-variable solution 'w))
(format t "x = ~A (shadow price: ~A)~%" (solution-variable solution 'x) (solution-shadow-price solution 'x))
(format t "y = ~A (shadow price: ~A)~%" (solution-variable solution 'y) (solution-shadow-price solution 'y))
(format t "z = ~A (shadow price: ~A)~%" (solution-variable solution 'z) (solution-shadow-price solution 'z))

;; ==>
;; Objective value solution: 57/2
;; x = 1/2 (shadow price: 0)
;; y = 7 (shadow price: 0)
;; z = 0 (shadow price: 1/2)

Alternatively, the with-solution-variables and with-solved-problem macros simplify some steps and binds the solution variables in their bodies.

(with-solution-variables (w x y z) solution
  (format t "Objective value solution: ~A~%" w)
  (format t "x = ~A (shadow price: ~A)~%" x (shadow-price solution 'x))
  (format t "y = ~A (shadow price: ~A)~%" y (shadow-price solution 'y))
  (format t "z = ~A (shadow price: ~A)~%" z (shadow-price solution 'z)))

;; ==>
;; Objective value solution: 57/2
;; x = 1/2 (shadow price: 0)
;; y = 7 (shadow price: 0)
;; z = 0 (shadow price: 1/2)


(with-solved-problem ((max (= w (+ x (* 4 y) (* 3 z))))
                      (<= (+ (* 2 x) y) 8)
                      (<= (+ y z) 7))
  (format t "Objective value solution: ~A~%" w)
  (format t "x = ~A (shadow price: ~A)~%" x (shadow-price solution 'x))
  (format t "y = ~A (shadow price: ~A)~%" y (shadow-price solution 'y))
  (format t "z = ~A (shadow price: ~A)~%" z (shadow-price solution 'z)))

;; ==>
;; Objective value solution: 57/2
;; x = 1/2 (shadow price: 0)
;; y = 7 (shadow price: 0)
;; z = 0 (shadow price: 1/2)
You can’t perform that action at this time.