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.