# The linear-programming Reference Manual

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

# The linear-programming Reference Manual

This is the linear-programming Reference Manual, version 2.1.1, generated automatically by Declt version 3.0 "Montgomery Scott" on Sun May 15 05:10:05 2022 GMT+0.

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

# Common Lisp Linear Programming

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

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

## Installation

The linear-programming library is avalible in both the main Quicklisp distribution and Ultralisp, so it can loaded with with `(ql:quickload :linear-programming)`. You can check that it works by running `(asdf:test-system :linear-programming)`.

If you are not using Quicklisp, place this repository, Alexandria, and Iterate somewhere where ASDF can find them. Then, it can be loaded with `(asdf:load-system :linear-programming)` and tested as above.

## Usage

See neil-lindquist.github.io/linear-programming/ for further documentation.

Consider the following linear programming problem.

maximize x + 4y + 3z
such that

• 2x + y ≤ 8
• y + z ≤ 7
• x, y, z ≥ 0

First, the problem needs to be specified. Problems are specified with a simple DSL, as described in the syntax reference.

``````(use-package :linear-programming)

(defvar problem (parse-linear-problem '(max (= w (+ x (* 4 y) (* 3 z))))
'((<= (+ (* 2 x) y) 8)
(<= (+ y z) 7))))
``````

Once the problem is created, it can be solved with the simplex method.

``````(defvar solution (solve-problem problem))
``````

