# VB Primal Dual Simplex Example

← All NMath Code Examples

ï»¿Imports System

Imports CenterSpace.NMath.Core
Imports CenterSpace.NMath.Analysis

Namespace CenterSpace.NMath.Analysis.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 Dantzig's 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")

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)
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

'' Upper bound constraint
Dim UbConstraintCoeffs As New DoubleVector(N)
UbConstraintCoeffs(I) = 1.0
UbConstraintCoeffs(I - 1) = EPS