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

• 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

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

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

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

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

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

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

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

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

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

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

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

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

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

• *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/lisp.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)

Internal Definitions

• newlinep (function)
• read-until (function)

3.1.5 linear-programming/simplex/lisp.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-var-mapping (function)
• violated-integer-constraint (function)

3.1.6 linear-programming/problem/lisp.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/lisp.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)

3.1.8 linear-programming/utils/lisp.lisp

Parent

linear-programming/utils (system)

Location

utils.lisp

Packages

linear-programming/utils

Exported Definitions

• lb-max (function)
• lb-min (function)
• ub-max (function)
• ub-min (function)
• validate-bounds (function)

Internal Definitions

• lb (type)
• ub (type)

3.1.9 linear-programming/conditions/lisp.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)

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

• 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

lisp.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

lisp.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)

Internal Definitions

• newlinep (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

lisp.lisp (file)

Use List

• 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-var-mapping (function)
• violated-integer-constraint (function)

4.5 linear-programming/problem

Handles the representation of linear programming problems.

Source

lisp.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

lisp.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)

4.7 linear-programming/utils

Various internal utilities

Source

lisp.lisp (file)

Use List

common-lisp

Exported Definitions

• lb-max (function)
• lb-min (function)
• ub-max (function)
• ub-min (function)
• validate-bounds (function)

Internal Definitions

• lb (type)
• ub (type)

4.8 linear-programming/conditions

Contains the various conditions used by this library.

Source

lisp.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)

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

• 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

lisp.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

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

• 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.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

• 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 * (*))

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

A.2 Functions

A.3 Variables

A.4 Data types