← All NMath Code Examples
Imports System
Imports System.Linq
Imports CenterSpace.NMath.Core
Namespace CenterSpace.NMath.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 1s.
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
dont 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
