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 (Visual Basic)

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

C# code F# code IronPython code Back to QuickStart Samples

Option Infer On

' The linear programming classes reside in their own namespace.
Imports Extreme.Mathematics.Optimization
' Vectors and matrices are in the Extreme.Mathematics namespace
Imports Extreme.Mathematics
Imports Extreme.Mathematics.LinearAlgebra

Namespace Extreme.Numerics.QuickStart.VB

    Module MixedIntegerProgramming

        ' Illustrates solving mixed integer programming problems
        ' using the classes in the Extreme.Mathematics.Optimization
        ' namespace of the Extreme Optimization Numerical Libraries for .NET.
        Sub Main()
            ' 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.
            Dim lp As 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.
            Dim variables(8, 8, 8) As LinearProgramVariable

            ' 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 As Integer = 0 To 8
                For column As Integer = 0 To 8
                    For digit As Integer = 0 To 8
                        Dim name As String = String.Format("x{0}{1}{2}", row, column, digit)
                        variables(row, column, digit) = lp.AddBinaryVariable(name, 0.0)
                    Next
                Next
            Next

            ' 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, Function(row, column, digit) variables(row, column, digit))
            ' Rule 2: each digit appears once in each row
            AddConstraints(lp, Function(row, digit, column) variables(row, column, digit))
            ' Rule 3: each digit appears once in each column
            AddConstraints(lp, Function(column, digit, row) variables(row, column, digit))
            ' Rule 4: each digit appears exactly once in each block
            AddConstraints(lp, Function(block, digit, index) _
                variables(3 * (block Mod 3) + (index Mod 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/
            Dim rows() = {0, 0, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 8, 8}
            Dim columns() = {2, 3, 0, 7, 1, 4, 6, 0, 5, 6, 1, 4, 8, 2, 3, 7, 1, 3, 8, 2, 7, 5, 6}
            Dim digits() As Double = {5, 3, 8, 2, 7, 1, 5, 4, 5, 3, 1, 7, 6, 3, 2, 8, 6, 5, 9, 4, 3, 9, 7}
            Dim 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 Each triplet In board.NonzeroComponents
                variables(triplet.Row, triplet.Column, CInt(triplet.Value) - 1).LowerBound = 1.0
            Next

            ' Solve the linear program.
            Dim solution = lp.Solve()

            ' Scan the variables and print the digit if the value is 1.
            For row As Integer = 0 To 8
                For column As Integer = 0 To 8
                    Dim theDigit As Integer = 0
                    For digit As Integer = 0 To 8
                        If (variables(row, column, digit).Value = 1.0) Then
                            theDigit = digit + 1
                            Exit For
                        End If
                    Next
                    Console.Write(IIf(theDigit > 0, theDigit.ToString(), "."))
                Next
                Console.WriteLine()
            Next

            Console.Write("Press Enter key to exit...")
            Console.ReadLine()

        End Sub

        ' Helper function that creates a constraint:
        Dim coefficients() As Double = {1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0}
        Sub AddConstraints(ByVal lp As LinearProgram, ByVal variable As Func(Of Integer, Integer, Integer, LinearProgramVariable))
            For i As Integer = 0 To 8
                For j As Integer = 0 To 8
                    Dim variables(8) As LinearProgramVariable
                    For k As Integer = 0 To 8
                        variables(k) = variable(i, j, k)
                    Next
                    lp.AddLinearConstraint(variables, coefficients, ConstraintType.Equal, 1.0)
                Next
            Next
        End Sub

    End Module

End Namespace