← All NMath Code Examples
Imports System
Imports CenterSpace.NMath.Core
Namespace CenterSpace.NMath.Examples.VisualBasic
<summary>
A .NET example in Visual Basic showing how to solve the Klee Minty cube
linear programming problem Imports both primal and dual simplex methods
and various pivoting strategies.
The Klee Minty cube is a unit cube with perturbed corners. Klee and
Minty showed that Dantzigs simplex algorithm can have worst-case
performance with this cube as the feasible region.
</summary>
Module PrimalDualSimplexExample
Sub Main()
Dim N As Integer = 200
Dim LPProblem = KleeMintyCube(N)
Console.WriteLine("Klee Minty Cube LP problem Imports Primal Simplex:")
Console.WriteLine("---------------------------------------------------")
SolveKleeMintyProblemPrimal(LPProblem)
Console.WriteLine()
Console.WriteLine("Klee Minty Cube LP problem Imports Dual Simplex:")
Console.WriteLine("---------------------------------------------------")
SolveKleeMintyProblemDual(LPProblem)
Console.WriteLine()
Console.WriteLine("Press Enter Key")
Console.Read()
End Sub
<summary>
Solve the Klee Minty cube linear programming problem with the primal simplex
solver using different pivoting strategies.
</summary>
<param name="kleeMintyProblem">Klee Minty cube linear programming problem.</param>
Sub SolveKleeMintyProblemPrimal(kleeMintyProblem As LinearProgrammingProblem)
Create a solver parameters object with the desired values.
Here we set costing, or pivot strategy for selecting which
variable enters the basis on a pivot, the maximum number of pivots
to perform, tell the solver that we want to minimize, not maximize,
the objective function. If the maximum number of pivots is exceeded
the Result property of the solver will be SolveResult.SolverInterrupted.
Dim SolverParams As New PrimalSimplexSolverParams
SolverParams.Costing = PrimalSimplexCosting.Partial Use partial pivoting.
SolverParams.MaxPivotCount = 5000 Do not perform more than 5000 pivots
SolverParams.Minimize = True minimize, not maximize the objective function.
Create a primal simplex solver and solve with the above options.
Dim Solver As New PrimalSimplexSolver()
Solver.Solve(kleeMintyProblem, SolverParams)
Dim PartialPivotCount As Integer = Solver.PivotCount
Console.WriteLine("Primal Simplex Solver, Partial pivot strategy result: " & Solver.Result.ToString())
Console.WriteLine("Partial pivot strategy pivot count = " & PartialPivotCount)
Console.WriteLine()
Now solve with best reduced cost pivoting strategy. This is the
classic Dantzig rule.
SolverParams.Costing = PrimalSimplexCosting.BestReducedCost
Solver.Solve(kleeMintyProblem, SolverParams)
Dim BestReducedCostPivotCount As Integer = Solver.PivotCount
Console.WriteLine("Primal Simplex Solver, Best Reduced Cost result: " & Solver.Result.ToString())
Console.WriteLine("Best reduced cost pivot strategy pivot count = " & BestReducedCostPivotCount)
Console.WriteLine()
Is one pivoting strategy preferable?
If (PartialPivotCount < BestReducedCostPivotCount) Then
Console.WriteLine("For Primal Simplex prefer steepest edge for Klee Minty problem")
ElseIf (BestReducedCostPivotCount < PartialPivotCount) Then
Console.WriteLine("For Primal Simplex prefer best reduced cost for Klee Minty problem")
Else
Console.WriteLine("For Primal Simplex both pivoting strategies yield the same number of pivots.")
End If
End Sub
<summary>
Solve the Klee Minty cube linear programming problem with the dual simplex
solver Imports different pivoting strategies.
</summary>
<param name="kleeMintyProblem">Klee Minty cube linear programming problem.</param>
Sub SolveKleeMintyProblemDual(KleeMintyProblem As LinearProgrammingProblem)
Create a solver parameters object with the desired values. Note that
partial pivoting is not an available option for the dual simplex
solver.
Dim SolverParams As New DualSimplexSolverParams
SolverParams.Costing = DualSimplexCosting.SteepestEdge Use steepest edge pivoting.
SolverParams.MaxPivotCount = 5000
SolverParams.Minimize = True minimize, not maximize the objective function.
Create a dual simplex solver and solve with the above options.
Dim Solver As New DualSimplexSolver()
Solver.Solve(KleeMintyProblem, SolverParams)
Dim SteepestEdgePivotCount As Integer = Solver.PivotCount
Console.WriteLine("Dual Simplex Solver, Steepest Edge result: " & Solver.Result.ToString())
Console.WriteLine("Steepest edge pivot strategy pivot count = " & SteepestEdgePivotCount)
Console.WriteLine()
Now solve with the best reduced cost pivot strategy. This is the
classic Dantzig rule.
SolverParams.Costing = DualSimplexCosting.BestReducedCost
Solver.Solve(KleeMintyProblem, SolverParams)
Dim BestReducedCostPivotCount As Integer = Solver.PivotCount
Console.WriteLine("Dual Simplex Solver, Best Reduced Cost result: " & Solver.Result.ToString())
Console.WriteLine("Best reduced cost pivot strategy pivot count = " & BestReducedCostPivotCount)
Console.WriteLine()
Is one pivoting strategy preferable?
If (SteepestEdgePivotCount < BestReducedCostPivotCount) Then
Console.WriteLine("For Dual Simplex prefer steepest edge for Klee Minty problem")
ElseIf (BestReducedCostPivotCount < SteepestEdgePivotCount) Then
Console.WriteLine("For Dual Simplex prefer best reduced cost for Klee Minty problem")
Else
Console.WriteLine("For Dual Simplex both pivoting strategies yield the same number of pivots.")
End If
End Sub
<summary>
Create the Klee Minty cube linear programming problem with the given dimension.
</summary>
<param name="n">The desired number of vertices.</param>
<returns><c>LinearProgramming</c> object describing the Klee Minty
cube linear programming problem.</returns>
Function KleeMintyCube(N As Integer) As LinearProgrammingProblem
Dim ObjectiveCoeff As New DoubleVector(N)
ObjectiveCoeff(N - 1) = 1.0
Dim EPS As Double = 1.0 / 300.0
Dim Problem As New LinearProgrammingProblem(ObjectiveCoeff)
Problem.AddBounds(0, 0.0, 1.0)
Dim I As Integer
For I = 1 To N - 1
Lower bound constraint.
Dim LbConstraintCoeffs As New DoubleVector(N)
LbConstraintCoeffs(I) = 1.0
LbConstraintCoeffs(I - 1) = -EPS
Problem.AddLowerBoundConstraint(LbConstraintCoeffs, 0.0)
Upper bound constraint
Dim UbConstraintCoeffs As New DoubleVector(N)
UbConstraintCoeffs(I) = 1.0
UbConstraintCoeffs(I - 1) = EPS
Problem.AddUpperBoundConstraint(UbConstraintCoeffs, 1.0)
Next
Return Problem
End Function
End Module
End Namespace
← All NMath Code Examples
