ClpSimplexPrimal
Primal simplex algorithm implementation
Algorithm
Primal Simplex Method: Solves LP by maintaining primal feasibility (variables within bounds) while iterating toward dual feasibility (optimality). Each iteration:
- Choose entering variable (pivot column) - with negative reduced cost
- Compute pivot column of tableau: d = B^{-1} a_j (via FTRAN)
- Choose leaving variable (pivot row) - via ratio test on bounds
- Update basis: swap entering/leaving variables
- Update primal solution and reduced costs
Uses single-phase approach with infeasibilityCost_ weighting for handling infeasible starting points. Steepest edge or Dantzig strategies for pivot selection. Anti-degeneracy via cost perturbation (OSL heritage).
Three nested loops: outer handles fake bounds, middle handles refactorization, inner performs pivots until optimality or unboundedness detected.
$$\min;c^{T} x \text{ s.t. }Ax=b, l≤x≤u$$ $$Basic solution: x_{B} = B^{-1}b - B^{-1}N x_{N}, with x_{N} \text{ at }bounds.$$ $$\text{Reduced cost: }s_{j} = c_{j} - c_{B}^{T} B^{-1} a_{j} (computed via BTRAN then dot product)$$ $$\text{Ratio test: }θ* = \min{(x_{B}[i]-l_{i})/d_{i}, (u_{i}-x_{B}[i])/(-d_{i})} \text{ for }feasible step.$$ Primal feasible when l ≤ x ≤ u. Optimal when also s_j ≥ 0 for vars at lower bound.
Complexity: $O(m^{2} n)$ per iteration typical (dominated by FTRAN/BTRAN). Iteration count varies widely. Often slower than dual simplex but useful when starting from feasible solution or for problems with few constraints.
References:
- Dantzig, "Linear Programming and Extensions", Princeton (1963)
See Also
- ClpSimplex for the base simplex class
- ClpSimplexDual for dual simplex variant (often faster)
- ClpPrimalColumnPivot for pivot column selection strategies
- ClpPrimalColumnSteepest, ClpPrimalColumnDantzig for specific strategies
Source
Header file: `src/ClpSimplexPrimal.hpp`