The linear-programming Reference Manual
Table of Contents
The linear-programming Reference Manual
This is the linear-programming Reference Manual, version 2.0.0,
generated automatically by Declt version 3.0 "Montgomery Scott"
on Mon Dec 02 10:38:34 2019 GMT+0.
1 Introduction
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, this 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 modular.
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 solution 'x))
(format t "y = ~A (reduced cost: ~A)~%" y (reduced-cost solution 'y))
(format t "z = ~A (reduced cost: ~A)~%" z (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)
(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 solution 'x))
(format t "y = ~A (reduced cost: ~A)~%" y (reduced-cost solution 'y))
(format t "z = ~A (reduced cost: ~A)~%" z (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)
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.0.0
- Dependencies
-
- 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
-
- Source
linear-programming.asd (file)
- Component
lisp.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
-
- Source
linear-programming.asd (file)
- Component
lisp.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
-
- Source
linear-programming.asd (file)
- Component
lisp.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
-
- Source
linear-programming.asd (file)
- Component
lisp.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
-
- Source
linear-programming.asd (file)
- Component
lisp.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
-
- Source
linear-programming.asd (file)
- Component
lisp.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
- Dependency
linear-programming/conditions (system)
- Source
linear-programming.asd (file)
- Component
lisp.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
lisp.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-20191130-git/linear-programming.asd
- Systems
-
3.1.2 linear-programming/all/lisp.lisp
- Parent
linear-programming/all (system)
- Location
all.lisp
- Packages
linear-programming/all
3.1.3 linear-programming/solver/lisp.lisp
- Parent
linear-programming/solver (system)
- Location
solver.lisp
- Packages
linear-programming/solver
- Exported Definitions
-
3.1.4 linear-programming/external-formats/lisp.lisp
- Parent
linear-programming/external-formats (system)
- Location
external-formats.lisp
- Packages
linear-programming/external-formats
- Exported Definitions
-
- Internal Definitions
-
3.1.5 linear-programming/simplex/lisp.lisp
- Parent
linear-programming/simplex (system)
- Location
simplex.lisp
- Packages
linear-programming/simplex
- Exported Definitions
-
- Internal Definitions
-
3.1.6 linear-programming/problem/lisp.lisp
- Parent
linear-programming/problem (system)
- Location
problem.lisp
- Packages
linear-programming/problem
- Exported Definitions
-
- Internal Definitions
-
3.1.7 linear-programming/expressions/lisp.lisp
- Parent
linear-programming/expressions (system)
- Location
expressions.lisp
- Packages
linear-programming/expressions
- Exported Definitions
-
- Internal Definitions
linear-constant-p (function)
3.1.8 linear-programming/utils/lisp.lisp
- Parent
linear-programming/utils (system)
- Location
utils.lisp
- Packages
linear-programming/utils
- Exported Definitions
-
- Internal Definitions
-
3.1.9 linear-programming/conditions/lisp.lisp
- Parent
linear-programming/conditions (system)
- Location
conditions.lisp
- Packages
linear-programming/conditions
- Exported Definitions
-
- Internal Definitions
-
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
lisp.lisp (file)
- Nickname
linear-programming
- Use List
-
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
lisp.lisp (file)
- Use List
-
- Used By List
linear-programming/all
- Exported Definitions
-
4.3 linear-programming/external-formats
Handles reading and writing problems to external formats.
- Source
lisp.lisp (file)
- Use List
-
- Used By List
linear-programming/all
- Exported Definitions
-
- Internal Definitions
-
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
lisp.lisp (file)
- Use List
-
- Exported Definitions
-
- Internal Definitions
-
4.5 linear-programming/problem
Handles the representation of linear programming problems.
- Source
lisp.lisp (file)
- Use List
-
- Used By List
-
- Exported Definitions
-
- Internal Definitions
-
4.6 linear-programming/expressions
Contains functions for processing linear expressions.
- Source
lisp.lisp (file)
- Use List
-
- Used By List
linear-programming/problem
- Exported Definitions
-
- Internal Definitions
linear-constant-p (function)
4.7 linear-programming/utils
Various internal utilities
- Source
lisp.lisp (file)
- Use List
common-lisp
- Exported Definitions
-
- Internal Definitions
-
4.8 linear-programming/conditions
Contains the various conditions used by this library.
- Source
lisp.lisp (file)
- Use List
common-lisp
- Used By List
-
- Exported Definitions
-
- Internal Definitions
-
5 Definitions
Definitions are sorted by export status, category, package, and then by
lexicographic order.
5.1 Exported definitions
5.1.1 Special variables
- Special Variable: *solver*
-
The function that should be used by solve-problem. 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
lisp.lisp (file)
5.1.2 Macros
- Macro: make-linear-problem OBJECTIVE &rest CONSTRAINTS
-
Creates a linear problem from the expressions in the body
- Package
linear-programming/problem
- Source
lisp.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
lisp.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
lisp.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
lisp.lisp (file)
5.1.3 Functions
- Function: build-tableau PROBLEM &optional INSTANCE-PROBLEM
-
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
lisp.lisp (file)
- Function: copy-tableau TABLEAU
-
Copies the given tableau and it’s matrix.
- Package
linear-programming/simplex
- Source
lisp.lisp (file)
- Function: format-linear-expression ALIST
-
Formats a linear expression as a sexp.
- Package
linear-programming/expressions
- Source
lisp.lisp (file)
- Function: lb-max X Y
-
Computes the maximum value where nil is negative infinity
- Package
linear-programming/utils
- Source
lisp.lisp (file)
- Function: lb-min X Y
-
Computes the minimum value where nil is negative infinity
- Package
linear-programming/utils
- Source
lisp.lisp (file)
- Function: n-pivot-row TABLEAU ENTERING-COL CHANGING-ROW
-
Destructively applies a single pivot to the table.
- Package
linear-programming/simplex
- Source
lisp.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
lisp.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
lisp.lisp (file)
- Function: parse-linear-problem OBJECTIVE-EXP CONSTRAINTS
-
Parses the expressions into a linear programming problem
- Package
linear-programming/problem
- Source
lisp.lisp (file)
- Function: pivot-row TABLEAU ENTERING-COL CHANGING-ROW
-
Non-destructively applies a single pivot to the table.
- Package
linear-programming/simplex
- Source
lisp.lisp (file)
- Function: problem-constraints INSTANCE
-
A list of (in)equality constraints.
- Package
linear-programming/problem
- Source
lisp.lisp (file)
- Function: problem-integer-vars INSTANCE
-
A list of variables with integer constraints.
- Package
linear-programming/problem
- Source
lisp.lisp (file)
- Function: problem-objective-func INSTANCE
-
The objective function as a linear expression alist.
- Package
linear-programming/problem
- Source
lisp.lisp (file)
- Function: problem-objective-var INSTANCE
-
The name of the objective function.
- Package
linear-programming/problem
- Source
lisp.lisp (file)
- Function: problem-type INSTANCE
-
Whether the problem is a ‘min‘ or ‘max‘ problem.
- Package
linear-programming/problem
- Source
lisp.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
lisp.lisp (file)
- Function: problem-vars INSTANCE
-
An array of the variables specified in the problem.
- Package
linear-programming/problem
- Source
lisp.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
lisp.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
lisp.lisp (file)
- Function: scale-linear-expression EXPR SCALAR
-
Multiplies the linear expression by the given scalar.
- Package
linear-programming/expressions
- Source
lisp.lisp (file)
- Function: simplex-solver PROBLEM
-
The solver interface function for the simplex backend.
- Package
linear-programming/simplex
- Source
lisp.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
lisp.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
lisp.lisp (file)
- Function: sum-linear-expressions &rest EXPRS
-
Takes a list of linear expressions and reduces it into a single expression.
- Package
linear-programming/expressions
- Source
lisp.lisp (file)
- Function: tableau-basis-columns INSTANCE
-
- Package
linear-programming/simplex
- Source
lisp.lisp (file)
- Function: tableau-constraint-count INSTANCE
-
- Package
linear-programming/simplex
- Source
lisp.lisp (file)
- Function: tableau-instance-problem INSTANCE
-
- Package
linear-programming/simplex
- Source
lisp.lisp (file)
- Function: tableau-matrix INSTANCE
-
- Package
linear-programming/simplex
- Source
lisp.lisp (file)
- Function: tableau-objective-value TABLEAU
-
Gets the objective function value in the tableau.
- Package
linear-programming/simplex
- Source
lisp.lisp (file)
- Function: tableau-p OBJECT
-
- Package
linear-programming/simplex
- Source
lisp.lisp (file)
- Function: tableau-problem INSTANCE
-
- Package
linear-programming/simplex
- Source
lisp.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
lisp.lisp (file)
- Function: tableau-var-count INSTANCE
-
- Package
linear-programming/simplex
- Source
lisp.lisp (file)
- Function: tableau-variable TABLEAU VAR
-
Gets the value of the given variable from the tableau
- Package
linear-programming/simplex
- Source
lisp.lisp (file)
- Function: ub-max X Y
-
Computes the maximum value where nil is positive infinity
- Package
linear-programming/utils
- Source
lisp.lisp (file)
- Function: ub-min X Y
-
Computes the minimum value where nil is positive infinity
- Package
linear-programming/utils
- Source
lisp.lisp (file)
- Function: validate-bounds LB UB VAR
-
Checks that the bounds represent a non empty range
- Package
linear-programming/utils
- Source
lisp.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
lisp.lisp (file)
5.1.4 Generic functions
- Generic Function: solution-objective-value SOLUTION
-
Gets the value of the objective function.
- Package
linear-programming/solver
- Source
lisp.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
lisp.lisp (file)
- Methods
- Method: solution-problem (SOLUTION tableau)
-
- Generic Function: solution-reduced-cost SOLUTION VARIABLE
-
Gets the reduced cost (i.e. the shadow price for the lower bound) of the
specified variable.
- Package
linear-programming/solver
- Source
lisp.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
lisp.lisp (file)
- Methods
- Method: solution-variable (SOLUTION tableau) VARIABLE
-
5.1.5 Conditions
- Condition: infeasible-integer-constraints-error ()
-
Indicates that there is no feasible region due to the integer constraints.
- Package
linear-programming/conditions
- Source
lisp.lisp (file)
- Direct superclasses
infeasible-problem-error (condition)
- Condition: infeasible-problem-error ()
-
Indicates the there is no feasible region.
- Package
linear-programming/conditions
- Source
lisp.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
lisp.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
lisp.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
lisp.lisp (file)
- Direct superclasses
error (condition)
- Direct subclasses
-
- 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
lisp.lisp (file)
- Direct superclasses
error (condition)
- Direct subclasses
-
- Condition: unbounded-problem-error ()
-
Indicates the feasible region is unbounded such that the optimal objective value
is infinite.
- Package
linear-programming/conditions
- Source
lisp.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
lisp.lisp (file)
- Direct superclasses
solver-error (condition)
- Direct methods
-
- Direct slots
- Slot: constraint
-
- Initargs
:constraint
- Readers
constraint (generic function)
- Slot: solver-name
-
- Initargs
:solver-name
- Readers
solver-name (generic function)
5.1.6 Structures
- Structure: problem ()
-
The representation of a linear programming problem.
- Package
linear-programming/problem
- Source
lisp.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
(vector 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
lisp.lisp (file)
- Direct superclasses
structure-object (structure)
- Direct methods
-
- 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 * (*))
- Initform
#()
- Readers
tableau-basis-columns (function)
- Writers
(setf tableau-basis-columns) (function)
- Slot: var-count
-
- Type
(integer 0 *)
- Initform
0
- Readers
tableau-var-count (function)
- Writers
(setf tableau-var-count) (function)
- Slot: constraint-count
-
- Type
(integer 0 *)
- 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)
5.2 Internal definitions
5.2.1 Functions
- Function: build-and-solve PROBLEM EXTRA-CONSTRAINTS
-
Builds and solves a tableau with the extra constrains added to the problem.
- Package
linear-programming/simplex
- Source
lisp.lisp (file)
- Function: copy-problem INSTANCE
-
- Package
linear-programming/problem
- Source
lisp.lisp (file)
- Function: find-entering-column TABLEAU
-
Gets the column to add to the basis.
- Package
linear-programming/simplex
- Source
lisp.lisp (file)
- Function: find-pivoting-row TABLEAU ENTERING-COL
-
Gets the column that will leave the basis.
- Package
linear-programming/simplex
- Source
lisp.lisp (file)
- Function: gen-entries TABLEAU ENTRY
-
Generates new entries to correct one of the integer constraints.
- Package
linear-programming/simplex
- Source
lisp.lisp (file)
- Function: linear-constant-p EXPR
-
A predicate for whether a linear expression is constant.
- Package
linear-programming/expressions
- Source
lisp.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
lisp.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)
-
- Package
linear-programming/simplex
- Source
lisp.lisp (file)
- Function: newlinep C
-
Predicate if the given character is a newline or return
- Package
linear-programming/external-formats
- Source
lisp.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
lisp.lisp (file)
- Function: problem-p OBJECT
-
- Package
linear-programming/problem
- Source
lisp.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
lisp.lisp (file)
- Function: tableau-var-mapping INSTANCE
-
- Package
linear-programming/simplex
- Source
lisp.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
lisp.lisp (file)
5.2.2 Generic functions
- Generic Function: constraint CONDITION
-
- Package
linear-programming/conditions
- Methods
- Method: constraint (CONDITION unsupported-constraint-error)
-
- Source
lisp.lisp (file)
- Generic Function: description CONDITION
-
- Package
linear-programming/conditions
- Methods
- Method: description (CONDITION parsing-error)
-
- Source
lisp.lisp (file)
- Generic Function: lb CONDITION
-
- Package
linear-programming/conditions
- Methods
- Method: lb (CONDITION invalid-bounds-error)
-
- Source
lisp.lisp (file)
- Generic Function: nonlinear-expression CONDITION
-
- Package
linear-programming/conditions
- Methods
- Method: nonlinear-expression (CONDITION nonlinear-error)
-
- Source
lisp.lisp (file)
- Generic Function: solver-name CONDITION
-
- Package
linear-programming/conditions
- Methods
- Method: solver-name (CONDITION unsupported-constraint-error)
-
- Source
lisp.lisp (file)
- Generic Function: ub CONDITION
-
- Package
linear-programming/conditions
- Methods
- Method: ub (CONDITION invalid-bounds-error)
-
- Source
lisp.lisp (file)
- Generic Function: var CONDITION
-
- Package
linear-programming/conditions
- Methods
- Method: var (CONDITION invalid-bounds-error)
-
- Source
lisp.lisp (file)
5.2.3 Types
- Type: lb ()
-
- Package
linear-programming/utils
- Source
lisp.lisp (file)
- Type: ub ()
-
- Package
linear-programming/utils
- Source
lisp.lisp (file)
Appendix A Indexes
A.1 Concepts
| Index Entry | | Section |
|
F | | |
| File, Lisp, linear-programming.asd: | | The linear-programming․asd file |
| File, Lisp, linear-programming/all/lisp.lisp: | | The linear-programming/all/lisp․lisp file |
| File, Lisp, linear-programming/conditions/lisp.lisp: | | The linear-programming/conditions/lisp․lisp file |
| File, Lisp, linear-programming/expressions/lisp.lisp: | | The linear-programming/expressions/lisp․lisp file |
| File, Lisp, linear-programming/external-formats/lisp.lisp: | | The linear-programming/external-formats/lisp․lisp file |
| File, Lisp, linear-programming/problem/lisp.lisp: | | The linear-programming/problem/lisp․lisp file |
| File, Lisp, linear-programming/simplex/lisp.lisp: | | The linear-programming/simplex/lisp․lisp file |
| File, Lisp, linear-programming/solver/lisp.lisp: | | The linear-programming/solver/lisp․lisp file |
| File, Lisp, linear-programming/utils/lisp.lisp: | | The linear-programming/utils/lisp․lisp file |
|
L | | |
| linear-programming.asd: | | The linear-programming․asd file |
| linear-programming/all/lisp.lisp: | | The linear-programming/all/lisp․lisp file |
| linear-programming/conditions/lisp.lisp: | | The linear-programming/conditions/lisp․lisp file |
| linear-programming/expressions/lisp.lisp: | | The linear-programming/expressions/lisp․lisp file |
| linear-programming/external-formats/lisp.lisp: | | The linear-programming/external-formats/lisp․lisp file |
| linear-programming/problem/lisp.lisp: | | The linear-programming/problem/lisp․lisp file |
| linear-programming/simplex/lisp.lisp: | | The linear-programming/simplex/lisp․lisp file |
| linear-programming/solver/lisp.lisp: | | The linear-programming/solver/lisp․lisp file |
| linear-programming/utils/lisp.lisp: | | The linear-programming/utils/lisp․lisp file |
| Lisp File, linear-programming.asd: | | The linear-programming․asd file |
| Lisp File, linear-programming/all/lisp.lisp: | | The linear-programming/all/lisp․lisp file |
| Lisp File, linear-programming/conditions/lisp.lisp: | | The linear-programming/conditions/lisp․lisp file |
| Lisp File, linear-programming/expressions/lisp.lisp: | | The linear-programming/expressions/lisp․lisp file |
| Lisp File, linear-programming/external-formats/lisp.lisp: | | The linear-programming/external-formats/lisp․lisp file |
| Lisp File, linear-programming/problem/lisp.lisp: | | The linear-programming/problem/lisp․lisp file |
| Lisp File, linear-programming/simplex/lisp.lisp: | | The linear-programming/simplex/lisp․lisp file |
| Lisp File, linear-programming/solver/lisp.lisp: | | The linear-programming/solver/lisp․lisp file |
| Lisp File, linear-programming/utils/lisp.lisp: | | The linear-programming/utils/lisp․lisp file |
|
A.2 Functions
| Index Entry | | Section |
|
B | | |
| build-and-solve : | | Internal functions |
| build-tableau : | | Exported functions |
|
C | | |
| constraint : | | Internal generic functions |
| constraint : | | Internal generic functions |
| copy-problem : | | Internal functions |
| copy-tableau : | | Exported functions |
|
D | | |
| description : | | Internal generic functions |
| description : | | Internal generic functions |
|
F | | |
| find-entering-column : | | Internal functions |
| find-pivoting-row : | | Internal functions |
| format-linear-expression : | | Exported functions |
| Function, build-and-solve : | | Internal functions |
| Function, build-tableau : | | Exported functions |
| Function, copy-problem : | | Internal functions |
| Function, copy-tableau : | | Exported functions |
| Function, find-entering-column : | | Internal functions |
| Function, find-pivoting-row : | | Internal functions |
| Function, format-linear-expression : | | Exported functions |
| Function, gen-entries : | | Internal functions |
| Function, lb-max : | | Exported functions |
| Function, lb-min : | | Exported functions |
| Function, linear-constant-p : | | Internal functions |
| Function, make-problem : | | Internal functions |
| Function, make-tableau : | | Internal functions |
| Function, n-pivot-row : | | Exported functions |
| Function, n-solve-tableau : | | Exported functions |
| Function, newlinep : | | Internal functions |
| Function, parse-linear-constraints : | | Internal functions |
| Function, parse-linear-expression : | | Exported functions |
| Function, parse-linear-problem : | | Exported functions |
| Function, pivot-row : | | Exported functions |
| Function, problem-constraints : | | Exported functions |
| Function, problem-integer-vars : | | Exported functions |
| Function, problem-objective-func : | | Exported functions |
| Function, problem-objective-var : | | Exported functions |
| Function, problem-p : | | Internal functions |
| Function, problem-type : | | Exported functions |
| Function, problem-var-bounds : | | Exported functions |
| Function, problem-vars : | | Exported functions |
| Function, read-mps : | | Exported functions |
| Function, read-sexp : | | Exported functions |
| Function, read-until : | | Internal functions |
| Function, scale-linear-expression : | | Exported functions |
| Function, simplex-solver : | | Exported functions |
| Function, solve-problem : | | Exported functions |
| Function, solve-tableau : | | Exported functions |
| Function, sum-linear-expressions : | | Exported functions |
| Function, tableau-basis-columns : | | Exported functions |
| Function, tableau-constraint-count : | | Exported functions |
| Function, tableau-instance-problem : | | Exported functions |
| Function, tableau-matrix : | | Exported functions |
| Function, tableau-objective-value : | | Exported functions |
| Function, tableau-p : | | Exported functions |
| Function, tableau-problem : | | Exported functions |
| Function, tableau-reduced-cost : | | Exported functions |
| Function, tableau-var-count : | | Exported functions |
| Function, tableau-var-mapping : | | Internal functions |
| Function, tableau-variable : | | Exported functions |
| Function, ub-max : | | Exported functions |
| Function, ub-min : | | Exported functions |
| Function, validate-bounds : | | Exported functions |
| Function, violated-integer-constraint : | | Internal functions |
| Function, write-sexp : | | Exported functions |
|
G | | |
| gen-entries : | | Internal functions |
| Generic Function, constraint : | | Internal generic functions |
| Generic Function, description : | | Internal generic functions |
| Generic Function, lb : | | Internal generic functions |
| Generic Function, nonlinear-expression : | | Internal generic functions |
| Generic Function, solution-objective-value : | | Exported generic functions |
| Generic Function, solution-problem : | | Exported generic functions |
| Generic Function, solution-reduced-cost : | | Exported generic functions |
| Generic Function, solution-variable : | | Exported generic functions |
| Generic Function, solver-name : | | Internal generic functions |
| Generic Function, ub : | | Internal generic functions |
| Generic Function, var : | | Internal generic functions |
|
L | | |
| lb : | | Internal generic functions |
| lb : | | Internal generic functions |
| lb-max : | | Exported functions |
| lb-min : | | Exported functions |
| linear-constant-p : | | Internal functions |
|
M | | |
| Macro, make-linear-problem : | | Exported macros |
| Macro, with-solution-variables : | | Exported macros |
| Macro, with-solved-problem : | | Exported macros |
| Macro, with-tableau-variables : | | Exported macros |
| make-linear-problem : | | Exported macros |
| make-problem : | | Internal functions |
| make-tableau : | | Internal functions |
| Method, constraint : | | Internal generic functions |
| Method, description : | | Internal generic functions |
| Method, lb : | | Internal generic functions |
| Method, nonlinear-expression : | | Internal generic functions |
| Method, solution-objective-value : | | Exported generic functions |
| Method, solution-problem : | | Exported generic functions |
| Method, solution-reduced-cost : | | Exported generic functions |
| Method, solution-variable : | | Exported generic functions |
| Method, solver-name : | | Internal generic functions |
| Method, ub : | | Internal generic functions |
| Method, var : | | Internal generic functions |
|
N | | |
| n-pivot-row : | | Exported functions |
| n-solve-tableau : | | Exported functions |
| newlinep : | | Internal functions |
| nonlinear-expression : | | Internal generic functions |
| nonlinear-expression : | | Internal generic functions |
|
P | | |
| parse-linear-constraints : | | Internal functions |
| parse-linear-expression : | | Exported functions |
| parse-linear-problem : | | Exported functions |
| pivot-row : | | Exported functions |
| problem-constraints : | | Exported functions |
| problem-integer-vars : | | Exported functions |
| problem-objective-func : | | Exported functions |
| problem-objective-var : | | Exported functions |
| problem-p : | | Internal functions |
| problem-type : | | Exported functions |
| problem-var-bounds : | | Exported functions |
| problem-vars : | | Exported functions |
|
R | | |
| read-mps : | | Exported functions |
| read-sexp : | | Exported functions |
| read-until : | | Internal functions |
|
S | | |
| scale-linear-expression : | | Exported functions |
| simplex-solver : | | Exported functions |
| solution-objective-value : | | Exported generic functions |
| solution-objective-value : | | Exported generic functions |
| solution-problem : | | Exported generic functions |
| solution-problem : | | Exported generic functions |
| solution-reduced-cost : | | Exported generic functions |
| solution-reduced-cost : | | Exported generic functions |
| solution-variable : | | Exported generic functions |
| solution-variable : | | Exported generic functions |
| solve-problem : | | Exported functions |
| solve-tableau : | | Exported functions |
| solver-name : | | Internal generic functions |
| solver-name : | | Internal generic functions |
| sum-linear-expressions : | | Exported functions |
|
T | | |
| tableau-basis-columns : | | Exported functions |
| tableau-constraint-count : | | Exported functions |
| tableau-instance-problem : | | Exported functions |
| tableau-matrix : | | Exported functions |
| tableau-objective-value : | | Exported functions |
| tableau-p : | | Exported functions |
| tableau-problem : | | Exported functions |
| tableau-reduced-cost : | | Exported functions |
| tableau-var-count : | | Exported functions |
| tableau-var-mapping : | | Internal functions |
| tableau-variable : | | Exported functions |
|
U | | |
| ub : | | Internal generic functions |
| ub : | | Internal generic functions |
| ub-max : | | Exported functions |
| ub-min : | | Exported functions |
|
V | | |
| validate-bounds : | | Exported functions |
| var : | | Internal generic functions |
| var : | | Internal generic functions |
| violated-integer-constraint : | | Internal functions |
|
W | | |
| with-solution-variables : | | Exported macros |
| with-solved-problem : | | Exported macros |
| with-tableau-variables : | | Exported macros |
| write-sexp : | | Exported functions |
|
A.3 Variables
| Index Entry | | Section |
|
* | | |
| *solver* : | | Exported special variables |
|
B | | |
| basis-columns : | | Exported structures |
|
C | | |
| constraint : | | Exported conditions |
| constraint-count : | | Exported structures |
| constraints : | | Exported structures |
|
D | | |
| description : | | Exported conditions |
|
E | | |
| expression : | | Exported conditions |
|
I | | |
| instance-problem : | | Exported structures |
| integer-vars : | | Exported structures |
|
L | | |
| lb : | | Exported conditions |
|
M | | |
| matrix : | | Exported structures |
|
O | | |
| objective-func : | | Exported structures |
| objective-var : | | Exported structures |
|
P | | |
| problem : | | Exported structures |
|
S | | |
| Slot, basis-columns : | | Exported structures |
| Slot, constraint : | | Exported conditions |
| Slot, constraint-count : | | Exported structures |
| Slot, constraints : | | Exported structures |
| Slot, description : | | Exported conditions |
| Slot, expression : | | Exported conditions |
| Slot, instance-problem : | | Exported structures |
| Slot, integer-vars : | | Exported structures |
| Slot, lb : | | Exported conditions |
| Slot, matrix : | | Exported structures |
| Slot, objective-func : | | Exported structures |
| Slot, objective-var : | | Exported structures |
| Slot, problem : | | Exported structures |
| Slot, solver-name : | | Exported conditions |
| Slot, type : | | Exported structures |
| Slot, ub : | | Exported conditions |
| Slot, var : | | Exported conditions |
| Slot, var-bounds : | | Exported structures |
| Slot, var-count : | | Exported structures |
| Slot, var-mapping : | | Exported structures |
| Slot, vars : | | Exported structures |
| solver-name : | | Exported conditions |
| Special Variable, *solver* : | | Exported special variables |
|
T | | |
| type : | | Exported structures |
|
U | | |
| ub : | | Exported conditions |
|
V | | |
| var : | | Exported conditions |
| var-bounds : | | Exported structures |
| var-count : | | Exported structures |
| var-mapping : | | Exported structures |
| vars : | | Exported structures |
|
A.4 Data types
| Index Entry | | Section |
|
C | | |
| Condition, infeasible-integer-constraints-error : | | Exported conditions |
| Condition, infeasible-problem-error : | | Exported conditions |
| Condition, invalid-bounds-error : | | Exported conditions |
| Condition, nonlinear-error : | | Exported conditions |
| Condition, parsing-error : | | Exported conditions |
| Condition, solver-error : | | Exported conditions |
| Condition, unbounded-problem-error : | | Exported conditions |
| Condition, unsupported-constraint-error : | | Exported conditions |
|
I | | |
| infeasible-integer-constraints-error : | | Exported conditions |
| infeasible-problem-error : | | Exported conditions |
| invalid-bounds-error : | | Exported conditions |
|
L | | |
| lb : | | Internal types |
| linear-programming : | | The linear-programming system |
| linear-programming/all : | | The linear-programming/all system |
| linear-programming/all : | | The linear-programming/all package |
| linear-programming/conditions : | | The linear-programming/conditions system |
| linear-programming/conditions : | | The linear-programming/conditions package |
| linear-programming/expressions : | | The linear-programming/expressions system |
| linear-programming/expressions : | | The linear-programming/expressions package |
| linear-programming/external-formats : | | The linear-programming/external-formats system |
| linear-programming/external-formats : | | The linear-programming/external-formats package |
| linear-programming/problem : | | The linear-programming/problem system |
| linear-programming/problem : | | The linear-programming/problem package |
| linear-programming/simplex : | | The linear-programming/simplex system |
| linear-programming/simplex : | | The linear-programming/simplex package |
| linear-programming/solver : | | The linear-programming/solver system |
| linear-programming/solver : | | The linear-programming/solver package |
| linear-programming/utils : | | The linear-programming/utils system |
| linear-programming/utils : | | The linear-programming/utils package |
|
N | | |
| nonlinear-error : | | Exported conditions |
|
P | | |
| Package, linear-programming/all : | | The linear-programming/all package |
| Package, linear-programming/conditions : | | The linear-programming/conditions package |
| Package, linear-programming/expressions : | | The linear-programming/expressions package |
| Package, linear-programming/external-formats : | | The linear-programming/external-formats package |
| Package, linear-programming/problem : | | The linear-programming/problem package |
| Package, linear-programming/simplex : | | The linear-programming/simplex package |
| Package, linear-programming/solver : | | The linear-programming/solver package |
| Package, linear-programming/utils : | | The linear-programming/utils package |
| parsing-error : | | Exported conditions |
| problem : | | Exported structures |
|
S | | |
| solver-error : | | Exported conditions |
| Structure, problem : | | Exported structures |
| Structure, tableau : | | Exported structures |
| System, linear-programming : | | The linear-programming system |
| System, linear-programming/all : | | The linear-programming/all system |
| System, linear-programming/conditions : | | The linear-programming/conditions system |
| System, linear-programming/expressions : | | The linear-programming/expressions system |
| System, linear-programming/external-formats : | | The linear-programming/external-formats system |
| System, linear-programming/problem : | | The linear-programming/problem system |
| System, linear-programming/simplex : | | The linear-programming/simplex system |
| System, linear-programming/solver : | | The linear-programming/solver system |
| System, linear-programming/utils : | | The linear-programming/utils system |
|
T | | |
| tableau : | | Exported structures |
| Type, lb : | | Internal types |
| Type, ub : | | Internal types |
|
U | | |
| ub : | | Internal types |
| unbounded-problem-error : | | Exported conditions |
| unsupported-constraint-error : | | Exported conditions |
|