Mixed Integer Programming in Visual Basic QuickStart Sample

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

View this sample in: C# F# IronPython

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

    Module MixedIntegerProgramming

        ' Illustrates solving mixed integer programming problems
        ' using the classes in the Extreme.Mathematics.Optimization
        ' namespace of Extreme Numerics.NET.
        Sub Main()
        ' The license is verified at runtime. We're using
        ' a demo license here. For more information, see
        ' https://numerics.net/trial-key
        Extreme.License.Verify("Demo license")

        ' 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.NonzeroElements
            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(If(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(lp As LinearProgram, 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