Finally, the optimal tableau can be inspected to get the resulting objective function, decision variables, and reduced-costs (i.e. the shadow prices for the variable's lower bounds).

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

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

Alternatively, the `with-solution-variables` and `with-solved-problem` macros simplify some steps and binds the solution variables in their bodies.

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

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

(with-solved-problem ((max (= w (+ x (* 4 y) (* 3 z))))
(<= (+ (* 2 x) y) 8)
(<= (+ y z) 7))
(format t "Objective value solution: ~A~%" w)
(format t "x = ~A (reduced cost: ~A)~%" x (reduced-cost x))
(format t "y = ~A (reduced cost: ~A)~%" y (reduced-cost y))
(format t "z = ~A (reduced cost: ~A)~%" z (reduced-cost z)))

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

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
Source Control

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

Bug Tracker

MIT

Description

A library for solving linear programming problems

Version

2.1.1

Dependencies
Source

linear-programming.asd (file)

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

### 2.2 linear-programming/all

Author

Neil Lindquist <NeilLindquist5@gmail.com>

Contact
Source Control

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

Bug Tracker

MIT

Dependencies
Source

linear-programming.asd (file)

Component

file-type.lisp (file)

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

### 2.3 linear-programming/solver

Author

Neil Lindquist <NeilLindquist5@gmail.com>

Contact
Source Control

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

Bug Tracker

MIT

Dependencies
Source

linear-programming.asd (file)

Component

file-type.lisp (file)

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

### 2.4 linear-programming/external-formats

Author

Neil Lindquist <NeilLindquist5@gmail.com>

Contact
Source Control

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

Bug Tracker

MIT

Dependencies
Source

linear-programming.asd (file)

Component

file-type.lisp (file)

### 2.5 linear-programming/simplex

Author

Neil Lindquist <NeilLindquist5@gmail.com>

Contact
Source Control

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

Bug Tracker

MIT

Dependencies
Source

linear-programming.asd (file)

Component

file-type.lisp (file)

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

### 2.6 linear-programming/problem

Author

Neil Lindquist <NeilLindquist5@gmail.com>

Contact
Source Control

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

Bug Tracker

MIT

Dependencies
Source

linear-programming.asd (file)

Component

file-type.lisp (file)

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

### 2.7 linear-programming/expressions

Author

Neil Lindquist <NeilLindquist5@gmail.com>

Contact
Source Control

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

Bug Tracker

MIT

Dependencies
Source

linear-programming.asd (file)

Component

file-type.lisp (file)

### 2.8 linear-programming/utils

Author

Neil Lindquist <NeilLindquist5@gmail.com>

Contact
Source Control

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

Bug Tracker

MIT

Dependencies
Source

linear-programming.asd (file)

Component

file-type.lisp (file)

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

### 2.9 linear-programming/conditions

Author

Neil Lindquist <NeilLindquist5@gmail.com>

Contact
Source Control

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

Bug Tracker

MIT

Source

linear-programming.asd (file)

Component

file-type.lisp (file)

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

### 2.10 linear-programming/system-info

Author

Neil Lindquist <NeilLindquist5@gmail.com>

Contact
Source Control

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

Bug Tracker

MIT

Dependencies
• iterate
• alexandria
Source

linear-programming.asd (file)

Component

file-type.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-20211020-git/linear-programming.asd

Systems

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

Parent

linear-programming/all (system)

Location

all.lisp

Packages

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

Parent

linear-programming/solver (system)

Location

solver.lisp

Packages
Exported Definitions

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

Parent
Location

external-formats.lisp

Packages
Exported Definitions
Internal Definitions

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

Parent

linear-programming/simplex (system)

Location

simplex.lisp

Packages
Exported Definitions
Internal Definitions

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

Parent

linear-programming/problem (system)

Location

problem.lisp

Packages
Exported Definitions
Internal Definitions

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

Parent

linear-programming/expressions (system)

Location

expressions.lisp

Packages
Exported Definitions
Internal Definitions

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

Parent

linear-programming/utils (system)

Location

utils.lisp

Packages
Exported Definitions
Internal Definitions

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

Parent

linear-programming/conditions (system)

Location

conditions.lisp

Packages
Exported Definitions
Internal Definitions

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

Parent

linear-programming/system-info (system)

Location

system-info.lisp

Packages
Exported 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

file-type.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

file-type.lisp (file)

Use List
• iterate
• common-lisp
Used By List
Exported Definitions

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

### 4.3 linear-programming/external-formats

Handles reading and writing problems to external formats.

Source

file-type.lisp (file)

Use List
Used By List
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

file-type.lisp (file)

Use List
Exported Definitions
Internal Definitions

### 4.5 linear-programming/problem

Handles the representation of linear programming problems.

Source

file-type.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

file-type.lisp (file)

Use List
Used By List
Exported Definitions
Internal Definitions

### 4.7 linear-programming/utils

Various internal utilities

Source

file-type.lisp (file)

Use List

common-lisp

Used By List
Exported Definitions
Internal Definitions

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

### 4.8 linear-programming/conditions

Contains the various conditions used by this library.

Source

file-type.lisp (file)

Use List

common-lisp

Used By List
Exported Definitions
Internal Definitions

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

### 4.9 linear-programming/system-info

Utilities for inspecting how certain implmenetation-dependant features behave.

Source

file-type.lisp (file)

Use List
• iterate
• common-lisp
Exported Definitions

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 Constants

Constant: +supported-floats+

Contains the distinct floating point representations supported.

Package
Source

file-type.lisp (file)

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

#### 5.1.2 Special variables

Special Variable: *solver*

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

Package
Source

file-type.lisp (file)

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

#### 5.1.3 Macros

Macro: make-linear-problem OBJECTIVE &rest CONSTRAINTS

Creates a linear problem from the expressions in the body

Package
Source

file-type.lisp (file)

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

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

Package
Source

file-type.lisp (file)

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

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

Package
Source

file-type.lisp (file)

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

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

Package
Source

file-type.lisp (file)

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

#### 5.1.4 Compiler macros

Compiler Macro: fp< A B &optional FACTOR
Package
Source

file-type.lisp (file)

Compiler Macro: fp<= A B &optional FACTOR
Package
Source

file-type.lisp (file)

Compiler Macro: fp> A B &optional FACTOR
Package
Source

file-type.lisp (file)

Compiler Macro: fp>= A B &optional FACTOR
Package
Source

file-type.lisp (file)

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

#### 5.1.5 Functions

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

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

Package
Source

file-type.lisp (file)

Function: copy-tableau TABLEAU

Copies the given tableau and it’s matrix.

Package
Source

file-type.lisp (file)

Function: float-contagion T1 T2

Computes the representation type using the rules for float contagion.

Package
Source

file-type.lisp (file)

Function: format-linear-expression ALIST

Formats a linear expression as a sexp.

Package
Source

file-type.lisp (file)

Function: fp< A B &optional FACTOR

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

Package
Source

file-type.lisp (file)

Function: fp<= A B &optional FACTOR

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

Package
Source

file-type.lisp (file)

Function: fp= A B &optional FACTOR

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

Package
Source

file-type.lisp (file)

Function: fp> A B &optional FACTOR

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

Package
Source

file-type.lisp (file)

Function: fp>= A B &optional FACTOR

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

Package
Source

file-type.lisp (file)

Function: lb-max X Y

Computes the maximum value where nil is negative infinity

Package
Source

file-type.lisp (file)

Function: lb-min X Y

Computes the minimum value where nil is negative infinity

Package
Source

file-type.lisp (file)

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

Destructively applies a single pivot to the table.

Package
Source

file-type.lisp (file)

Function: n-solve-tableau TABLEAU

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

Package
Source

file-type.lisp (file)

Function: optimization-type X

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

Package
Source

file-type.lisp (file)

Function: parse-linear-expression EXPR

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

Package
Source

file-type.lisp (file)

Function: parse-linear-problem OBJECTIVE-EXP CONSTRAINTS

Parses the expressions into a linear programming problem

Package
Source

file-type.lisp (file)

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

Non-destructively applies a single pivot to the table.

Package
Source

file-type.lisp (file)

Function: problem-constraints INSTANCE

A list of (in)equality constraints.

Package
Source

file-type.lisp (file)

Function: problem-integer-vars INSTANCE

A list of variables with integer constraints.

Package
Source

file-type.lisp (file)

Function: problem-objective-func INSTANCE

The objective function as a linear expression alist.

Package
Source

file-type.lisp (file)

Function: problem-objective-var INSTANCE

The name of the objective function.

Package
Source

file-type.lisp (file)

Function: problem-type INSTANCE

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

Package
Source

file-type.lisp (file)

Function: problem-var-bounds INSTANCE

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

Package
Source

file-type.lisp (file)

Function: problem-vars INSTANCE

An array of the variables specified in the problem.

Package
Source

file-type.lisp (file)

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
Source

file-type.lisp (file)

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
Source

file-type.lisp (file)

Function: scale-linear-expression EXPR SCALAR

Multiplies the linear expression by the given scalar.

Package
Source

file-type.lisp (file)

Function: simplex-solver PROBLEM &rest ARGS

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

Package
Source

file-type.lisp (file)

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

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

Package
Source

file-type.lisp (file)

Function: solve-tableau TABLEAU

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

Package
Source

file-type.lisp (file)

Function: sum-linear-expressions &rest EXPRS

Takes linear expressions and reduces it into a single expression.

Package
Source

file-type.lisp (file)

Function: tableau-basis-columns INSTANCE
Package
Source

file-type.lisp (file)

Function: tableau-constraint-count INSTANCE
Package
Source

file-type.lisp (file)

Function: tableau-instance-problem INSTANCE
Package
Source

file-type.lisp (file)

Function: tableau-matrix INSTANCE
Package
Source

file-type.lisp (file)

Function: tableau-objective-value TABLEAU

Gets the objective function value in the tableau.

Package
Source

file-type.lisp (file)

Function: tableau-p OBJECT
Package
Source

file-type.lisp (file)

Function: tableau-problem INSTANCE
Package
Source

file-type.lisp (file)

Function: tableau-reduced-cost TABLEAU VAR

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

Package
Source

file-type.lisp (file)

Function: tableau-var-count INSTANCE
Package
Source

file-type.lisp (file)

Function: tableau-variable TABLEAU VAR

Gets the value of the given variable from the tableau

Package
Source

file-type.lisp (file)

Function: ub-max X Y

Computes the maximum value where nil is positive infinity

Package
Source

file-type.lisp (file)

Function: ub-min X Y

Computes the minimum value where nil is positive infinity

Package
Source

file-type.lisp (file)

Function: validate-bounds LB UB VAR

Checks that the bounds represent a non empty range

Package
Source

file-type.lisp (file)

Function: write-sexp STREAM PROBLEM &key PACKAGE

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

Package
Source

file-type.lisp (file)

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

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

Package
Source

file-type.lisp (file)

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

#### 5.1.6 Generic functions

Generic Function: solution-objective-value SOLUTION

Gets the value of the objective function.

Package
Source

file-type.lisp (file)

Methods
Method: solution-objective-value (SOLUTION tableau)
Generic Function: solution-problem SOLUTION

Gets the original problem for the solution.

Package
Source

file-type.lisp (file)

Methods
Method: solution-problem (SOLUTION tableau)
Generic Function: solution-reduced-cost SOLUTION VARIABLE

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

Package
Source

file-type.lisp (file)

Methods
Method: solution-reduced-cost (SOLUTION tableau) VARIABLE
Generic Function: solution-variable SOLUTION VARIABLE

Gets the value of the specified variable.

Package
Source

file-type.lisp (file)

Methods
Method: solution-variable (SOLUTION tableau) VARIABLE

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

#### 5.1.7 Conditions

Condition: infeasible-integer-constraints-error ()

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

Package
Source

file-type.lisp (file)

Direct superclasses

infeasible-problem-error (condition)

Condition: infeasible-problem-error ()

Indicates the there is no feasible region.

Package
Source

file-type.lisp (file)

Direct superclasses

solver-error (condition)

Direct subclasses

infeasible-integer-constraints-error (condition)

Condition: invalid-bounds-error ()

Indicates a problem with a variable’s bounds.

Package
Source

file-type.lisp (file)

Direct superclasses

parsing-error (condition)

Direct methods
• lb (method)
• ub (method)
• var (method)
Direct slots
Slot: var
Initargs

:var

var (generic function)

Slot: ub
Initargs

:ub

ub (generic function)

Slot: lb
Initargs

:lb

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
Source

file-type.lisp (file)

Direct superclasses

parsing-error (condition)

Direct methods

nonlinear-expression (method)

Direct slots
Slot: expression

Contains the problematic expression

Initargs

:expression

nonlinear-expression (generic function)

Condition: parsing-error ()

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

Package
Source

file-type.lisp (file)

Direct superclasses

error (condition)

Direct subclasses
Direct methods

description (method)

Direct slots
Slot: description
Initargs

:description

description (generic function)

Condition: solver-error ()

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

Package
Source

file-type.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
Source

file-type.lisp (file)

Direct superclasses

solver-error (condition)

Condition: unsupported-constraint-error ()

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

Package
Source

file-type.lisp (file)

Direct superclasses

solver-error (condition)

Direct methods
Direct slots
Slot: constraint
Initargs

:constraint

constraint (generic function)

Slot: solver-name
Initargs

:solver-name

solver-name (generic function)

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

#### 5.1.8 Structures

Structure: problem ()

The representation of a linear programming problem.

Package
Source

file-type.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: type
Type

(member max min)

Initform

(quote max)

problem-type (function)

Writers

(setf problem-type) (function)

Slot: vars
Type

(simple-array symbol (*))

Initform

#()

problem-vars (function)

Writers

(setf problem-vars) (function)

Slot: objective-var
Type

symbol

Initform

(quote #:z)

problem-objective-var (function)

Writers

(setf problem-objective-var) (function)

Slot: objective-func
Type

list

problem-objective-func (function)

Writers

(setf problem-objective-func) (function)

Slot: integer-vars
Type

list

problem-integer-vars (function)

Writers

(setf problem-integer-vars) (function)

Slot: var-bounds
Type

list

problem-var-bounds (function)

Writers

(setf problem-var-bounds) (function)

Slot: constraints
Type

list

problem-constraints (function)

Writers

(setf problem-constraints) (function)

Structure: tableau ()

Contains the necessary information for a simplex tableau.

Package
Source

file-type.lisp (file)

Direct superclasses

structure-object (structure)

Direct methods
Direct slots
Slot: problem
Type

linear-programming/problem:problem

tableau-problem (function)

Writers

(setf tableau-problem) (function)

Slot: instance-problem
Type

linear-programming/problem:problem

tableau-instance-problem (function)

Writers

(setf tableau-instance-problem) (function)

Slot: matrix
Type

(simple-array real 2)

Initform

#2a()

tableau-matrix (function)

Writers

(setf tableau-matrix) (function)

Slot: basis-columns
Type

(simple-array fixnum (*))

Initform

#()

tableau-basis-columns (function)

Writers

(setf tableau-basis-columns) (function)

Slot: var-count
Type

(and fixnum unsigned-byte)

Initform

0

tableau-var-count (function)

Writers

(setf tableau-var-count) (function)

Slot: constraint-count
Type

(and fixnum unsigned-byte)

Initform

0

tableau-constraint-count (function)

Writers

(setf tableau-constraint-count) (function)

Slot: var-mapping
Type

hash-table

Initform

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

tableau-var-mapping (function)

Writers

(setf tableau-var-mapping) (function)

Slot: fp-tolerance-factor
Type

real

Initform

1024

tableau-fp-tolerance-factor (function)

Writers

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

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

### 5.2 Internal definitions

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

#### 5.2.1 Macros

Macro: fp-inequality NAME OP EPS-MOD
Package
Source

file-type.lisp (file)

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

#### 5.2.2 Functions

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

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

Package
Source

file-type.lisp (file)

Function: copy-problem INSTANCE
Package
Source

file-type.lisp (file)

Function: find-entering-column TABLEAU

Gets the column to add to the basis.

Package
Source

file-type.lisp (file)

Function: find-pivoting-row TABLEAU ENTERING-COL

Gets the column that will leave the basis.

Package
Source

file-type.lisp (file)

Function: gen-entries TABLEAU ENTRY

Generates new entries to correct one of the integer constraints.

Package
Source

file-type.lisp (file)

Function: linear-constant-p EXPR

A predicate for whether a linear expression is constant.

Package
Source

file-type.lisp (file)

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

file-type.lisp (file)

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

file-type.lisp (file)

Function: newlinep C

Predicate if the given character is a newline or return

Package
Source

file-type.lisp (file)

Function: parse-linear-constraints EXPRS

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

Package
Source

file-type.lisp (file)

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

file-type.lisp (file)

Function: problem-p OBJECT
Package
Source

file-type.lisp (file)

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

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

Package
Source

file-type.lisp (file)

Function: sum-linear-expressions-list EXPRS

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

Package
Source

file-type.lisp (file)

Function: tableau-fp-tolerance-factor INSTANCE
Package
Source

file-type.lisp (file)

Function: tableau-var-mapping INSTANCE
Package
Source

file-type.lisp (file)

Function: violated-integer-constraint TABLEAU

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

Package
Source

file-type.lisp (file)

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

#### 5.2.3 Generic functions

Generic Function: constraint CONDITION
Package
Methods
Method: constraint (CONDITION unsupported-constraint-error)
Source

file-type.lisp (file)

Generic Function: description CONDITION
Package
Methods
Method: description (CONDITION parsing-error)
Source

file-type.lisp (file)

Generic Function: lb CONDITION
Package
Methods
Method: lb (CONDITION invalid-bounds-error)
Source

file-type.lisp (file)

Generic Function: nonlinear-expression CONDITION
Package
Methods
Method: nonlinear-expression (CONDITION nonlinear-error)
Source

file-type.lisp (file)

Generic Function: solver-name CONDITION
Package
Methods
Method: solver-name (CONDITION unsupported-constraint-error)
Source

file-type.lisp (file)

Generic Function: ub CONDITION
Package
Methods
Method: ub (CONDITION invalid-bounds-error)
Source

file-type.lisp (file)

Generic Function: var CONDITION
Package
Methods
Method: var (CONDITION invalid-bounds-error)
Source

file-type.lisp (file)

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

#### 5.2.4 Types

Type: lb ()
Package
Source

file-type.lisp (file)

Type: ub ()
Package
Source

file-type.lisp (file)

Type: var-mapping-entry ()

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

Package
Source

file-type.lisp (file)

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

## Appendix A Indexes

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

### A.1 Concepts

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

### A.2 Functions

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

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

### A.3 Variables

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

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