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 4.0 beta 2 "William Riker" on Thu Sep 15 05:13:02 2022 GMT+0.

Table of Contents


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's designed to provide a high-level and ergonomic API for specifying linear programming problems as lisp expressions.

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

Installation

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

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

Usage

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

Consider the following linear programming problem.

maximize x + 4y + 3z
such that

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

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

(use-package :linear-programming)

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

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

(defvar solution (solve-problem problem))

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

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

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

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

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

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


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

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

2 Systems

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


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

2.1 linear-programming

A library for solving linear programming problems

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

Version

2.1.1

Dependencies
Source

linear-programming.asd.


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.


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


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


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


2.6 linear-programming/utils

Author

Neil Lindquist <NeilLindquist5@gmail.com>

Contact

NeilLindquist5@gmail.com

Home Page

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

Source Control

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

Bug Tracker

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

License

MIT

Dependencies
Source

linear-programming.asd.


2.7 linear-programming/system-info

Author

Neil Lindquist <NeilLindquist5@gmail.com>

Contact

NeilLindquist5@gmail.com

Home Page

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

Source Control

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

Bug Tracker

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

License

MIT

Dependencies
  • iterate (system).
  • alexandria (system).
Source

linear-programming.asd.


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


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


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


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


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

Source

linear-programming.asd.

Parent Component

linear-programming/all (system).

Packages

linear-programming/all.


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

Source

linear-programming.asd.

Parent Component

linear-programming/problem (system).

Packages

linear-programming/problem.

Public Interface
Internals

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

Source

linear-programming.asd.

Parent Component

linear-programming/conditions (system).

Packages

linear-programming/conditions.

Public Interface
Internals

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

Source

linear-programming.asd.

Parent Component

linear-programming/expressions (system).

Packages

linear-programming/expressions.

Public Interface
Internals

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

Source

linear-programming.asd.

Parent Component

linear-programming/utils (system).

Packages

linear-programming/utils.

Public Interface
Internals

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

Source

linear-programming.asd.

Parent Component

linear-programming/system-info (system).

Packages

linear-programming/system-info.

Public Interface

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

Source

linear-programming.asd.

Parent Component

linear-programming/solver (system).

Packages

linear-programming/solver.

Public Interface

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

Source

linear-programming.asd.

Parent Component

linear-programming/simplex (system).

Packages

linear-programming/simplex.

Public Interface
Internals

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

Source

linear-programming.asd.

Parent Component

linear-programming/external-formats (system).

Packages

linear-programming/external-formats.

Public Interface
Internals

4 Packages

Packages are listed by definition order.


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

4.1 linear-programming/utils

Various internal utilities

Source

file-type.lisp.

Use List

common-lisp.

Used By List

linear-programming/simplex.

Public Interface
Internals

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

Nickname

linear-programming

Use List

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

Use List
  • common-lisp.
  • iterate.
Used By List

linear-programming/all.

Public Interface

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.

Use List
Public Interface
Internals

4.5 linear-programming/conditions

Contains the various conditions used by this library.

Source

file-type.lisp.

Use List

common-lisp.

Used By List
Public Interface
Internals

4.6 linear-programming/system-info

Utilities for inspecting how certain implmenetation-dependant features behave.

Source

file-type.lisp.

Use List
  • common-lisp.
  • iterate.
Public Interface

4.7 linear-programming/problem

Handles the representation of linear programming problems.

Source

file-type.lisp.

Use List
Used By List
Public Interface
Internals

4.8 linear-programming/expressions

Contains functions for processing linear expressions.

Source

file-type.lisp.

Use List
Used By List

linear-programming/problem.

Public Interface
Internals

4.9 linear-programming/external-formats

Handles reading and writing problems to external formats.

Source

file-type.lisp.

Use List
Used By List

linear-programming/all.

Public Interface
Internals

5 Definitions

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


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

5.1 Public Interface


5.1.1 Constants

Constant: +supported-floats+

Contains the distinct floating point representations supported.

Package

linear-programming/system-info.

Source

file-type.lisp.


