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