Crate simplex_trace

Expand description

§simplex-trace

A simplex solver for linear programs that uses exact rational arithmetic and records every step (tableaus, ratio tests, pivots, phase changes) as plain data, so a teaching tool or UI can replay the method exactly as it is done by hand.

Supported methods: primal simplex, Big-M (with a symbolic M), two-phase and dual simplex. Variables are non-negative unless declared free or non-positive (see Sign). Every optimal solution includes a Sensitivity analysis (shadow prices, reduced costs and ranges), and reoptimize repairs it with dual simplex pivots after constraints are added, instead of solving again.

With the serde feature, Problem, Solution, Trace and every Step can be (de)serialized, e.g. to JSON for a web front end. Numbers are exact strings such as "3/2".

use simplex_trace::{solve, Method, Options, Problem, Relation, Status, ratio};

// min 4x1 + x2  s.t.  3x1 + x2 = 3,  4x1 + 3x2 >= 6,  x1 + 2x2 <= 4
let problem = Problem::minimize([4, 1])
    .subject_to([3, 1], Relation::Eq, 3)
    .subject_to([4, 3], Relation::Ge, 6)
    .subject_to([1, 2], Relation::Le, 4);

let solution = solve(&problem, Method::TwoPhase, &Options::default()).unwrap();
assert_eq!(
    solution.status,
    Status::Optimal { objective: ratio(17, 5), values: vec![ratio(2, 5), ratio(9, 5)] }
);

// Every tableau and pivot is available for display or replay.
for snapshot in solution.trace.tableaus() {
    println!("{snapshot}");
}

Structs§

Coef: A number of the form m·M + c, where M is the symbolic “big M” penalty.
Constraint: A linear constraint coeffs · x (relation) rhs.
ConstraintSensitivity: Sensitivity of one constraint.
DualRatioTest: One entry of the dual simplex ratio test, which runs over the columns of the leaving row.
Interval: A closed interval whose ends may be infinite (None).
NamedValue: A variable name with its value.
Options: Solver settings.
ParseRationalError: The error of parsing a Rational from a string that is not n or n/d with integers n and d != 0.
Problem: A linear program. Variables are non-negative unless declared free or non_positive.
RatioTest: One entry of the minimum-ratio test.
Rational: An arbitrary-precision exact rational number, always kept in lowest terms.
Sensitivity: Sensitivity analysis of an optimal solution, read from its final basis.
Snapshot: A full copy of the tableau at one point in time.
Solution: The status, the problem that was solved, the sensitivity analysis (when optimal) and the full step-by-step trace.
Source: A cell of the final tableau’s objective row.
Trace: The ordered list of everything the solver did.
VariableSensitivity: Sensitivity of one original variable.

Enums§

Error: Errors returned by solve and reoptimize.
Method: Which variant of the simplex method to run.
Phase: Stage of the algorithm a step belongs to.
PivotRule: Rule for choosing the entering column.
Relation: Relation of a constraint: <=, >= or = (also their JSON form with serde).
Sense: Whether the objective is maximized or minimized.
Sign: The sign restriction of a variable.
Status: Final result of a solve.
Step: One recorded event.
Termination: How a run ended.

Traits§

IntoRational: Conversion into a Rational, so the builder API accepts plain integers and fractions.

Functions§

ratio: Builds the fraction n / d. Panics if d == 0.
reoptimize: Re-optimizes a solved problem after appending constraints to it, with the dual simplex.
solve: Solves problem with the given method, recording every step.