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.
        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
Top