Module simplex_solver 

SimplexSolver — LP solver for parametric analysis.

This module provides a high-level LP interface used by simplex_parametric for sensitivity analysis and parametric optimization.

Algorithm

Uses the Big-M primal simplex method with exact BigRational arithmetic.

Standard Form Conversion

For each constraint a'x ≤ b, a'x ≥ b, or a'x = b:

• Le: add slack s ≥ 0 → a’x + s = b (s is initial basic variable)
• Ge: add surplus s ≥ 0 and artificial a ≥ 0 → a’x - s + a = b
• Eq: add artificial a ≥ 0 → a’x + a = b

Artificials appear in the objective with coefficient +M (Big-M method) so the primal simplex drives them to zero. Once all artificials = 0, the basis is feasible and the true objective is minimised.

Shadow Prices

Shadow prices are extracted from the objective row of the final tableau at the columns corresponding to slack variables. For a minimisation LP in standard form the shadow price of constraint i is −(reduced cost of its slack variable s_i), which equals the dual variable π_i.

Structs

Constraint

A linear constraint a'x {≤|≥|=} b.

SimplexSolver

High-level LP solver for parametric analysis.

SolveResult

Result returned by SimplexSolver::solve.

Enums

ConstraintKind

Sense of a linear constraint.

SimplexError

Error type for SimplexSolver.

SolveStatus

Status of a solve.