The linear-programming Reference Manual

Table of Contents

The linear-programming Reference Manual

This is the linear-programming Reference Manual, version 2.1.1, generated automatically by Declt version 3.0 "Montgomery Scott" on Wed Oct 13 11:24:46 2021 GMT+0.

1 Introduction

Common Lisp Linear Programming

This is a Common Lisp library for solving linear programming problems. It's designed to provide a high-level and ergonomic API for specifying linear programming problems as lisp expressions.

The core library is implemented purely in Common Lisp with only a few community-standard libraries as dependencies (ASDF, Alexandria, Iterate). However, the solver is designed to support alternative backends without any change to the user's code. Currently, there is a backend for the GNU Linear Programming Kit (GLPK).

Installation

The linear-programming library is avalible in both the main Quicklisp distribution and Ultralisp, so it can loaded with 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
• x, y, z ≥ 0

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 reduced-costs (i.e. the shadow prices for the variable's lower bounds).

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

;; ==>
;; Objective value solution: 57/2
;; x = 1/2 (reduced cost: 0)
;; y = 7 (reduced cost: 0)
;; z = 0 (reduced cost: 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 (reduced cost: ~A)~%" x (reduced-cost x))
  (format t "y = ~A (reduced cost: ~A)~%" y (reduced-cost y))
  (format t "z = ~A (reduced cost: ~A)~%" z (reduced-cost z)))

;; ==>
;; Objective value solution: 57/2
;; x = 1/2 (reduced cost: 0)
;; y = 7 (reduced cost: 0)
;; z = 0 (reduced cost: 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 (reduced cost: ~A)~%" x (reduced-cost x))
  (format t "y = ~A (reduced cost: ~A)~%" y (reduced-cost y))
  (format t "z = ~A (reduced cost: ~A)~%" z (reduced-cost z)))

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

2 Systems

The main system appears first, followed by any subsystem dependency.

2.1 linear-programming

Author

Neil Lindquist <NeilLindquist5@gmail.com>

Contact

NeilLindquist5@gmail.com

Home Page

https://neil-lindquist.github.io/linear-programming/

Source Control

(:git "https://github.com/neil-lindquist/linear-programming.git")

Bug Tracker

https://github.com/neil-lindquist/linear-programming/issues

License

MIT

Description

A library for solving linear programming problems

Version

2.1.1

Dependencies

• asdf (at least version 3.1.6)
• linear-programming/all (system)

Source

linear-programming.asd (file)

2.2 linear-programming/all

Author

Neil Lindquist <NeilLindquist5@gmail.com>

Contact

NeilLindquist5@gmail.com

Home Page

https://neil-lindquist.github.io/linear-programming/

Source Control

(:git "https://github.com/neil-lindquist/linear-programming.git")

Bug Tracker

https://github.com/neil-lindquist/linear-programming/issues

License

MIT

Dependencies

• linear-programming/problem (system)
• linear-programming/solver (system)
• linear-programming/conditions (system)
• linear-programming/external-formats (system)
• linear-programming/simplex (system)

Source

linear-programming.asd (file)

Component

file-type.lisp (file)

2.3 linear-programming/solver

Author

Neil Lindquist <NeilLindquist5@gmail.com>

Contact

NeilLindquist5@gmail.com

Home Page

https://neil-lindquist.github.io/linear-programming/

Source Control

(:git "https://github.com/neil-lindquist/linear-programming.git")

Bug Tracker

https://github.com/neil-lindquist/linear-programming/issues

License

MIT

Dependencies

• iterate
• alexandria
• linear-programming/problem (system)
• linear-programming/simplex (system)

Source

linear-programming.asd (file)

Component

file-type.lisp (file)

2.4 linear-programming/external-formats

Author

Neil Lindquist <NeilLindquist5@gmail.com>

Contact

NeilLindquist5@gmail.com

Home Page

https://neil-lindquist.github.io/linear-programming/

Source Control

(:git "https://github.com/neil-lindquist/linear-programming.git")

Bug Tracker

https://github.com/neil-lindquist/linear-programming/issues

License

MIT

Dependencies

• iterate
• linear-programming/problem (system)
• alexandria
• linear-programming/expressions (system)
• linear-programming/utils (system)

Source

linear-programming.asd (file)

Component

file-type.lisp (file)

2.5 linear-programming/simplex

Author

Neil Lindquist <NeilLindquist5@gmail.com>

Contact

NeilLindquist5@gmail.com

Home Page

https://neil-lindquist.github.io/linear-programming/

Source Control

(:git "https://github.com/neil-lindquist/linear-programming.git")

Bug Tracker

https://github.com/neil-lindquist/linear-programming/issues

License

MIT

Dependencies

• iterate
• linear-programming/conditions (system)
• linear-programming/problem (system)
• linear-programming/utils (system)
• alexandria

Source

linear-programming.asd (file)

Component

file-type.lisp (file)

2.6 linear-programming/problem

Author

Neil Lindquist <NeilLindquist5@gmail.com>

Contact

NeilLindquist5@gmail.com

Home Page

https://neil-lindquist.github.io/linear-programming/

Source Control

(:git "https://github.com/neil-lindquist/linear-programming.git")

Bug Tracker

https://github.com/neil-lindquist/linear-programming/issues

License

MIT

Dependencies

• iterate
• linear-programming/conditions (system)
• linear-programming/expressions (system)
• alexandria
• linear-programming/utils (system)

Source

linear-programming.asd (file)

Component

file-type.lisp (file)

2.7 linear-programming/expressions

Author

Neil Lindquist <NeilLindquist5@gmail.com>

Contact

NeilLindquist5@gmail.com

Home Page

https://neil-lindquist.github.io/linear-programming/

Source Control

(:git "https://github.com/neil-lindquist/linear-programming.git")

Bug Tracker

https://github.com/neil-lindquist/linear-programming/issues

License

MIT

Dependencies

• iterate
• linear-programming/conditions (system)
• alexandria

Source

linear-programming.asd (file)

Component

file-type.lisp (file)

2.8 linear-programming/utils

Author

Neil Lindquist <NeilLindquist5@gmail.com>

Contact

NeilLindquist5@gmail.com

Home Page

https://neil-lindquist.github.io/linear-programming/

Source Control

(:git "https://github.com/neil-lindquist/linear-programming.git")

Bug Tracker

https://github.com/neil-lindquist/linear-programming/issues

License

MIT

Dependencies

• alexandria
• linear-programming/conditions (system)
• linear-programming/system-info (system)

Source

linear-programming.asd (file)

Component

file-type.lisp (file)

2.9 linear-programming/conditions

Author

Neil Lindquist <NeilLindquist5@gmail.com>

Contact

NeilLindquist5@gmail.com

Home Page

https://neil-lindquist.github.io/linear-programming/

Source Control

(:git "https://github.com/neil-lindquist/linear-programming.git")

Bug Tracker

https://github.com/neil-lindquist/linear-programming/issues

License

MIT

Source

linear-programming.asd (file)

Component

file-type.lisp (file)

2.10 linear-programming/system-info

Author

Neil Lindquist <NeilLindquist5@gmail.com>

Contact

NeilLindquist5@gmail.com

Home Page

https://neil-lindquist.github.io/linear-programming/

Source Control

(:git "https://github.com/neil-lindquist/linear-programming.git")

Bug Tracker

https://github.com/neil-lindquist/linear-programming/issues

License

MIT

Dependencies

• iterate
• alexandria

Source

linear-programming.asd (file)

Component

file-type.lisp (file)

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.

3.1 Lisp

3.1.1 linear-programming.asd

Location

/home/quickref/quicklisp/dists/quicklisp/software/linear-programming-20210411-git/linear-programming.asd

Systems

• linear-programming (system)
• linear-programming/all (system)
• linear-programming/solver (system)
• linear-programming/external-formats (system)
• linear-programming/simplex (system)
• linear-programming/problem (system)
• linear-programming/expressions (system)
• linear-programming/utils (system)
• linear-programming/conditions (system)
• linear-programming/system-info (system)

3.1.2 linear-programming/all/file-type.lisp

Parent

linear-programming/all (system)

Location

all.lisp

Packages

linear-programming/all

3.1.3 linear-programming/solver/file-type.lisp

Parent

linear-programming/solver (system)

Location

solver.lisp

Packages

linear-programming/solver

Exported Definitions

• *solver* (special variable)
• solution-objective-value (generic function)
• solution-objective-value (method)
• solution-problem (generic function)
• solution-problem (method)
• solution-reduced-cost (generic function)
• solution-reduced-cost (method)
• solution-variable (generic function)
• solution-variable (method)
• solve-problem (function)
• with-solution-variables (macro)
• with-solved-problem (macro)

3.1.4 linear-programming/external-formats/file-type.lisp

Parent

linear-programming/external-formats (system)

Location

external-formats.lisp

Packages

linear-programming/external-formats

Exported Definitions

• read-mps (function)
• read-sexp (function)
• write-sexp (function)
• write-standard-format (function)

Internal Definitions

• newlinep (function)
• print-linear-expression (function)
• read-until (function)

3.1.5 linear-programming/simplex/file-type.lisp

Parent

linear-programming/simplex (system)

Location

simplex.lisp

Packages

linear-programming/simplex

Exported Definitions

• build-tableau (function)
• copy-tableau (function)
• n-pivot-row (function)
• n-solve-tableau (function)
• pivot-row (function)
• simplex-solver (function)
• solve-tableau (function)
• tableau (structure)
• tableau-basis-columns (function)
• tableau-constraint-count (function)
• tableau-instance-problem (function)
• tableau-matrix (function)
• tableau-objective-value (function)
• tableau-p (function)
• tableau-problem (function)
• tableau-reduced-cost (function)
• tableau-var-count (function)
• tableau-variable (function)
• with-tableau-variables (macro)

Internal Definitions

• build-and-solve (function)
• find-entering-column (function)
• find-pivoting-row (function)
• gen-entries (function)
• make-tableau (function)
• tableau-fp-tolerance-factor (function)
• tableau-var-mapping (function)
• var-mapping-entry (type)
• violated-integer-constraint (function)

3.1.6 linear-programming/problem/file-type.lisp

Parent

linear-programming/problem (system)

Location

problem.lisp

Packages

linear-programming/problem

Exported Definitions

• make-linear-problem (macro)
• parse-linear-problem (function)
• problem (structure)
• problem-constraints (function)
• problem-integer-vars (function)
• problem-objective-func (function)
• problem-objective-var (function)
• problem-type (function)
• problem-var-bounds (function)
• problem-vars (function)

Internal Definitions

• copy-problem (function)
• make-problem (function)
• parse-linear-constraints (function)
• problem-p (function)

3.1.7 linear-programming/expressions/file-type.lisp

Parent

linear-programming/expressions (system)

Location

expressions.lisp

Packages

linear-programming/expressions

Exported Definitions

• format-linear-expression (function)
• parse-linear-expression (function)
• scale-linear-expression (function)
• sum-linear-expressions (function)

Internal Definitions

• linear-constant-p (function)
• sum-linear-expressions-list (function)

3.1.8 linear-programming/utils/file-type.lisp

Parent

linear-programming/utils (system)

Location

utils.lisp

Packages

linear-programming/utils

Exported Definitions

• fp< (compiler macro)
• fp< (function)
• fp<= (compiler macro)
• fp<= (function)
• fp= (function)
• fp> (compiler macro)
• fp> (function)
• fp>= (compiler macro)
• fp>= (function)
• lb-max (function)
• lb-min (function)
• ub-max (function)
• ub-min (function)
• validate-bounds (function)

Internal Definitions

• fp-inequality (macro)
• lb (type)
• ub (type)

3.1.9 linear-programming/conditions/file-type.lisp

Parent

linear-programming/conditions (system)

Location

conditions.lisp

Packages

linear-programming/conditions

Exported Definitions

• infeasible-integer-constraints-error (condition)
• infeasible-problem-error (condition)
• invalid-bounds-error (condition)
• nonlinear-error (condition)
• parsing-error (condition)
• solver-error (condition)
• unbounded-problem-error (condition)
• unsupported-constraint-error (condition)

Internal Definitions

• constraint (method)
• description (method)
• lb (method)
• nonlinear-expression (method)
• solver-name (method)
• ub (method)
• var (method)

3.1.10 linear-programming/system-info/file-type.lisp

Parent

linear-programming/system-info (system)

Location

system-info.lisp

Packages

linear-programming/system-info

Exported Definitions

• +supported-floats+ (constant)
• float-contagion (function)
• optimization-type (function)

4 Packages

Packages are listed by definition order.

4.1 linear-programming/all

The overall package for the linear programming library. It contains only the reexported symbols of ‘linear-programming/problem‘, ‘linear-programming/solver‘, ‘linear-programming/conditioner‘, and ‘linear-programming/external-formats‘, plus ‘simplex-solver‘ from ‘linear-programming/simplex‘.

Source

file-type.lisp (file)

Nickname

linear-programming

Use List

• linear-programming/external-formats
• linear-programming/conditions
• linear-programming/solver
• linear-programming/problem

4.2 linear-programming/solver

The high level linear programming solver interface. This interface is able to wrap multiple backends. The backend can be adjusted by setting the ‘*solver*‘ variable. The default backend is the ‘simplex-solver‘ in the ‘linear-programming/simplex‘ package.

Source

file-type.lisp (file)

Use List

• iterate
• common-lisp

Used By List

linear-programming/all

Exported Definitions

• *solver* (special variable)
• solution-objective-value (generic function)
• solution-objective-value (method)
• solution-problem (generic function)
• solution-problem (method)
• solution-reduced-cost (generic function)
• solution-reduced-cost (method)
• solution-variable (generic function)
• solution-variable (method)
• solve-problem (function)
• with-solution-variables (macro)
• with-solved-problem (macro)

4.3 linear-programming/external-formats

Handles reading and writing problems to external formats.

Source

file-type.lisp (file)

Use List

• linear-programming/problem
• iterate
• common-lisp

Used By List

linear-programming/all

Exported Definitions

• read-mps (function)
• read-sexp (function)
• write-sexp (function)
• write-standard-format (function)

Internal Definitions

• newlinep (function)
• print-linear-expression (function)
• read-until (function)

4.4 linear-programming/simplex

The actual simplex solver implementation for the default solver backend. This package should be used through the interface provided by the ‘linear-programming/solver‘ package.

Source

file-type.lisp (file)

Use List

• linear-programming/utils
• linear-programming/problem
• linear-programming/conditions
• iterate
• common-lisp

Exported Definitions

• build-tableau (function)
• copy-tableau (function)
• n-pivot-row (function)
• n-solve-tableau (function)
• pivot-row (function)
• simplex-solver (function)
• solve-tableau (function)
• tableau (structure)
• tableau-basis-columns (function)
• tableau-constraint-count (function)
• tableau-instance-problem (function)
• tableau-matrix (function)
• tableau-objective-value (function)
• tableau-p (function)
• tableau-problem (function)
• tableau-reduced-cost (function)
• tableau-var-count (function)
• tableau-variable (function)
• with-tableau-variables (macro)

Internal Definitions

• build-and-solve (function)
• find-entering-column (function)
• find-pivoting-row (function)
• gen-entries (function)
• make-tableau (function)
• tableau-fp-tolerance-factor (function)
• tableau-var-mapping (function)
• var-mapping-entry (type)
• violated-integer-constraint (function)

4.5 linear-programming/problem

Handles the representation of linear programming problems.

Source

file-type.lisp (file)

Use List

• linear-programming/expressions
• linear-programming/conditions
• iterate
• common-lisp

Used By List

• linear-programming/all
• linear-programming/external-formats
• linear-programming/simplex

Exported Definitions

• make-linear-problem (macro)
• parse-linear-problem (function)
• problem (structure)
• problem-constraints (function)
• problem-integer-vars (function)
• problem-objective-func (function)
• problem-objective-var (function)
• problem-type (function)
• problem-var-bounds (function)
• problem-vars (function)

Internal Definitions

• copy-problem (function)
• make-problem (function)
• parse-linear-constraints (function)
• problem-p (function)

4.6 linear-programming/expressions

Contains functions for processing linear expressions.

Source

file-type.lisp (file)

Use List

• linear-programming/conditions
• iterate
• common-lisp

Used By List

linear-programming/problem

Exported Definitions

• format-linear-expression (function)
• parse-linear-expression (function)
• scale-linear-expression (function)
• sum-linear-expressions (function)

Internal Definitions

• linear-constant-p (function)
• sum-linear-expressions-list (function)

4.7 linear-programming/utils

Various internal utilities

Source

file-type.lisp (file)

Use List

common-lisp

Used By List

linear-programming/simplex

Exported Definitions

• fp< (compiler macro)
• fp< (function)
• fp<= (compiler macro)
• fp<= (function)
• fp= (function)
• fp> (compiler macro)
• fp> (function)
• fp>= (compiler macro)
• fp>= (function)
• lb-max (function)
• lb-min (function)
• ub-max (function)
• ub-min (function)
• validate-bounds (function)

Internal Definitions

• fp-inequality (macro)
• lb (type)
• ub (type)

4.8 linear-programming/conditions

Contains the various conditions used by this library.

Source

file-type.lisp (file)

Use List

common-lisp

Used By List

• linear-programming/all
• linear-programming/simplex
• linear-programming/problem
• linear-programming/expressions

Exported Definitions

• infeasible-integer-constraints-error (condition)
• infeasible-problem-error (condition)
• invalid-bounds-error (condition)
• nonlinear-error (condition)
• parsing-error (condition)
• solver-error (condition)
• unbounded-problem-error (condition)
• unsupported-constraint-error (condition)

Internal Definitions

• constraint (generic function)
• constraint (method)
• description (generic function)
• description (method)
• lb (generic function)
• lb (method)
• nonlinear-expression (generic function)
• nonlinear-expression (method)
• solver-name (generic function)
• solver-name (method)
• ub (generic function)
• ub (method)
• var (generic function)
• var (method)

4.9 linear-programming/system-info

Utilities for inspecting how certain implmenetation-dependant features behave.

Source

file-type.lisp (file)

Use List

• iterate
• common-lisp

Exported Definitions

• +supported-floats+ (constant)
• float-contagion (function)
• optimization-type (function)

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

5.1 Exported definitions

5.1.1 Constants

Constant: +supported-floats+

Contains the distinct floating point representations supported.

Package

linear-programming/system-info

Source

file-type.lisp (file)

5.1.2 Special variables

Special Variable: *solver*

The function that should be used by solve-problem (defaults to ‘linear-programming/simplex:simplex-solver‘). The function should take a problem, and any backend specific keyword arguments and returns some form of solution object. The solution object should support the following methods ‘solution-problem‘, ‘solution-objective-value‘, ‘solution-variable‘, and ‘solution-reduced-cost‘.

Package

linear-programming/solver

Source

file-type.lisp (file)

5.1.3 Macros

Macro: make-linear-problem OBJECTIVE &rest CONSTRAINTS

Creates a linear problem from the expressions in the body

Package

linear-programming/problem

Source

file-type.lisp (file)

Macro: with-solution-variables VAR-LIST SOLUTION &body BODY

Evaluates the body with the variables in ‘var-list‘ bound to their values in the solution. Additionally, the macro ‘reduced-cost‘ is locally bound that takes a variable name and provides it’s reduced cost.

Package

linear-programming/solver

Source

file-type.lisp (file)

Macro: with-solved-problem (OBJECTIVE-FUNC &rest CONSTRAINTS) &body BODY

Takes the problem description, and evaluates ‘body‘ with the variables of the problem bound to their solution values. Additionally, the macro ‘reduced-cost‘ is locally bound that takes a variable name and provides it’s reduced cost.

Package

linear-programming/solver

Source

file-type.lisp (file)

Macro: with-tableau-variables VAR-LIST TABLEAU &body BODY

Evaluates the body with the variables in ‘var-list‘ bound to their values from the tableau.

Package

linear-programming/simplex

Source

file-type.lisp (file)

5.1.4 Compiler macros

Compiler Macro: fp< A B &optional FACTOR

Package

linear-programming/utils

Source

file-type.lisp (file)

Compiler Macro: fp<= A B &optional FACTOR

Package

linear-programming/utils

Source

file-type.lisp (file)

Compiler Macro: fp> A B &optional FACTOR

Package

linear-programming/utils

Source

file-type.lisp (file)

Compiler Macro: fp>= A B &optional FACTOR

Package

linear-programming/utils

Source

file-type.lisp (file)

5.1.5 Functions

Function: build-tableau PROBLEM INSTANCE-PROBLEM &key FP-TOLERANCE-FACTOR

Creates the tableau from the given linear problem. If the trivial basis is not feasible, instead a list is returned containing the two tableaus for a two-phase simplex method.

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: copy-tableau TABLEAU

Copies the given tableau and it’s matrix.

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: float-contagion T1 T2

Computes the representation type using the rules for float contagion.

Package

linear-programming/system-info

Source

file-type.lisp (file)

Function: format-linear-expression ALIST

Formats a linear expression as a sexp.

Package

linear-programming/expressions

Source

file-type.lisp (file)

Function: fp< A B &optional FACTOR

Tests for inequality taking into account floating point error. ‘factor‘ is the acceptable multiple of unit round off that the two values can differ by.

Package

linear-programming/utils

Source

file-type.lisp (file)

Function: fp<= A B &optional FACTOR

Tests for inequality taking into account floating point error. ‘factor‘ is the acceptable multiple of unit round off that the two values can differ by.

Package

linear-programming/utils

Source

file-type.lisp (file)

Function: fp= A B &optional FACTOR

Tests for equality taking into account floating point error. ‘factor‘ is the acceptable multiple of unit round off that the two values can differ by.

Package

linear-programming/utils

Source

file-type.lisp (file)

Function: fp> A B &optional FACTOR

Tests for inequality taking into account floating point error. ‘factor‘ is the acceptable multiple of unit round off that the two values can differ by.

Package

linear-programming/utils

Source

file-type.lisp (file)

Function: fp>= A B &optional FACTOR

Tests for inequality taking into account floating point error. ‘factor‘ is the acceptable multiple of unit round off that the two values can differ by.

Package

linear-programming/utils

Source

file-type.lisp (file)

Function: lb-max X Y

Computes the maximum value where nil is negative infinity

Package

linear-programming/utils

Source

file-type.lisp (file)

Function: lb-min X Y

Computes the minimum value where nil is negative infinity

Package

linear-programming/utils

Source

file-type.lisp (file)

Function: n-pivot-row TABLEAU ENTERING-COL CHANGING-ROW

Destructively applies a single pivot to the table.

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: n-solve-tableau TABLEAU

A non-consing version of [‘solve-tableau‘](#function-linear-programming/simplex:solve-tableau).

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: optimization-type X

Gets the type of ‘x‘ to optimize for. If ‘x‘ is a rational, returns ‘rational‘. Otherwise, returns the type of ‘x‘.

Package

linear-programming/system-info

Source

file-type.lisp (file)

Function: parse-linear-expression EXPR

Parses the expression into a alist mapping variables to coefficients. Any constant values are mapped to ‘+constant+‘.

Package

linear-programming/expressions

Source

file-type.lisp (file)

Function: parse-linear-problem OBJECTIVE-EXP CONSTRAINTS

Parses the expressions into a linear programming problem

Package

linear-programming/problem

Source

file-type.lisp (file)

Function: pivot-row TABLEAU ENTERING-COL CHANGING-ROW

Non-destructively applies a single pivot to the table.

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: problem-constraints INSTANCE

A list of (in)equality constraints.

Package

linear-programming/problem

Source

file-type.lisp (file)

Function: problem-integer-vars INSTANCE

A list of variables with integer constraints.

Package

linear-programming/problem

Source

file-type.lisp (file)

Function: problem-objective-func INSTANCE

The objective function as a linear expression alist.

Package

linear-programming/problem

Source

file-type.lisp (file)

Function: problem-objective-var INSTANCE

The name of the objective function.

Package

linear-programming/problem

Source

file-type.lisp (file)

Function: problem-type INSTANCE

Whether the problem is a ‘min‘ or ‘max‘ problem.

Package

linear-programming/problem

Source

file-type.lisp (file)

Function: problem-var-bounds INSTANCE

A list of variable bounds, of the form ‘(var . (lower-bound . upper-bound))‘.

Package

linear-programming/problem

Source

file-type.lisp (file)

Function: problem-vars INSTANCE

An array of the variables specified in the problem.

Package

linear-programming/problem

Source

file-type.lisp (file)

Function: read-mps STREAM PROBLEM-TYPE &key PACKAGE READ-CASE TRIM-NAMES-P NUMBER-TYPE RHS-ID

Reads a problem in MPS format from the given stream. Note that a line starting with ‘ENDATA‘ ends the problem, so MPS files can be embedded in streams of other data. Only the fixed width version of the format is supported, but both the ‘OBJSENCE‘ and ‘OBJNAME‘ headers are supported and the ‘BV‘, ‘LI‘, and ‘UI‘ boundaries are supported.

Package

linear-programming/external-formats

Source

file-type.lisp (file)

Function: read-sexp STREAM &key ALLOW-READ-EVAL PACKAGE

Loads a problem stored in sexp format. This is a single sexp with the first element being the objective function and the rest of the elements being the constraints. Note that normally ‘*read-eval*‘ is bound to ‘nil‘, but can be enabled with ‘allow-read-eval‘; however, this should only be done when parsing trusted data.

Package

linear-programming/external-formats

Source

file-type.lisp (file)

Function: scale-linear-expression EXPR SCALAR

Multiplies the linear expression by the given scalar.

Package

linear-programming/expressions

Source

file-type.lisp (file)

Function: simplex-solver PROBLEM &rest ARGS

The solver interface function for the simplex backend. The ‘fp-tolerance‘ keyword argument can be used to indicate the tolerance for error on floating point comparisons (defaults to 1024).

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: solve-problem PROBLEM &rest ARGS &key &allow-other-keys

Solves the given problem using the function stored by ‘*solver*‘. Any keyword arguments are passed to the solver function.

Package

linear-programming/solver

Source

file-type.lisp (file)

Function: solve-tableau TABLEAU

Attempts to solve the tableau using the simplex method. If a list of two tableaus is given, then a two-phase version is used. The original tableau(s) are unchanged.

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: sum-linear-expressions &rest EXPRS

Takes linear expressions and reduces it into a single expression.

Package

linear-programming/expressions

Source

file-type.lisp (file)

Function: tableau-basis-columns INSTANCE

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: tableau-constraint-count INSTANCE

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: tableau-instance-problem INSTANCE

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: tableau-matrix INSTANCE

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: tableau-objective-value TABLEAU

Gets the objective function value in the tableau.

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: tableau-p OBJECT

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: tableau-problem INSTANCE

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: tableau-reduced-cost TABLEAU VAR

Gets the reduced cost (i.e. the shadow price for the lower bound) for the given variable from the tableau.

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: tableau-var-count INSTANCE

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: tableau-variable TABLEAU VAR

Gets the value of the given variable from the tableau

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: ub-max X Y

Computes the maximum value where nil is positive infinity

Package

linear-programming/utils

Source

file-type.lisp (file)

Function: ub-min X Y

Computes the minimum value where nil is positive infinity

Package

linear-programming/utils

Source

file-type.lisp (file)

Function: validate-bounds LB UB VAR

Checks that the bounds represent a non empty range

Package

linear-programming/utils

Source

file-type.lisp (file)

Function: write-sexp STREAM PROBLEM &key PACKAGE

Writes the problem as a sexp. The first element is the objective function and the rest of the elements are the constraints.

Package

linear-programming/external-formats

Source

file-type.lisp (file)

Function: write-standard-format STREAM PROBLEM &key UNICODEP AESTHETIC-VARIABLE-NAMES-P

Writes a problem to the given stream in human readable, standard notation. The ‘unicodep‘ argument controls whether to print comparisons as unicode or ascii. The ‘aesthetic-variable-names-p‘ argument controls whether variable names are printed aesthetically.

Package

linear-programming/external-formats

Source

file-type.lisp (file)

5.1.6 Generic functions

Generic Function: solution-objective-value SOLUTION

Gets the value of the objective function.

Package

linear-programming/solver

Source

file-type.lisp (file)

Methods

Method: solution-objective-value (SOLUTION tableau)

Generic Function: solution-problem SOLUTION

Gets the original problem for the solution.

Package

linear-programming/solver

Source

file-type.lisp (file)

Methods

Method: solution-problem (SOLUTION tableau)

Generic Function: solution-reduced-cost SOLUTION VARIABLE

Gets the reduced cost of the specified variable. This is the
amount that the objective coefficient for the variable must increase or decrease, for maximization and minimization problems respectively, before the given variable appears in an optimal solution.

Package

linear-programming/solver

Source

file-type.lisp (file)

Methods

Method: solution-reduced-cost (SOLUTION tableau) VARIABLE

Generic Function: solution-variable SOLUTION VARIABLE

Gets the value of the specified variable.

Package

linear-programming/solver

Source

file-type.lisp (file)

Methods

Method: solution-variable (SOLUTION tableau) VARIABLE

5.1.7 Conditions

Condition: infeasible-integer-constraints-error ()

Indicates that there is no feasible region due to the integer constraints.

Package

linear-programming/conditions

Source

file-type.lisp (file)

Direct superclasses

infeasible-problem-error (condition)

Condition: infeasible-problem-error ()

Indicates the there is no feasible region.

Package

linear-programming/conditions

Source

file-type.lisp (file)

Direct superclasses

solver-error (condition)

Direct subclasses

infeasible-integer-constraints-error (condition)

Condition: invalid-bounds-error ()

Indicates a problem with a variable’s bounds.

Package

linear-programming/conditions

Source

file-type.lisp (file)

Direct superclasses

parsing-error (condition)

Direct methods

• lb (method)
• ub (method)
• var (method)

Direct slots

Slot: var

Initargs

:var

Readers

var (generic function)

Slot: ub

Initargs

:ub

Readers

ub (generic function)

Slot: lb

Initargs

:lb

Readers

lb (generic function)

Condition: nonlinear-error ()

Indicates a form was not a linear expression. This includes the use of nonlinear functions and taking the product of multiple variables

Package

linear-programming/conditions

Source

file-type.lisp (file)

Direct superclasses

parsing-error (condition)

Direct methods

nonlinear-expression (method)

Direct slots

Slot: expression

Contains the problematic expression

Initargs

:expression

Readers

nonlinear-expression (generic function)

Condition: parsing-error ()

Indicates an error occured while parsing a linear problem. Includes a textual description of the issue.

Package

linear-programming/conditions

Source

file-type.lisp (file)

Direct superclasses

error (condition)

Direct subclasses

• nonlinear-error (condition)
• invalid-bounds-error (condition)

Direct methods

description (method)

Direct slots

Slot: description

Initargs

:description

Readers

description (generic function)

Condition: solver-error ()

The base class for errors that occur with the solving algorithm.

Package

linear-programming/conditions

Source

file-type.lisp (file)

Direct superclasses

error (condition)

Direct subclasses

• unbounded-problem-error (condition)
• infeasible-problem-error (condition)
• unsupported-constraint-error (condition)

Condition: unbounded-problem-error ()

Indicates the feasible region is unbounded such that the optimal objective value is infinite.

Package

linear-programming/conditions

Source

file-type.lisp (file)

Direct superclasses

solver-error (condition)

Condition: unsupported-constraint-error ()

Indicates there are unsupported constraints or properties in the given problem.

Package

linear-programming/conditions

Source

file-type.lisp (file)

Direct superclasses

solver-error (condition)

Direct methods

• solver-name (method)
• constraint (method)

Direct slots

Slot: constraint

Initargs

:constraint

Readers

constraint (generic function)

Slot: solver-name

Initargs

:solver-name

Readers

solver-name (generic function)

5.1.8 Structures

Structure: problem ()

The representation of a linear programming problem.

Package

linear-programming/problem

Source

file-type.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots

Slot: type

Type

(member max min)

Initform

(quote max)

Readers

problem-type (function)

Writers

(setf problem-type) (function)

Slot: vars

Type

(simple-array symbol (*))

Initform

#()

Readers

problem-vars (function)

Writers

(setf problem-vars) (function)

Slot: objective-var

Type

symbol

Initform

(quote #:z)

Readers

problem-objective-var (function)

Writers

(setf problem-objective-var) (function)

Slot: objective-func

Type

list

Readers

problem-objective-func (function)

Writers

(setf problem-objective-func) (function)

Slot: integer-vars

Type

list

Readers

problem-integer-vars (function)

Writers

(setf problem-integer-vars) (function)

Slot: var-bounds

Type

list

Readers

problem-var-bounds (function)

Writers

(setf problem-var-bounds) (function)

Slot: constraints

Type

list

Readers

problem-constraints (function)

Writers

(setf problem-constraints) (function)

Structure: tableau ()

Contains the necessary information for a simplex tableau.

Package

linear-programming/simplex

Source

file-type.lisp (file)

Direct superclasses

structure-object (structure)

Direct methods

• solution-reduced-cost (method)
• solution-variable (method)
• solution-objective-value (method)
• solution-problem (method)

Direct slots

Slot: problem

Type

linear-programming/problem:problem

Readers

tableau-problem (function)

Writers

(setf tableau-problem) (function)

Slot: instance-problem

Type

linear-programming/problem:problem

Readers

tableau-instance-problem (function)

Writers

(setf tableau-instance-problem) (function)

Slot: matrix

Type

(simple-array real 2)

Initform

#2a()

Readers

tableau-matrix (function)

Writers

(setf tableau-matrix) (function)

Slot: basis-columns

Type

(simple-array fixnum (*))

Initform

#()

Readers

tableau-basis-columns (function)

Writers

(setf tableau-basis-columns) (function)

Slot: var-count

Type

(and fixnum unsigned-byte)

Initform

0

Readers

tableau-var-count (function)

Writers

(setf tableau-var-count) (function)

Slot: constraint-count

Type

(and fixnum unsigned-byte)

Initform

0

Readers

tableau-constraint-count (function)

Writers

(setf tableau-constraint-count) (function)

Slot: var-mapping

Type

hash-table

Initform

(make-hash-table :test (function eq))

Readers

tableau-var-mapping (function)

Writers

(setf tableau-var-mapping) (function)

Slot: fp-tolerance-factor

Type

real

Initform

1024

Readers

tableau-fp-tolerance-factor (function)

Writers

(setf tableau-fp-tolerance-factor) (function)

5.2 Internal definitions

5.2.1 Macros

Macro: fp-inequality NAME OP EPS-MOD

Package

linear-programming/utils

Source

file-type.lisp (file)

5.2.2 Functions

Function: build-and-solve PROBLEM EXTRA-CONSTRAINTS &key FP-TOLERANCE-FACTOR

Builds and solves a tableau with the extra constrains added to the problem.

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: copy-problem INSTANCE

Package

linear-programming/problem

Source

file-type.lisp (file)

Function: find-entering-column TABLEAU

Gets the column to add to the basis.

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: find-pivoting-row TABLEAU ENTERING-COL

Gets the column that will leave the basis.

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: gen-entries TABLEAU ENTRY

Generates new entries to correct one of the integer constraints.

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: linear-constant-p EXPR

A predicate for whether a linear expression is constant.

Package

linear-programming/expressions

Source

file-type.lisp (file)

Function: make-problem &key (TYPE TYPE) (VARS VARS) (OBJECTIVE-VAR OBJECTIVE-VAR) (OBJECTIVE-FUNC OBJECTIVE-FUNC) (INTEGER-VARS INTEGER-VARS) (VAR-BOUNDS VAR-BOUNDS) (CONSTRAINTS CONSTRAINTS)

Package

linear-programming/problem

Source

file-type.lisp (file)

Function: make-tableau &key (PROBLEM PROBLEM) (INSTANCE-PROBLEM INSTANCE-PROBLEM) (MATRIX MATRIX) (BASIS-COLUMNS BASIS-COLUMNS) (VAR-COUNT VAR-COUNT) (CONSTRAINT-COUNT CONSTRAINT-COUNT) (VAR-MAPPING VAR-MAPPING) (FP-TOLERANCE-FACTOR FP-TOLERANCE-FACTOR)

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: newlinep C

Predicate if the given character is a newline or return

Package

linear-programming/external-formats

Source

file-type.lisp (file)

Function: parse-linear-constraints EXPRS

Parses the list of constraints and returns a list containing a list of simple inequalities and a list of integer variables.

Package

linear-programming/problem

Source

file-type.lisp (file)

Function: print-linear-expression STREAM EXPRESSION &optional AESTHETIC-VARIABLE-NAMES-P

Package

linear-programming/external-formats

Source

file-type.lisp (file)

Function: problem-p OBJECT

Package

linear-programming/problem

Source

file-type.lisp (file)

Function: read-until STREAM TEST &optional PREVIEW-TEST

Reads the given stream until the condition is true. ‘test‘ can either be a predicate that takes one argument, or a character to be tested using ‘char=‘.

Package

linear-programming/external-formats

Source

file-type.lisp (file)

Function: sum-linear-expressions-list EXPRS

Takes a list of linear expressions and reduces it into a single expression.

Package

linear-programming/expressions

Source

file-type.lisp (file)

Function: tableau-fp-tolerance-factor INSTANCE

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: tableau-var-mapping INSTANCE

Package

linear-programming/simplex

Source

file-type.lisp (file)

Function: violated-integer-constraint TABLEAU

Gets a variable that is required to be an integer but is currently violating that constraint.

Package

linear-programming/simplex

Source

file-type.lisp (file)

5.2.3 Generic functions

Generic Function: constraint CONDITION

Package

linear-programming/conditions

Methods

Method: constraint (CONDITION unsupported-constraint-error)

Source

file-type.lisp (file)

Generic Function: description CONDITION

Package

linear-programming/conditions

Methods

Method: description (CONDITION parsing-error)

Source

file-type.lisp (file)

Generic Function: lb CONDITION

Package

linear-programming/conditions

Methods

Method: lb (CONDITION invalid-bounds-error)

Source

file-type.lisp (file)

Generic Function: nonlinear-expression CONDITION

Package

linear-programming/conditions

Methods

Method: nonlinear-expression (CONDITION nonlinear-error)

Source

file-type.lisp (file)

Generic Function: solver-name CONDITION

Package

linear-programming/conditions

Methods

Method: solver-name (CONDITION unsupported-constraint-error)

Source

file-type.lisp (file)

Generic Function: ub CONDITION

Package

linear-programming/conditions

Methods

Method: ub (CONDITION invalid-bounds-error)

Source

file-type.lisp (file)

Generic Function: var CONDITION

Package

linear-programming/conditions

Methods

Method: var (CONDITION invalid-bounds-error)

Source

file-type.lisp (file)

5.2.4 Types

Type: lb ()

Package

linear-programming/utils

Source

file-type.lisp (file)

Type: ub ()

Package

linear-programming/utils

Source

file-type.lisp (file)

Type: var-mapping-entry ()

Represents a maping from a problem’s variable to a set of columns in the tableau.

Package

linear-programming/simplex

Source

file-type.lisp (file)

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables