ï»¿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