ClpSimplexDual
Dual simplex algorithm implementation
Algorithm
Dual Simplex Method: Solves LP by maintaining dual feasibility (reduced costs have correct signs) while iterating toward primal feasibility. Each iteration:
- Choose leaving variable (pivot row) - infeasible basic variable
- Compute pivot row of tableau: r^T = e_i^T B^{-1} A
- Choose entering variable (pivot column) - via ratio test on reduced costs
- Update basis: swap entering/leaving variables
- Update dual solution and reduced costs
Uses single-phase approach with fake bounds (updatedDualBound_) to handle dual infeasibility. 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 infeasibility detected.
$$\min;c^{T} x \text{ s.t. }Ax=b, l≤x≤u \text{ (primal)}$$ $$\text{Dual: }max b^{T} y \text{ s.t. }A^{T} y + s = c, s_{j}≥0 \text{ for }x_{j} \text{ at }\text{lower}, s_{j}≤0 \text{ for }x_{j} \text{ at }\text{upper}$$ $$\text{Reduced cost: }s_{j} = c_{j} - a_{j}^{T} y \text{ where }y = B^{-T} c_{B}$$ Dual feasible when reduced costs have correct signs for non-basic variables. $$\text{Ratio test: }θ* = \min{s_{j}/r_{j} : r_{j} \text{ has }\text{correct }\text{sign}} \text{ determines }\text{entering }\text{var.}$$
Complexity: $O(m^{2} n)$ per iteration typical (dominated by BTRAN/FTRAN). Iteration count highly problem-dependent. Often faster than primal simplex for problems with many constraints, especially after adding cuts in B&B.
References:
- Forrest & Goldfarb, "Steepest-edge simplex algorithms for LP", Mathematical Programming 57 (1992) 341-374
See Also
- ClpSimplex for the base simplex class
- ClpSimplexPrimal for primal simplex variant
- ClpDualRowPivot for pivot row selection strategies
- ClpDualRowSteepest, ClpDualRowDantzig for specific strategies
Source
Header file: `src/ClpSimplexDual.hpp`