← All NMath Code Examples
using System;
using System.Linq;
using CenterSpace.NMath.Core;
namespace CenterSpace.NMath.Examples.CSharp
{
/// <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>
public class BinaryLinearProgrammingExample
{
static void Main( string[] args )
{
// The linear objective function is specified 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.
var problem = 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. Eeach 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.
var constraintCoefficients = 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.
for ( int i = 0; i < 6; i++ )
{
problem.AddLowerBoundConstraint( constraintCoefficients.Row( i ), 1.0 );
// The ith variable in the solution must be 0 or 1.
problem.AddBinaryConstraint( i );
}
// Create the default primal simplex solver object and solve the problem.
var solver = new PrimalSimplexSolver();
solver.Solve( problem );
// Print out the results.
Console.WriteLine( "Solver result: " + solver.Result );
// 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 );
// 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 ( int i = 0; i < solver.OptimalX.Length; i++ )
{
if ( solver.OptimalX[i] == 1 )
Console.Write( "{0} ", i );
}
Console.WriteLine();
Console.WriteLine( "Total of {0} fire stations.", -solver.OptimalObjectiveFunctionValue );
Console.WriteLine();
Console.WriteLine( "Press Enter Key" );
Console.Read();
}
}
}
← All NMath Code Examples
