# Common Lisp Linear Programming

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