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 (IronPython)

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

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

import numerics

from System import Array

# The linear programming classes reside in their own namespace.
from Extreme.Mathematics.Optimization import *
# Vectors and matrices are in the Extreme.Mathematics namespace
from Extreme.Mathematics import *

# Illustrates solving mixed integer programming problems
# using the classes in the Extreme.Mathematics.Optimization
# namespace of the Extreme Optimization Numerical Libraries for .NET.

# 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.
lp = 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.
variables = Array.CreateInstance(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 row in range(9):
    for column in range(9):
        for digit in range(9):
            variables[row, column, digit] = lp.AddBinaryVariable("x{0}{1}{2}".format(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.
coefficients = Vector([ 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0 ])
def AddConstraints(lp, variable):
    for i in range(9):
        for j in range(9):
            variables = Array.CreateInstance(LinearProgramVariable, 9)
            for k in range(9):
                variables[k] = variable(i, j, k)
            lp.AddLinearConstraint(variables, coefficients, ConstraintType.Equal, 1.0)

# Rule 1: each posiion contains exactly one digit
AddConstraints(lp, lambda row, column, digit: variables[row, column, digit])
# Rule 2: each digit appears once in each row
AddConstraints(lp, lambda row, digit, column: variables[row, column, digit])
# Rule 3: each digit appears once in each column
AddConstraints(lp, lambda column, digit, row: variables[row, column, digit])
# Rule 4: each digit appears exactly once in each block
AddConstraints(lp, lambda 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:
rows = Array[int]([ 0,0,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,8,8 ])
columns = Array[int]([ 2,3,0,7,1,4,6,0,5,6,1,4,8,2,3,7,1,3,8,2,7,5,6 ])
digits = Array[float]([ 5,3,8,2,7,1,5,4,5,3,1,7,6,3,2,8,6,5,9,4,3,9,7 ])
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:
for triplet in board.NonzeroComponents:
    variables[triplet.Row, triplet.Column, triplet.Value - 1].LowerBound = 1.0

# Solve the linear program.
solution = lp.Solve()

# Scan the variables and print the digit if the value is 1.
for row in range(9):
    for column in range(9):
        theDigit = 0
        for digit in range(9):
            if variables[row, column, digit].Value == 1.0:
                theDigit = digit + 1
        print theDigit.ToString() if theDigit > 0 else ".",