Next: , Previous: , Up: Public Interface   [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

linear-programming/solver.

Source

file-type.lisp.


5.1.3 Macros

Macro: make-linear-problem (objective &rest constraints)

Creates a linear problem from the expressions in the body

Package

linear-programming/problem.

Source

file-type.lisp.

Macro: with-solution-variables (var-list solution &body body)

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

Package

linear-programming/solver.

Source

file-type.lisp.

Macro: with-solved-problem ((objective-func &rest constraints) &body body)

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

Package

linear-programming/solver.

Source

file-type.lisp.

Macro: with-tableau-variables (var-list tableau &body body)

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

Package

linear-programming/simplex.

Source

file-type.lisp.


5.1.4 Compiler macros

Compiler Macro: fp< (a b &optional factor)
Package

linear-programming/utils.

Source

file-type.lisp.

Compiler Macro: fp<= (a b &optional factor)
Package

linear-programming/utils.

Source

file-type.lisp.

Compiler Macro: fp> (a b &optional factor)
Package

linear-programming/utils.

Source

file-type.lisp.

Compiler Macro: fp>= (a b &optional factor)
Package

linear-programming/utils.

Source

file-type.lisp.


5.1.5 Ordinary functions

Function: build-tableau (problem instance-problem &key fp-tolerance-factor)

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

Package

linear-programming/simplex.

Source

file-type.lisp.

Function: copy-tableau (tableau)

Copies the given tableau and it’s matrix.

Package

linear-programming/simplex.

Source

file-type.lisp.

Function: float-contagion (t1 t2)

Computes the representation type using the rules for float contagion.

Package

linear-programming/system-info.

Source

file-type.lisp.

Function: format-linear-expression (alist)

Formats a linear expression as a sexp.

Package

linear-programming/expressions.

Source

file-type.lisp.

Function: fp< (a b &optional factor)

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

Package

linear-programming/utils.

Source

file-type.lisp.

Function: fp<= (a b &optional factor)

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

Package

linear-programming/utils.

Source

file-type.lisp.

Function: fp= (a b &optional factor)

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

Package

linear-programming/utils.

Source

file-type.lisp.

Function: fp> (a b &optional factor)

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

Package

linear-programming/utils.

Source

file-type.lisp.

Function: fp>= (a b &optional factor)

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

Package

linear-programming/utils.

Source

file-type.lisp.

Function: lb-max (x y)

Computes the maximum value where nil is negative infinity

Package

linear-programming/utils.

Source

file-type.lisp.

Function: lb-min (x y)

Computes the minimum value where nil is negative infinity

Package

linear-programming/utils.

Source

file-type.lisp.

Function: n-pivot-row (tableau entering-col changing-row)

Destructively applies a single pivot to the table.

Package

linear-programming/simplex.

Source

file-type.lisp.

Function: n-solve-tableau (tableau)

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

Package

linear-programming/simplex.

Source

file-type.lisp.

Function: optimization-type (x)

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

Package

linear-programming/system-info.

Source

file-type.lisp.

Function: parse-linear-expression (expr)

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

Package

linear-programming/expressions.

Source

file-type.lisp.

Function: parse-linear-problem (objective-exp constraints)

Parses the expressions into a linear programming problem

Package

linear-programming/problem.

Source

file-type.lisp.

Function: pivot-row (tableau entering-col changing-row)

Non-destructively applies a single pivot to the table.

Package

linear-programming/simplex.

Source

file-type.lisp.

Reader: problem-constraints (instance)

A list of (in)equality constraints.

Package

linear-programming/problem.

Source

file-type.lisp.

Target Slot

constraints.

Reader: problem-integer-vars (instance)

A list of variables with integer constraints.

Package

linear-programming/problem.

Source

file-type.lisp.

Target Slot

integer-vars.

Reader: problem-objective-func (instance)

The objective function as a linear expression alist.

Package

linear-programming/problem.

Source

file-type.lisp.

Target Slot

objective-func.

Reader: problem-objective-var (instance)

The name of the objective function.

Package

linear-programming/problem.

Source

file-type.lisp.

Target Slot

objective-var.

Reader: problem-type (instance)

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

Package

linear-programming/problem.

Source

file-type.lisp.

Target Slot

type.

Reader: problem-var-bounds (instance)

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

Package

linear-programming/problem.

Source

file-type.lisp.

Target Slot

var-bounds.

Reader: problem-vars (instance)

An array of the variables specified in the problem.

Package

linear-programming/problem.

Source

file-type.lisp.

Target Slot

vars.

Function: read-mps (stream problem-type &key package read-case trim-names-p number-type rhs-id)

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

Package

linear-programming/external-formats.

Source

file-type.lisp.

Function: read-sexp (stream &key allow-read-eval package)

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

Package

linear-programming/external-formats.

Source

file-type.lisp.

Function: scale-linear-expression (expr scalar)

Multiplies the linear expression by the given scalar.

Package

linear-programming/expressions.

Source

file-type.lisp.

Function: simplex-solver (problem &rest args)

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

Package

linear-programming/simplex.

Source

file-type.lisp.

Function: solve-problem (problem &rest args &key &allow-other-keys)

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

Package

linear-programming/solver.

Source

file-type.lisp.

Function: solve-tableau (tableau)

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

Package

linear-programming/simplex.

Source

file-type.lisp.

Function: sum-linear-expressions (&rest exprs)

Takes linear expressions and reduces it into a single expression.

Package

linear-programming/expressions.

Source

file-type.lisp.

Reader: tableau-basis-columns (instance)
Package

linear-programming/simplex.

Source

file-type.lisp.

Target Slot

basis-columns.

Reader: tableau-constraint-count (instance)
Package

linear-programming/simplex.

Source

file-type.lisp.

Target Slot

constraint-count.

Reader: tableau-instance-problem (instance)
Package

linear-programming/simplex.

Source

file-type.lisp.

Target Slot

instance-problem.

Reader: tableau-matrix (instance)
Package

linear-programming/simplex.

Source

file-type.lisp.

Target Slot

matrix.

Function: tableau-objective-value (tableau)

Gets the objective function value in the tableau.

Package

linear-programming/simplex.

Source

file-type.lisp.

Function: tableau-p (object)
Package

linear-programming/simplex.

Source

file-type.lisp.

Reader: tableau-problem (instance)
Package

linear-programming/simplex.

Source

file-type.lisp.

Target Slot

problem.

Function: tableau-reduced-cost (tableau var)

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

Package

linear-programming/simplex.

Source

file-type.lisp.

Reader: tableau-var-count (instance)
Package

linear-programming/simplex.

Source

file-type.lisp.

Target Slot

var-count.

Function: tableau-variable (tableau var)

Gets the value of the given variable from the tableau

Package

linear-programming/simplex.

Source

file-type.lisp.

Function: ub-max (x y)

Computes the maximum value where nil is positive infinity

Package

linear-programming/utils.

Source

file-type.lisp.

Function: ub-min (x y)

Computes the minimum value where nil is positive infinity

Package

linear-programming/utils.

Source

file-type.lisp.

Function: validate-bounds (lb ub var)

Checks that the bounds represent a non empty range

Package

linear-programming/utils.

Source

file-type.lisp.

Function: write-sexp (stream problem &key package)

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

Package

linear-programming/external-formats.

Source

file-type.lisp.

Function: write-standard-format (stream problem &key unicodep aesthetic-variable-names-p)

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

Package

linear-programming/external-formats.

Source

file-type.lisp.


5.1.6 Generic functions

Generic Function: solution-objective-value (solution)

Gets the value of the objective function.

Package

linear-programming/solver.

Source

file-type.lisp.

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

Gets the original problem for the solution.

Package

linear-programming/solver.

Source

file-type.lisp.

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

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

Package

linear-programming/solver.

Source

file-type.lisp.

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

Gets the value of the specified variable.

Package

linear-programming/solver.

Source

file-type.lisp.

Methods
Method: solution-variable ((solution tableau) variable)

5.1.7 Conditions

Condition: infeasible-integer-constraints-error

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

Package

linear-programming/conditions.

Source

file-type.lisp.

Direct superclasses

infeasible-problem-error.

Condition: infeasible-problem-error

Indicates the there is no feasible region.

Package

linear-programming/conditions.

Source

file-type.lisp.

Direct superclasses

solver-error.

Direct subclasses

infeasible-integer-constraints-error.

Condition: invalid-bounds-error

Indicates a problem with a variable’s bounds.

Package

linear-programming/conditions.

Source

file-type.lisp.

Direct superclasses

parsing-error.

Direct methods
Direct slots
Slot: var
Initargs

:var

Readers

var.

Writers

This slot is read-only.

Slot: ub
Initargs

:ub

Readers

ub.

Writers

This slot is read-only.

Slot: lb
Initargs

:lb

Readers

lb.

Writers

This slot is read-only.

Condition: nonlinear-error

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

Package

linear-programming/conditions.

Source

file-type.lisp.

Direct superclasses

parsing-error.

Direct methods

nonlinear-expression.

Direct slots
Slot: expression

Contains the problematic expression

Initargs

:expression

Readers

nonlinear-expression.

Writers

This slot is read-only.

Condition: parsing-error

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

Package

linear-programming/conditions.

Source

file-type.lisp.

Direct superclasses

error.

Direct subclasses
Direct methods

description.

Direct slots
Slot: description
Initargs

:description

Readers

description.

Writers

This slot is read-only.

Condition: solver-error

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

Package

linear-programming/conditions.

Source

file-type.lisp.

Direct superclasses

error.

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

file-type.lisp.

Direct superclasses

solver-error.

Condition: unsupported-constraint-error

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

Package

linear-programming/conditions.

Source

file-type.lisp.

Direct superclasses

solver-error.

Direct methods
Direct slots
Slot: constraint
Initargs

:constraint

Readers

constraint.

Writers

This slot is read-only.

Slot: solver-name
Initargs

:solver-name

Readers

solver-name.

Writers

This slot is read-only.


Previous: , Up: Public Interface   [Contents][Index]

5.1.8 Structures

Structure: problem

The representation of a linear programming problem.

Package

linear-programming/problem.

Source

file-type.lisp.

Direct superclasses

structure-object.

Direct slots
Slot: type
Package

common-lisp.

Type

(member max min)

Initform

(quote max)

Readers

problem-type.

Writers

This slot is read-only.

Slot: vars
Type

(simple-array symbol (*))

Initform

#()

Readers

problem-vars.

Writers

This slot is read-only.

Slot: objective-var
Type

symbol

Initform

(quote #:z)

Readers

problem-objective-var.

Writers

This slot is read-only.

Slot: objective-func
Type

list

Readers

problem-objective-func.

Writers

This slot is read-only.

Slot: integer-vars
Type

list

Readers

problem-integer-vars.

Writers

This slot is read-only.

Slot: var-bounds
Type

list

Readers

problem-var-bounds.

Writers

This slot is read-only.

Slot: constraints
Type

list

Readers

problem-constraints.

Writers

This slot is read-only.

Structure: tableau

Contains the necessary information for a simplex tableau.

Package

linear-programming/simplex.

Source

file-type.lisp.

Direct superclasses

structure-object.

Direct methods
Direct slots
Slot: problem
Package

linear-programming/problem.

Type

linear-programming/problem:problem

Readers

tableau-problem.

Writers

This slot is read-only.

Slot: instance-problem
Type

linear-programming/problem:problem

Readers

tableau-instance-problem.

Writers

This slot is read-only.

Slot: matrix
Type

(simple-array real 2)

Initform

#2a()

Readers

tableau-matrix.

Writers

This slot is read-only.

Slot: basis-columns
Type

(simple-array fixnum (*))

Initform

#()

Readers

tableau-basis-columns.

Writers

This slot is read-only.

Slot: var-count
Type

(and fixnum unsigned-byte)

Initform

0

Readers

tableau-var-count.

Writers

This slot is read-only.

Slot: constraint-count
Type

(and fixnum unsigned-byte)

Initform

0

Readers

tableau-constraint-count.

Writers

This slot is read-only.

Slot: var-mapping
Type

hash-table

Initform

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

Readers

tableau-var-mapping.

Writers

This slot is read-only.

Slot: fp-tolerance-factor
Type

real

Initform

1024

Readers

tableau-fp-tolerance-factor.

Writers

This slot is read-only.


5.2 Internals


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

5.2.1 Macros

Macro: fp-inequality (name op eps-mod)
Package

linear-programming/utils.

Source

file-type.lisp.


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

5.2.2 Ordinary functions

Function: build-and-solve (problem extra-constraints &key fp-tolerance-factor)

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

Package

linear-programming/simplex.

Source

file-type.lisp.

Function: copy-problem (instance)
Package

linear-programming/problem.

Source

file-type.lisp.

Function: find-entering-column (tableau)

Gets the column to add to the basis.

Package

linear-programming/simplex.

Source

file-type.lisp.

Function: find-pivoting-row (tableau entering-col)

Gets the column that will leave the basis.

Package

linear-programming/simplex.

Source

file-type.lisp.

Function: gen-entries (tableau entry)

Generates new entries to correct one of the integer constraints.

Package

linear-programming/simplex.

Source

file-type.lisp.

Function: linear-constant-p (expr)

A predicate for whether a linear expression is constant.

Package

linear-programming/expressions.

Source

file-type.lisp.

Function: make-problem (&key type vars objective-var objective-func integer-vars var-bounds constraints)
Package

linear-programming/problem.

Source

file-type.lisp.

Function: make-tableau (&key problem instance-problem matrix basis-columns var-count constraint-count var-mapping fp-tolerance-factor)
Package

linear-programming/simplex.

Source

file-type.lisp.

Function: newlinep (c)

Predicate if the given character is a newline or return

Package

linear-programming/external-formats.

Source

file-type.lisp.

Function: parse-linear-constraints (exprs)

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

Package

linear-programming/problem.

Source

file-type.lisp.

Function: print-linear-expression (stream expression &optional aesthetic-variable-names-p)
Package

linear-programming/external-formats.

Source

file-type.lisp.

Function: problem-p (object)
Package

linear-programming/problem.

Source

file-type.lisp.

Function: read-until (stream test &optional preview-test)

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

Package

linear-programming/external-formats.

Source

file-type.lisp.

Function: sum-linear-expressions-list (exprs)

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

Package

linear-programming/expressions.

Source

file-type.lisp.

Reader: tableau-fp-tolerance-factor (instance)
Package

linear-programming/simplex.

Source

file-type.lisp.

Target Slot

fp-tolerance-factor.

Reader: tableau-var-mapping (instance)
Package

linear-programming/simplex.

Source

file-type.lisp.

Target Slot

var-mapping.

Function: violated-integer-constraint (tableau)

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

Package

linear-programming/simplex.

Source

file-type.lisp.


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

5.2.3 Generic functions

Generic Reader: constraint (condition)
Package

linear-programming/conditions.

Methods
Reader Method: constraint ((condition unsupported-constraint-error))
Source

file-type.lisp.

Target Slot

constraint.

Generic Reader: description (condition)
Package

linear-programming/conditions.

Methods
Reader Method: description ((condition parsing-error))
Source

file-type.lisp.

Target Slot

description.

Generic Reader: lb (condition)
Package

linear-programming/conditions.

Methods
Reader Method: lb ((condition invalid-bounds-error))
Source

file-type.lisp.

Target Slot

lb.

Generic Reader: nonlinear-expression (condition)
Package

linear-programming/conditions.

Methods
Reader Method: nonlinear-expression ((condition nonlinear-error))
Source

file-type.lisp.

Target Slot

expression.

Generic Reader: solver-name (condition)
Package

linear-programming/conditions.

Methods
Reader Method: solver-name ((condition unsupported-constraint-error))
Source

file-type.lisp.

Target Slot

solver-name.

Generic Reader: ub (condition)
Package

linear-programming/conditions.

Methods
Reader Method: ub ((condition invalid-bounds-error))
Source

file-type.lisp.

Target Slot

ub.

Generic Reader: var (condition)
Package

linear-programming/conditions.

Methods
Reader Method: var ((condition invalid-bounds-error))
Source

file-type.lisp.

Target Slot

var.


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

5.2.4 Types

Type: lb ()
Package

linear-programming/utils.

Source

file-type.lisp.

Type: ub ()
Package

linear-programming/utils.

Source

file-type.lisp.

Type: var-mapping-entry ()

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

Package

linear-programming/simplex.

Source

file-type.lisp.


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  
Index Entry  Section

B
build-and-solve: Private ordinary functions
build-tableau: Public ordinary functions

C
Compiler Macro, fp<: Public compiler macros
Compiler Macro, fp<=: Public compiler macros
Compiler Macro, fp>: Public compiler macros
Compiler Macro, fp>=: Public compiler macros
constraint: Private generic functions
constraint: Private generic functions
copy-problem: Private ordinary functions
copy-tableau: Public ordinary functions

D
description: Private generic functions
description: Private generic functions

F
find-entering-column: Private ordinary functions
find-pivoting-row: Private ordinary functions
float-contagion: Public ordinary functions
format-linear-expression: Public ordinary functions
fp-inequality: Private macros
fp<: Public compiler macros
fp<: Public ordinary functions
fp<=: Public compiler macros
fp<=: Public ordinary functions
fp=: Public ordinary functions
fp>: Public compiler macros
fp>: Public ordinary functions
fp>=: Public compiler macros
fp>=: Public ordinary functions
Function, build-and-solve: Private ordinary functions
Function, build-tableau: Public ordinary functions
Function, copy-problem: Private ordinary functions
Function, copy-tableau: Public ordinary functions
Function, find-entering-column: Private ordinary functions
Function, find-pivoting-row: Private ordinary functions
Function, float-contagion: Public ordinary functions
Function, format-linear-expression: Public ordinary functions
Function, fp<: Public ordinary functions
Function, fp<=: Public ordinary functions
Function, fp=: Public ordinary functions
Function, fp>: Public ordinary functions
Function, fp>=: Public ordinary functions
Function, gen-entries: Private ordinary functions
Function, lb-max: Public ordinary functions
Function, lb-min: Public ordinary functions
Function, linear-constant-p: Private ordinary functions
Function, make-problem: Private ordinary functions
Function, make-tableau: Private ordinary functions
Function, n-pivot-row: Public ordinary functions
Function, n-solve-tableau: Public ordinary functions
Function, newlinep: Private ordinary functions
Function, optimization-type: Public ordinary functions
Function, parse-linear-constraints: Private ordinary functions
Function, parse-linear-expression: Public ordinary functions
Function, parse-linear-problem: Public ordinary functions
Function, pivot-row: Public ordinary functions
Function, print-linear-expression: Private ordinary functions
Function, problem-constraints: Public ordinary functions
Function, problem-integer-vars: Public ordinary functions
Function, problem-objective-func: Public ordinary functions
Function, problem-objective-var: Public ordinary functions
Function, problem-p: Private ordinary functions
Function, problem-type: Public ordinary functions
Function, problem-var-bounds: Public ordinary functions
Function, problem-vars: Public ordinary functions
Function, read-mps: Public ordinary functions
Function, read-sexp: Public ordinary functions
Function, read-until: Private ordinary functions
Function, scale-linear-expression: Public ordinary functions
Function, simplex-solver: Public ordinary functions
Function, solve-problem: Public ordinary functions
Function, solve-tableau: Public ordinary functions
Function, sum-linear-expressions: Public ordinary functions
Function, sum-linear-expressions-list: Private ordinary functions
Function, tableau-basis-columns: Public ordinary functions
Function, tableau-constraint-count: Public ordinary functions
Function, tableau-fp-tolerance-factor: Private ordinary functions
Function, tableau-instance-problem: Public ordinary functions
Function, tableau-matrix: Public ordinary functions
Function, tableau-objective-value: Public ordinary functions
Function, tableau-p: Public ordinary functions
Function, tableau-problem: Public ordinary functions
Function, tableau-reduced-cost: Public ordinary functions
Function, tableau-var-count: Public ordinary functions
Function, tableau-var-mapping: Private ordinary functions
Function, tableau-variable: Public ordinary functions
Function, ub-max: Public ordinary functions
Function, ub-min: Public ordinary functions
Function, validate-bounds: Public ordinary functions
Function, violated-integer-constraint: Private ordinary functions
Function, write-sexp: Public ordinary functions
Function, write-standard-format: Public ordinary functions

G
gen-entries: Private ordinary functions
Generic Function, constraint: Private generic functions
Generic Function, description: Private generic functions
Generic Function, lb: Private generic functions
Generic Function, nonlinear-expression: Private generic functions
Generic Function, solution-objective-value: Public generic functions
Generic Function, solution-problem: Public generic functions
Generic Function, solution-reduced-cost: Public generic functions
Generic Function, solution-variable: Public generic functions
Generic Function, solver-name: Private generic functions
Generic Function, ub: Private generic functions
Generic Function, var: Private generic functions

L
lb: Private generic functions
lb: Private generic functions
lb-max: Public ordinary functions
lb-min: Public ordinary functions
linear-constant-p: Private ordinary functions

M
Macro, fp-inequality: Private macros
Macro, make-linear-problem: Public macros
Macro, with-solution-variables: Public macros
Macro, with-solved-problem: Public macros
Macro, with-tableau-variables: Public macros
make-linear-problem: Public macros
make-problem: Private ordinary functions
make-tableau: Private ordinary functions
Method, constraint: Private generic functions
Method, description: Private generic functions
Method, lb: Private generic functions
Method, nonlinear-expression: Private generic functions
Method, solution-objective-value: Public generic functions
Method, solution-problem: Public generic functions
Method, solution-reduced-cost: Public generic functions
Method, solution-variable: Public generic functions
Method, solver-name: Private generic functions
Method, ub: Private generic functions
Method, var: Private generic functions

N
n-pivot-row: Public ordinary functions
n-solve-tableau: Public ordinary functions
newlinep: Private ordinary functions
nonlinear-expression: Private generic functions
nonlinear-expression: Private generic functions

O
optimization-type: Public ordinary functions

P
parse-linear-constraints: Private ordinary functions
parse-linear-expression: Public ordinary functions
parse-linear-problem: Public ordinary functions
pivot-row: Public ordinary functions
print-linear-expression: Private ordinary functions
problem-constraints: Public ordinary functions
problem-integer-vars: Public ordinary functions
problem-objective-func: Public ordinary functions
problem-objective-var: Public ordinary functions
problem-p: Private ordinary functions
problem-type: Public ordinary functions
problem-var-bounds: Public ordinary functions
problem-vars: Public ordinary functions

R
read-mps: Public ordinary functions
read-sexp: Public ordinary functions
read-until: Private ordinary functions

S
scale-linear-expression: Public ordinary functions
simplex-solver: Public ordinary functions
solution-objective-value: Public generic functions
solution-objective-value: Public generic functions
solution-problem: Public generic functions
solution-problem: Public generic functions
solution-reduced-cost: Public generic functions
solution-reduced-cost: Public generic functions
solution-variable: Public generic functions
solution-variable: Public generic functions
solve-problem: Public ordinary functions
solve-tableau: Public ordinary functions
solver-name: Private generic functions
solver-name: Private generic functions
sum-linear-expressions: Public ordinary functions
sum-linear-expressions-list: Private ordinary functions

T
tableau-basis-columns: Public ordinary functions
tableau-constraint-count: Public ordinary functions
tableau-fp-tolerance-factor: Private ordinary functions
tableau-instance-problem: Public ordinary functions
tableau-matrix: Public ordinary functions
tableau-objective-value: Public ordinary functions
tableau-p: Public ordinary functions
tableau-problem: Public ordinary functions
tableau-reduced-cost: Public ordinary functions
tableau-var-count: Public ordinary functions
tableau-var-mapping: Private ordinary functions
tableau-variable: Public ordinary functions

U
ub: Private generic functions
ub: Private generic functions
ub-max: Public ordinary functions
ub-min: Public ordinary functions

V
validate-bounds: Public ordinary functions
var: Private generic functions
var: Private generic functions
violated-integer-constraint: Private ordinary functions

W
with-solution-variables: Public macros
with-solved-problem: Public macros
with-tableau-variables: Public macros
write-sexp: Public ordinary functions
write-standard-format: Public ordinary functions

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  
Index Entry  Section

*
*solver*: Public special variables

+
+supported-floats+: Public constants

B
basis-columns: Public structures

C
Constant, +supported-floats+: Public constants
constraint: Public conditions
constraint-count: Public structures
constraints: Public structures

D
description: Public conditions

E
expression: Public conditions

F
fp-tolerance-factor: Public structures

I
instance-problem: Public structures
integer-vars: Public structures

L
lb: Public conditions

M
matrix: Public structures

O
objective-func: Public structures
objective-var: Public structures

P
problem: Public structures

S
Slot, basis-columns: Public structures
Slot, constraint: Public conditions
Slot, constraint-count: Public structures
Slot, constraints: Public structures
Slot, description: Public conditions
Slot, expression: Public conditions
Slot, fp-tolerance-factor: Public structures
Slot, instance-problem: Public structures
Slot, integer-vars: Public structures
Slot, lb: Public conditions
Slot, matrix: Public structures
Slot, objective-func: Public structures
Slot, objective-var: Public structures
Slot, problem: Public structures
Slot, solver-name: Public conditions
Slot, type: Public structures
Slot, ub: Public conditions
Slot, var: Public conditions
Slot, var-bounds: Public structures
Slot, var-count: Public structures
Slot, var-mapping: Public structures
Slot, vars: Public structures
solver-name: Public conditions
Special Variable, *solver*: Public special variables

T
type: Public structures

U
ub: Public conditions

V
var: Public conditions
var-bounds: Public structures
var-count: Public structures
var-mapping: Public structures
vars: Public structures

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

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

A.4 Data types

Jump to:   C   F   I   L   N   P   S   T   U   V  
Index Entry  Section

C
Condition, infeasible-integer-constraints-error: Public conditions
Condition, infeasible-problem-error: Public conditions
Condition, invalid-bounds-error: Public conditions
Condition, nonlinear-error: Public conditions
Condition, parsing-error: Public conditions
Condition, solver-error: Public conditions
Condition, unbounded-problem-error: Public conditions
Condition, unsupported-constraint-error: Public conditions

F
File, file-type.lisp: The linear-programming/all/file-type․lisp file
File, file-type.lisp: The linear-programming/problem/file-type․lisp file
File, file-type.lisp: The linear-programming/conditions/file-type․lisp file
File, file-type.lisp: The linear-programming/expressions/file-type․lisp file
File, file-type.lisp: The linear-programming/utils/file-type․lisp file
File, file-type.lisp: The linear-programming/system-info/file-type․lisp file
File, file-type.lisp: The linear-programming/solver/file-type․lisp file
File, file-type.lisp: The linear-programming/simplex/file-type․lisp file
File, file-type.lisp: The linear-programming/external-formats/file-type․lisp file
File, linear-programming.asd: The linear-programming/linear-programming․asd file
file-type.lisp: The linear-programming/all/file-type․lisp file
file-type.lisp: The linear-programming/problem/file-type․lisp file
file-type.lisp: The linear-programming/conditions/file-type․lisp file
file-type.lisp: The linear-programming/expressions/file-type․lisp file
file-type.lisp: The linear-programming/utils/file-type․lisp file
file-type.lisp: The linear-programming/system-info/file-type․lisp file
file-type.lisp: The linear-programming/solver/file-type․lisp file
file-type.lisp: The linear-programming/simplex/file-type․lisp file
file-type.lisp: The linear-programming/external-formats/file-type․lisp file

I
infeasible-integer-constraints-error: Public conditions
infeasible-problem-error: Public conditions
invalid-bounds-error: Public conditions

L
lb: Private types
linear-programming: The linear-programming system
linear-programming.asd: The linear-programming/linear-programming․asd file
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/system-info: The linear-programming/system-info system
linear-programming/system-info: The linear-programming/system-info package
linear-programming/utils: The linear-programming/utils system
linear-programming/utils: The linear-programming/utils package

N
nonlinear-error: Public 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/system-info: The linear-programming/system-info package
Package, linear-programming/utils: The linear-programming/utils package
parsing-error: Public conditions
problem: Public structures

S
solver-error: Public conditions
Structure, problem: Public structures
Structure, tableau: Public 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/system-info: The linear-programming/system-info system
System, linear-programming/utils: The linear-programming/utils system

T
tableau: Public structures
Type, lb: Private types
Type, ub: Private types
Type, var-mapping-entry: Private types

U
ub: Private types
unbounded-problem-error: Public conditions
unsupported-constraint-error: Public conditions

V
var-mapping-entry: Private types

Jump to:   C   F   I   L   N   P   S   T   U   V