VB Binary Linear Programming Example

← All NMath Code Examples

 

Imports System
Imports System.Linq

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

Namespace CenterSpace.NMath.Analysis.Examples.VisualBasic

  ' <summary>
  ' There are 6 cities in a region. The region wants to build the minimum
  ' number of fire stations in cities such that there is a fire station within 15 minutes
  ' of each city. The driving times in minutes between cities is given in the
  ' the following table.
  ' 
  '    From 1 2  3  4  5  6
  '    -----------------------
  '  To 1 | 0 10 20 30 30 20
  '     2 | 10 0 25 35 20 10
  '     3 | 20 25 0 15 30 20
  '     4 | 30 35 15 0 15 25
  '     5 | 20 20 30 15 0 14
  '     6 | 20 10 20 25 14 0
  ' 
  ' We can formulate this as an integer linear programming problem as
  ' follows:
  ' Define six variables x0, x1,..., x5, where
  ' xi = 1 if there is a fire station built in city i, and 0 otherwise.
  ' Then the total number of fire stations built is
  ' x0 + x1 + x2 + x3 + x4 + x5
  ' This is the objective function we want to minimize. Next we use
  ' the 15 minute maximum travel time to formulate our constraints.
  ' Consider city 0. From the table we see that in order to have at least
  ' one fire station 15 minutes away we must build a fire station in 
  ' city 0 and/or city 1. Formulated as a constraint it is:
  ' x0 + x1      >= 1 (City 0 constraint)
  ' Doing this for the other 5 cities we have
  ' x0 + x1 + x5 >= 1 (City 1 constraint)
  ' x2 + x3      >= 1 (City 2 constraint)
  ' x2 + x3 + x4 >= 1 (City 3 constraint)
  ' x3 + x4 + x5 >= 1 (City 4 constraint)
  ' x1 + x4 + x5 >= 1 (City 5 constraint)
  ' 

  ' </summary>
  Module BinaryLinearProgrammingExample

    Sub Main()

      ' The linear objective function is specified by its coefficients.
      ' In this problem the coefficient is 1.0 for each of the 6 variables,
      ' however, the the NMath solver is set up to *maximize* the objective
      ' function. To minimize the objective we must negate the coefficients
      ' of the linear objective function. Thus we set each of the 6 variables
      ' coefficients to -1 and construct the problem object from this 
      ' coefficient vector.
      Dim Problem As New MixedIntegerLinearProgrammingProblem(New DoubleVector(6, -1.0))

      ' Next we need to add our constraints. Since, like the objective function,
      ' the constraint functions are linear we need only specify their 
      ' coefficients. Each constraint coefficient is either 0 or 1, depending
      ' on whether or not the coefficient appears in the constraint. We
      ' encode the constraints using a 6 x 6 matrix where the jth row contains
      ' the coefficients for the constraint on the jth city.
      ' Since the matrix values are initialized to 0 on construction we need only
      ' set the values which are 1's.
      Dim ConstraintCoefficients As New DoubleMatrix(6, 6)

      ' City 0. x0 + x1
      ConstraintCoefficients(0, 0) = 1
      ConstraintCoefficients(0, 1) = 1

      ' City 1. x0 + x1 + x5
      ConstraintCoefficients(1, 0) = 1
      ConstraintCoefficients(1, 1) = 1
      ConstraintCoefficients(1, 5) = 1

      ' City 2. x2 + x3
      ConstraintCoefficients(2, 2) = 1
      ConstraintCoefficients(2, 3) = 1

      ' City 3. x2 + x3 + x4
      ConstraintCoefficients(3, 2) = 1
      ConstraintCoefficients(3, 3) = 1
      ConstraintCoefficients(3, 4) = 1

      ' City 4. x3 + x4 + x6
      ConstraintCoefficients(4, 3) = 1
      ConstraintCoefficients(4, 4) = 1
      ConstraintCoefficients(4, 5) = 1

      ' City 5. x1 + x4 + x5
      ConstraintCoefficients(5, 1) = 1
      ConstraintCoefficients(5, 4) = 1
      ConstraintCoefficients(5, 5) = 1

      ' Add the constraints to the problem. Each constraint
      ' is a lower bound constraint with a lower bound of 1.
      ' Now is also when we constraint the solution variables
      ' to be binary, 1 or 0, depending on whether we build or
      ' don't build a fire station in the city, respectively.
      Dim I As Integer
      For I = 0 To 5
        Problem.AddLowerBoundConstraint(ConstraintCoefficients.Row(I), 1.0)

        ' The ith variable in the solution must be 0 or 1.
        Problem.AddBinaryConstraint(I)
      Next

      ' Create the default primal simplex solver object and solve the problem.
      Dim Solver As New PrimalSimplexSolver()
      Solver.Solve(Problem)

      ' Print out the results.
      Console.WriteLine("Solver result: " & Solver.Result.ToString())
      Console.WriteLine()

      ' Print out the solution vector. The ith component of the vector
      ' is 1 if we build a fire station in city i and 0 otherwise.
      Console.WriteLine("The solution vector: " & Solver.OptimalX.ToString())

      ' Print out the optimal object function value. Note that we negated the
      ' objective function on input in order to minimize it, so we negate
      ' the optimal value.
      Console.WriteLine("The objective function value: " & -Solver.OptimalObjectiveFunctionValue)

      Console.WriteLine()

      ' Summarize
      Console.Write("Build fire stations in cities ")
      For I = 0 To Solver.OptimalX.Length - 1
        If (Solver.OptimalX(I) = 1) Then
          Console.Write("{0} ", I)
        End If
      Next

      Console.WriteLine()
      Console.WriteLine("Total of {0} fire stations.", -Solver.OptimalObjectiveFunctionValue)

      Console.WriteLine()
      Console.WriteLine("Press Enter Key")
      Console.Read()

    End Sub
  End Module
End Namespace
← All NMath Code Examples
Top