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) and two-phase. All variables are non-negative. Every optimal solution includes a Sensitivity analysis: shadow prices, reduced costs and ranges.

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.
Interval: A closed interval whose ends may be infinite (None).
NamedValue: A variable name with its value.
Options: Solver settings.
Problem: A linear program with non-negative variables.
RatioTest: One entry of the minimum-ratio test.
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 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.
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.
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.
solve: Solves problem with the given method, recording every step.

Type Aliases§

Rational: Arbitrary-precision exact rational number used for every value in the crate.