Data Analysis Mathematics Linear Algebra Statistics
New Version 8.1!

Supports .NET 6.0. Try it for free with our fully functional 60-day trial version. QuickStart Samples

# Mixed Integer Programming QuickStart Sample (C#)

Illustrates how to solve mixed integer programming by solving Sudoku puzzles using the linear programming solver in C#.

```using System;

namespace Extreme.Numerics.QuickStart.CSharp
{
// The linear programming classes reside in their own namespace.
using Extreme.Mathematics.Optimization;
// Vectors and matrices are in the Extreme.Mathematics namespace
using Extreme.Mathematics;

/// <summary>
/// Illustrates solving mixed integer programming problems
/// using the classes in the Extreme.Mathematics.Optimization
/// namespace of the Extreme Optimization Numerical Libraries for .NET.
/// </summary>
class MixedIntegerProgramming {
/// <summary>
/// The main entry point for the application.
/// </summary>
static void Main(string[] args) {

// In this QuickStart sample, we'll use the Mixed Integer
// programming capabilities to solve Sudoku puzzles.
// The rules of Sudoku will be4 expressed in terms of
// linear constraints on binary variables.

// First, create an empty linear program.
var lp = new LinearProgram();

// Create an array of binary variables that indicate whether
// the cell at a specific row and column contain a specific digit.
// - The first index corresponds to the row.
// - The second index corresponds to the column.
// - The third index corresponds to the digit.
var variables = new LinearProgramVariable[9, 9, 9];

// Create a binary variable for each digit in each row and column.
// The AddBinaryVariable method creates a variable that can have values of 0 or 1.
for (int row = 0; row < 9; row++)
for (int column = 0; column < 9; column++)
for (int digit = 0; digit < 9; digit++)
variables[row, column, digit] = lp.AddBinaryVariable(string.Format("x{0}{1}{2}", row, column, digit), 0.0);

// Now add constraints that represent the rules of Sudoku.

// There are 4 rules in Sudoku. They are all of the kind
// where only one of a certain set of combinations
// of (row, column, digit) can occur at the same time.
// We can express this by stating that the sum of the corresponding
// binary variables must be one.

// AddConstraints is a helper function defined below.
// For each combination of the first two arguments,
// it builds a constraint by iterating over the third argument.

// Rule 1: each posiion contains exactly one digit
AddConstraints(lp, (row, column, digit) => variables[row, column, digit]);
// Rule 2: each digit appears once in each row
AddConstraints(lp, (row, digit, column) => variables[row, column, digit]);
// Rule 3: each digit appears once in each column
AddConstraints(lp, (column, digit, row) => variables[row, column, digit]);
// Rule 4: each digit appears exactly once in each block
variables[3 * (block % 3) + (index % 3), 3 * (block / 3) + (index / 3), digit]);

// We represent the board with a 9x9 sparse matrix.
// The nonzero entries correspond to the numbers

// Let's see if we can solve "the world's hardest Sudoku" puzzle:
// http://www.mirror.co.uk/fun-games/sudoku/2010/08/19/world-s-hardest-sudoku-can-you-solve-dr-arto-inkala-s-puzzle-115875-22496946/
int[] rows = { 0,0,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,8,8 };
int[] columns = { 2,3,0,7,1,4,6,0,5,6,1,4,8,2,3,7,1,3,8,2,7,5,6 };
double[] digits = { 5,3,8,2,7,1,5,4,5,3,1,7,6,3,2,8,6,5,9,4,3,9,7 };
var board = Matrix.CreateSparse(9, 9, rows, columns, digits);

// Now fix the variables for the for the digits that are already on the board.
// We do this by setting the lower bound equal to the upper bound:
foreach (var triplet in board.NonzeroElements)
variables[triplet.Row, triplet.Column, (int)triplet.Value - 1].LowerBound = 1.0;

// Solve the linear program.
var solution = lp.Solve();

// Scan the variables and print the digit if the value is 1.
for (int row = 0; row < 9; row++) {
for (int column = 0; column < 9; column++) {
int theDigit = 0;
for (int digit = 0; digit < 9; digit++)
if (variables[row, column, digit].Value == 1.0) {
theDigit = digit + 1;
break;
}
Console.Write(theDigit > 0 ? theDigit.ToString() : ".");
}
Console.WriteLine();
}

Console.Write("Press Enter key to exit...");
}

// Helper function that creates a constraint:
private static double[] coefficients = { 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0 };
private static void AddConstraints(LinearProgram lp, Func<int, int, int, LinearProgramVariable> variable) {
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++) {
var variables = new LinearProgramVariable;
for (int k = 0; k < 9; k++)
variables[k] = variable(i, j, k);