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-CONSTRAINTS (INSTANCE)
A list of (in)equality constraints.
FUNCTION - PROBLEM-TYPE (INSTANCE)
Whether the problem is a min or max problem.
FUNCTION - PROBLEM-VAR-BOUNDS (INSTANCE)
A list of variable bounds, of the form (var . (lower-bound . upper-bound)).
STRUCT - PROBLEM
The representation of a linear programming problem.
MACRO - MAKE-LINEAR-PROBLEM (OBJECTIVE &REST CONSTRAINTS)
Creates a linear problem from the expressions in the body
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
FUNCTION - PROBLEM-INTEGER-VARS (INSTANCE)
A list of variables with integer constraints.
FUNCTION - PROBLEM-OBJECTIVE-FUNC (INSTANCE)
The objective function as a linear expression alist.
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.
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-PROBLEM (SOLUTION)
Gets the original problem for the solution.
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-VARIABLE (SOLUTION VARIABLE)
Gets the value of the specified variable.
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-OBJECTIVE-VALUE (SOLUTION)
Gets the value of the objective function.
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.
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-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.
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.
PACKAGE - LINEAR-PROGRAMMING/CONDITIONS
Contains the various conditions used by this library.
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 - UNSUPPORTED-CONSTRAINT-ERROR
Indicates there are unsupported constraints or properties in the given problem.
CONDITION - PARSING-ERROR
Indicates an error occured while parsing a linear problem. Includes a textual
description of the issue.
CONDITION - INFEASIBLE-PROBLEM-ERROR
Indicates the there is no feasible region.
CONDITION - INVALID-BOUNDS-ERROR
Indicates a problem with a variable’s bounds.
CONDITION - SOLVER-ERROR
The base class for errors that occur with the solving algorithm.
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/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 - 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-BASIS-COLUMNS (INSTANCE)
STRUCT - TABLEAU
Contains the necessary information for a simplex tableau.
FUNCTION - TABLEAU-VAR-COUNT (INSTANCE)
FUNCTION - TABLEAU-VARIABLE (TABLEAU VAR)
Gets the value of the given variable from the tableau
FUNCTION - COPY-TABLEAU (TABLEAU)
Copies the given tableau and it’s matrix.
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).
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 - N-PIVOT-ROW (TABLEAU ENTERING-COL CHANGING-ROW)
Destructively applies a single pivot to the table.
FUNCTION - TABLEAU-PROBLEM (INSTANCE)
FUNCTION - TABLEAU-INSTANCE-PROBLEM (INSTANCE)
FUNCTION - PIVOT-ROW (TABLEAU ENTERING-COL CHANGING-ROW)
Non-destructively applies a single pivot to the table.
FUNCTION - TABLEAU-OBJECTIVE-VALUE (TABLEAU)
Gets the objective function value in the tableau.
FUNCTION - N-SOLVE-TABLEAU (TABLEAU)
A non-consing version of solve-tableau.
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-CONSTRAINT-COUNT (INSTANCE)
FUNCTION - TABLEAU-MATRIX (INSTANCE)
PACKAGE - LINEAR-PROGRAMMING/EXPRESSIONS
Contains functions for processing linear expressions.
FUNCTION - PARSE-LINEAR-EXPRESSION (EXPR)
Parses the expression into a alist mapping variables to coefficients. Any
constant values are mapped to +constant+.
FUNCTION - FORMAT-LINEAR-EXPRESSION (ALIST)
Formats a linear expression as a sexp.
FUNCTION - SUM-LINEAR-EXPRESSIONS (&REST EXPRS)
Takes linear expressions and reduces it into a single expression.
FUNCTION - SCALE-LINEAR-EXPRESSION (EXPR SCALAR)
Multiplies the linear expression by the given scalar.