The linear-programming Reference Manual

Table of Contents

Next: , Previous: , Up: (dir)   [Contents][Index]

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.


Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction

Common Lisp Linear Programming

Travis Build Status Appveyor Build status Coverage Status

MIT License GitHub release Current documentation

This is a Common Lisp library for solving linear programming problems. It is implemented in pure Common Lisp, instead of calling a high performance library. This has the advantage of being dependent on only a couple community standard libraries (ASDF, Alexandria, Iterate). However, 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

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)

Next: , Previous: , Up: Top   [Contents][Index]

2 Systems

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


Next: , Previous: , Up: Systems   [Contents][Index]

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)


Next: , Previous: , Up: Systems   [Contents][Index]

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)


Next: , Previous: , Up: Systems   [Contents][Index]

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)


Next: , Previous: , Up: Systems   [Contents][Index]

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)


Next: , Previous: , Up: Systems   [Contents][Index]

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)


Next: , Previous: , Up: Systems   [Contents][Index]

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)


Next: , Previous: , Up: Systems   [Contents][Index]

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)


Next: , Previous: , Up: Systems   [Contents][Index]

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)


Previous: , Up: Systems   [Contents][Index]

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)


Next: , Previous: , Up: Top   [Contents][Index]

3 Files

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


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.1 linear-programming.asd

Location

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

Systems

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.2 linear-programming/all/lisp.lisp

Parent

linear-programming/all (system)

Location

all.lisp

Packages

linear-programming/all


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.3 linear-programming/solver/lisp.lisp

Parent

linear-programming/solver (system)

Location

solver.lisp

Packages

linear-programming/solver

Exported Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

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

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.5 linear-programming/simplex/lisp.lisp

Parent

linear-programming/simplex (system)

Location

simplex.lisp

Packages

linear-programming/simplex

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.6 linear-programming/problem/lisp.lisp

Parent

linear-programming/problem (system)

Location

problem.lisp

Packages

linear-programming/problem

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

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)


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.8 linear-programming/utils/lisp.lisp

Parent

linear-programming/utils (system)

Location

utils.lisp

Packages

linear-programming/utils

Exported Definitions
Internal Definitions

Previous: , Up: Lisp files   [Contents][Index]

3.1.9 linear-programming/conditions/lisp.lisp

Parent

linear-programming/conditions (system)

Location

conditions.lisp

Packages

linear-programming/conditions

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

4 Packages

Packages are listed by definition order.


Next: , Previous: , Up: Packages   [Contents][Index]

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

Next: , Previous: , Up: Packages   [Contents][Index]

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

Next: , Previous: , Up: Packages   [Contents][Index]

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

Next: , Previous: , Up: Packages   [Contents][Index]

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

Next: , Previous: , Up: Packages   [Contents][Index]

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

Next: , Previous: , Up: Packages   [Contents][Index]

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)


Next: , Previous: , Up: Packages   [Contents][Index]

4.7 linear-programming/utils

Various internal utilities

Source

lisp.lisp (file)

Use List

common-lisp

Exported Definitions
Internal Definitions

Previous: , Up: Packages   [Contents][Index]

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

Next: , Previous: , Up: Top   [Contents][Index]

5 Definitions

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


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

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)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

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)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

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)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

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

Next: , Previous: , Up: Exported definitions   [Contents][Index]

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)


Previous: , Up: Exported definitions   [Contents][Index]

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)


Previous: , Up: Definitions   [Contents][Index]

5.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

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)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

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)


Previous: , Up: Internal definitions   [Contents][Index]

5.2.3 Types

Type: lb ()
Package

linear-programming/utils

Source

lisp.lisp (file)

Type: ub ()
Package

linear-programming/utils

Source

lisp.lisp (file)


Previous: , Up: Top   [Contents][Index]

Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Jump to:   F   L  
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

Jump to:   F   L  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   B   C   D   F   G   L   M   N   P   R   S   T   U   V   W  
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

Jump to:   B   C   D   F   G   L   M   N   P   R   S   T   U   V   W  

Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables

Jump to:   *  
B   C   D   E   I   L   M   O   P   S   T   U   V  
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

Jump to:   *  
B   C   D   E   I   L   M   O   P   S   T   U   V  

Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   C   I   L   N   P   S   T   U  
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

Jump to:   C   I   L   N   P   S   T   U