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-P (OBJECT)

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.