# 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

' The ith variable in the solution must be 0 or 1.
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")