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