**PACKAGE** - LINEAR-PROGRAMMING

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`

.

**PACKAGE** - LINEAR-PROGRAMMING/PROBLEM

Handles the representation of linear programming problems.

**FUNCTION** - PROBLEM-TYPE (INSTANCE)

Whether the problem is a `min`

or `max`

problem.

**FUNCTION** - PROBLEM-OBJECTIVE-FUNC (INSTANCE)

The objective function as a linear expression alist.

**FUNCTION** - PROBLEM-OBJECTIVE-VAR (INSTANCE)

The name of the objective function.

**FUNCTION** - PROBLEM-VARS (INSTANCE)

An array of the variables specified in the problem.

**FUNCTION** - PARSE-LINEAR-PROBLEM (OBJECTIVE-EXP CONSTRAINTS)

Parses the expressions into a linear programming problem

**MACRO** - MAKE-LINEAR-PROBLEM (OBJECTIVE &REST CONSTRAINTS)

Creates a linear problem from the expressions in the body

**FUNCTION** - PROBLEM-INTEGER-VARS (INSTANCE)

A list of variables with integer constraints.

**STRUCT** - PROBLEM

The representation of a linear programming problem.

**FUNCTION** - PROBLEM-VAR-BOUNDS (INSTANCE)

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

.

**FUNCTION** - PROBLEM-CONSTRAINTS (INSTANCE)

A list of (in)equality constraints.

**PACKAGE** - 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.

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

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

**GENERIC** - SOLUTION-PROBLEM (SOLUTION)

Gets the original problem for the solution.

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

**GENERIC** - SOLUTION-VARIABLE (SOLUTION VARIABLE)

Gets the value of the specified variable.

**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`

.

**GENERIC** - 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.

**GENERIC** - SOLUTION-OBJECTIVE-VALUE (SOLUTION)

Gets the value of the objective function.

**PACKAGE** - LINEAR-PROGRAMMING/EXTERNAL-FORMATS

Handles reading and writing problems to external formats.

**FUNCTION** - READ-MPS (STREAM PROBLEM-TYPE &KEY PACKAGE (READ-CASE (READTABLE-CASE *READTABLE*))
(TRIM-NAMES-P T) (NUMBER-TYPE ‘RATIONAL) 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.

**FUNCTION** - WRITE-STANDARD-FORMAT (STREAM PROBLEM &KEY (UNICODEP T) (AESTHETIC-VARIABLE-NAMES-P T))

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.

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

**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/CONDITIONS

Contains the various conditions used by this library.

**CONDITION** - UNSUPPORTED-CONSTRAINT-ERROR

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

**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

**CONDITION** - INFEASIBLE-PROBLEM-ERROR

Indicates the there is no feasible region.

**CONDITION** - SOLVER-ERROR

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

**CONDITION** - INVALID-BOUNDS-ERROR

Indicates a problem with a variable’s bounds.

**CONDITION** - INFEASIBLE-INTEGER-CONSTRAINTS-ERROR

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

**CONDITION** - UNBOUNDED-PROBLEM-ERROR

Indicates the feasible region is unbounded such that the optimal objective value
is infinite.

**CONDITION** - PARSING-ERROR

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

**PACKAGE** - 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.

**FUNCTION** - N-PIVOT-ROW (TABLEAU ENTERING-COL CHANGING-ROW)

Destructively applies a single pivot to the table.

**FUNCTION** - TABLEAU-MATRIX (INSTANCE)

**STRUCT** - TABLEAU

Contains the necessary information for a simplex tableau.

**FUNCTION** - TABLEAU-VAR-COUNT (INSTANCE)

**FUNCTION** - TABLEAU-OBJECTIVE-VALUE (TABLEAU)

Gets the objective function value in the tableau.

**FUNCTION** - PIVOT-ROW (TABLEAU ENTERING-COL CHANGING-ROW)

Non-destructively applies a single pivot to the table.

**FUNCTION** - TABLEAU-INSTANCE-PROBLEM (INSTANCE)

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

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

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

**FUNCTION** - BUILD-TABLEAU (PROBLEM INSTANCE-PROBLEM &KEY (FP-TOLERANCE-FACTOR 1024))

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.

**FUNCTION** - TABLEAU-BASIS-COLUMNS (INSTANCE)

**FUNCTION** - TABLEAU-CONSTRAINT-COUNT (INSTANCE)

**FUNCTION** - N-SOLVE-TABLEAU (TABLEAU)

A non-consing version of `solve-tableau`

.

**FUNCTION** - TABLEAU-PROBLEM (INSTANCE)

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

**FUNCTION** - COPY-TABLEAU (TABLEAU)

Copies the given tableau and it’s matrix.

**FUNCTION** - TABLEAU-VARIABLE (TABLEAU VAR)

Gets the value of the given variable from the tableau

**PACKAGE** - LINEAR-PROGRAMMING/EXPRESSIONS

Contains functions for processing linear expressions.

**FUNCTION** - SCALE-LINEAR-EXPRESSION (EXPR SCALAR)

Multiplies the linear expression by the given scalar.

**FUNCTION** - FORMAT-LINEAR-EXPRESSION (ALIST)

Formats a linear expression as a sexp.

**FUNCTION** - PARSE-LINEAR-EXPRESSION (EXPR)

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

.

**FUNCTION** - SUM-LINEAR-EXPRESSIONS (&REST EXPRS)

Takes linear expressions and reduces it into a single expression.