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