New Version 6.0!

Try it for free with our fully functional 60-day trial version.

Download now!

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

Visual Basic code F# code IronPython code Back to QuickStart Samples

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>
        [STAThread]
        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);
            // To add integer variables, you can use the AddIntegerVariable method.
            // To add real variables, you can use the AddVariable method.

            // 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
            AddConstraints(lp, (block, digit, index) =>
                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
            // already on the board.

            // 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...");
            Console.ReadLine();
        }

        // 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[9];
                    for (int k = 0; k < 9; k++)
                        variables[k] = variable(i, j, k);
                    lp.AddLinearConstraint(variables, coefficients, ConstraintType.Equal, 1.0);
                }
        }
    }
}