# C# Binary Linear Programming Example

← All NMath Code Examples

```ï»¿using System;
using System.Linq;

using CenterSpace.NMath.Core;
using CenterSpace.NMath.Analysis;

namespace CenterSpace.NMath.Analysis.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 1's.
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
// don't 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.
}

// 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" );