SimplexSolver<T>
Models & Types · AiDotNet.Solvers.LinearProgramming
Solves linear programs with the two-phase simplex method.
Implements: ILinearProgramSolver<T>
For Beginners
Picture the set of allowed choices as a many-sided crystal. Because the thing you are maximizing is linear, the best point is never in the middle of a face — it is always at a corner. So instead of searching everywhere, the method hops from corner to corner, always moving to a better one, and stops when every neighbouring corner is worse. That is the whole idea, and it is why linear programs of enormous size are routinely solved exactly.
How It Works
Implements Dantzig’s simplex method in tableau form (Dantzig, 1947; see also Nocedal and Wright, “Numerical Optimization”, chapter 13), with:
- a two-phase start, so no feasible point has to be supplied — phase one minimizes
the sum of artificial variables to find one, phase two optimizes the real objective;
- Bland’s anti-cycling rule engaged automatically after a run of degenerate pivots,
which guarantees termination on problems where Dantzig’s rule alone can cycle;
- dual values (shadow prices) recovered from the final tableau, so the solution
reports not just the answer but the marginal worth of every constraint.
The geometry. The constraints of a linear program carve out a polytope, and because the objective is linear, an optimum always sits at one of its corners (vertices). The simplex method exploits exactly this: it starts at a corner and repeatedly walks along an edge to an adjacent corner that improves the objective, stopping when no adjacent corner is better — at which point the corner is provably optimal, because a linear objective over a convex region has no local optima that are not global.
Constructors
| Constructor | Summary |
|---|---|
SimplexSolver(SimplexSolverOptions options) |
Creates a simplex solver. |
Methods
| Method | Summary |
|---|---|
LinearProgramSolution<T> Solve(LinearProgram<T> program) |