`linear_programming`

The linear_programming library provides immutable construction and solving of small linear and mixed-integer linear programs. The simplex backend is a portable dense two-phase tableau implementation supporting Bland’s and Dantzig’s pivot rules. The milp_branch_and_bound backend provides deterministic depth-first branch-and-bound over simplex LP relaxations.

The model API supports continuous, integer, and binary variable declarations. The simplex backend solves continuous models only and throws a domain_error(simplex_variable_type, Variable-Type) error for other variable types. Use milp_branch_and_bound to solve models containing integer or binary variables.

API documentation

Open the ../../apis/library_index.html#linear-programming link in a web browser.

Loading

To load all entities in this library, load the loader.lgt file:

| ?- logtalk_load(linear_programming(loader)).

Testing

To test this library, load the tester.lgt file:

| ?- logtalk_load(linear_programming(tester)).

Model representation

Variables are identified by unique ground terms. Linear expressions are lists of Coefficient*Variable terms. Repeated variables are combined and zero coefficients are removed. Arithmetic expression trees such as [2*x + 3*y] are not accepted; write [2*x, 3*y] instead.

Continuous and integer variables default to bounds 0 and inf. Binary variables default to bounds 0 and 1. Explicit bounds are numbers, -inf for an absent lower bound, or inf for an absent upper bound.

Continuous solving

The simplex backend solves continuous linear programs using a portable dense two-phase tableau implementation. The supported options are:

max_iterations(PositiveInteger) - Maximum number of iterations shared by both simplex phases (default: 10000).
tolerance(PositiveNumber) - Numerical tolerance (default: 1.0e-9).
pivot_rule(Rule) - Pivot rule, either bland (the default), which selects the first eligible entering column, or dantzig, which selects the eligible column with the most negative reduced cost, breaking ties by the lowest column index.

| ?- simplex::( new_problem(P0), variable(x, continuous, P0, P1), variable(y, continuous, P1, P2), constraint([1x, 2y], =<, 14, P2, P3), constraint([3x, -1y], >=, 0, P3, P4), objective([3x, 4y], maximize, P4, P), solve(P, Result), status(Result, Status), variable_value(Result, x, X), variable_value(Result, y, Y), objective_value(Result, Value) ). Status = optimal, X = 14.0, Y = 0, Value = 42.0.

Dense matrix conversion

The problem_from_matrices/8 predicate converts a dense standard-form input to the same immutable model. Equality rows are represented by Aeq and Beq; inequality rows are represented by Aineq and Bineq and always mean Aineq*x =< Bineq. Variables are named by one-based column indices.

| ?- simplex::problem_from_matrices(
         [3,4], maximize,
         [], [],
         [[1,2],[-3,1]], [14,0],
         [0-inf,0-inf], Problem
     ),
     simplex::solve(Problem, Result).

Results and errors

Solver statuses are optimal, infeasible, unbounded, iteration_limit, node_limit, and numerical_error. Only an optimal result contains variable values and an objective value. The corresponding inspector predicates fail for other statuses. Malformed problems and unsupported backend capabilities throw errors instead of being reported as mathematical solver statuses.

Mixed-integer solving

The milp_branch_and_bound backend supports mixed continuous, integer, and binary models. Integer and binary variables must have finite bounds and each integer domain must contain at least one integer. The solver proves optimality by exhausting or bounding the search tree; it does not use cutting planes or primal heuristics.

The supported options are:

max_nodes(PositiveInteger) - Maximum number of search nodes (default: 10000).
integrality_tolerance(PositiveNumber) - Integrality tolerance (default: 1.0e-9).
simplex_max_iterations(PositiveInteger) - Maximum simplex iterations per LP relaxation (default: 10000).
simplex_tolerance(PositiveNumber) - Simplex numerical tolerance (default: 1.0e-9).
simplex_pivot_rule(Rule) - Simplex pivot rule for all LP relaxations (default: bland).
branching_rule(Rule) - Branching rule, either first_fractional (the default), which selects the first fractional discrete variable in declaration order, or most_fractional, which selects the variable whose value is farthest from its nearest integer, breaking ties by declaration order.
branch_order(Order) - Child traversal order, either lower_first (the default) or upper_first.

| ?- milp_branch_and_bound:: new_problem(P0), variable(x, binary, P0, P1), variable(y, binary, P1, P2), constraint([2x, 2y], =<, 3, P2, P3), objective([1x, 1y], maximize, P3, P), solve(P, Result ).

Limitations

Both backends use dense lists and are intended for small problems.

The library does not currently implement presolve beyond bound and standard-form normalization, sparse storage, cutting planes, dual values, reduced costs, basis export, warm starts, time limits, callbacks, or parallel search.

linear_programming