Tutorial

Introduction

Numberjack is a constraint optimisation platform, written in python. It allows rapid development of constraint satisfaction and optimisation problems. This document should cover the basics of specifying your problems in Numberjack and how to solve those problems.

Variables

Variables in Numberjack are specified by the constructors

var1 = Variable() # Creates a binary variable
var2 = Variable(lower, upper) # Creates a variable with domain [lower ... upper]
var3 = Variable([3,4,6]) # Creates a variable with a domain of the specified list

Variables are by default integer variables, special cases of continuous variables are possible but solver specific. They will be covered later on.

Expressions

Variable objects are expressions. Pretty much everything in Numberjack is an expression. Expressions have the following available methods

  •         get_value()
           
    If the problem has been solved returns the value of the expression. Return value is undefined if the problem is infeasable. Return type is also undefined if the problem has yet to be solved.
  •         __str__()
           
    Returns a string representation of the expression. If the expression has yet to be solved the string will be a representation of the model in string formet. For example a Sum expression might have the string representation of "Sum(x1 in [0,5], x2 in [1,3], x3 in [4,8])" where as a variable would have the string represention of "xN in [domain]" before solving and it's value after solving. This method allows printing of the objects with meaningful output.

There are many more methods to the Expression class, these are just the basics. We will cover more later.

VarArray

It is possible to create lists of variables with the same bounds all at once with the VarArray object.

vars1 = VarArray(5) # Creates a list of five binary variables
vars2 = VarArray(5, lower, upper) # Creates a list of five variables with domains
                                  # [lower, upper]

The VarArray object has some useful operators overridden:

  •                 vars1 < vars2
                   
    This creates a Less Lex constraint.
  •                 vars1 <= vars2
                   
    Creates the Leq Lex constraint.
  •                 vars1 > vars2
                   
    Creates the Gt Lex constraint.
  •                 vars1 >= vars2
                   
    Creates the Geq Lex constraint.
  •                 vars1[variable1]
                   
    Creates the Element expression. The value of this expression will be the value of the $n^{th}$ element of vars1 where n is equal to the value of variable1.
  •                 vars1[n]
                   
    On the other hand returns the $n^{th}$ element of the array, if n is an integer.
  •                 __str__()
                   
    This returns a string representation of the VarArray, it is the concatenation of the string representations of all the variables in the array. This methods allows printing of the object with sensible output.

Matrix

The Matrix construct can be seen to be an extension of the VarArray construct. It provides a method of creating and manipulating two dimensional matrices of variables.

square = Matrix(n, m) # Creates a n by m matrix of binary variables
square = Matrix(n, m, l, u) # Creates a n by m matrix if variables in domain [l,u]

The matrix construct, like the VarArray has many useful operators overridden.

  •                 __str__()
                   
    Returns the string representation of the matrix, it is the concatenation of the string representations of the Matrix's VarArray objects and the newline character. This methods allows printing of the object with sensible output.
  •                 matrix.flat
                   
    This is a list representing the flattened matrix.
  •                 matrix.row
                   
    This is a list representing the rows of the matrix
  •                 matrix.col
                   
    This is a list representing the columns of the matrix
  •                 matrix[n]
                   
    This returns the $n^{th}$ VarArray of the matrix
  •                 matrix[(expr1, expr2)]
                   
    This creates an element expression. If both expr1 and expr2 are indeed expressions then
    the expression will be
                    matrix.flat[(expr1 * len(matrix.col)) + expr2]
                   

    If one of expr1 or expr2 are integers then the element construct is on the rows or columns of the integer index with the
    expression being variable. i.e
                    matrix.row[expr1][expr2] # If expr1 is an integer
                    matrix.col[expr2][expr1] # If expr2 is an integer
                   

The Model

The model is where Numberjack problems are specified, it contains knowledge of the variables and constraints. Models are solver independent and can be solved by multiple solvers. Models can be constructed in two ways, constraints can be specified upon construction, constraints can be added as needed or you can do both.

model = Model() # To create an empty model

model = Model([
    constraint1,
    constraint2,
    .
    .
    .
    constraintN
]) # To create a model with some constraints already added.

Once you have a model created you can add constraints, lists of constraints of n-dimensional matrices of constraints to the model

model.add(constraints)
# or
model += constraints

You can also print your model ad the $\_\_str\_\_()$ function has been overridden. The model as a string outlines all the variables and constraints on those variables in the problem.

Constraints

Numberjack supports an ever growing catalog of constraints. Not all constraints are implemented in every solver though, for example an element constraint is pretty tricky to implement in a linear solver. We are constantly working on adding support for constraints in solvers.

Binary Operators

All binary operator constraints are implemented by overriding the associated function of the expression class. These operators then create an expression that can be used in expression trees.

  • Multiplication
            expr1 * expr2
           
    Creates an expression that had the value of expr1 * expr2, expr2 can be either a variable or a constant.
  • Division
            expr1 / expr2
           
    Creates an expression that had the value of expr1 / expr2, expr2 can be either a variable or a constant.
  • Add
            expr1 + expr2
           
    Creates an expression that had the value of expr1 + expr2, expr2 can be either a variable or a constant.
  • Subtract
            expr1 - expr2
           
    Creates an expression that had the value of expr1 - expr2, expr2 can be either a variable or a constant.
  • Modulo
            expr1 % expr2
           
    Creates an expression that had the value of expr1 \% expr2, expr2 can be either a variable or a constant.
  • Equal
            expr1 == expr2
           
    Creates an expression that had the value of 1 if expr1 $=$ expr2 and 0 otherwise, expr2 can be either a variable or a constant.
  • Not Equal
            expr1 != expr2
           
    Creates an expression that had the value of 1 if expr1$\neq$ expr2 and 0 otherwise, expr2 can be either a variable or a constant.
  • Less than or Equal
            expr1 <= expr2
           
    Creates an expression that had the value of 1 if expr1$\leq$ expr2 and 0 otherwise, expr2 can be either a variable or a constant.
  • Less than
            expr1 < expr2
           
    Creates an expression that had the value of 1 if expr1$<$ expr2 and 0 otherwise, expr2 can be either a variable or a constant.
  • Greater than or Equal
            expr1 >= expr2
           
    Creates an expression that had the value of 1 if expr1 $\geq$ expr2 and 0 otherwise, expr2 can be either a variable or a constant.
  • Greater than
            expr1 > expr2
           
    Creates an expression that had the value of 1 if expr1 $>$ expr2 and 0 otherwise, expr2 can be either a variable or a constant.
  • Logical And
            expr1 & expr2
           
    Creates an expression that had the value of 1 if expr1 \& expr2 and 0 otherwise. Both expr1 and expr2 are expected to binary variables. The constraint is undefined if this is not the case.
  • Logical Or
            expr1 | expr2
           
    Creates an expression that had the value of 1 if expr1 $|$ expr2 and 0 otherwise. Both expr1 and expr2 are expected to binary variables. The constraint is undefined if this is not the case.

Other constraints

There are many other constraints available in Numberjack. These though are specified as function calls not as operators on Variables.

  • Sum
            Sum(VarArray)
            Sum([var1, var2, var4])
            Sum([var1, var2, var3], [coef1, coef2, coef3])
           
    There are many ways of specifying the Sum constraint. It is an expression representing the sum of the variables, or the sum of the variables times the coefficients if there are coefficients provided. Something worth noting is that the Sum constraint is intelligent, in that it parses the expression trees below it to see if there are + or * operators or other Sum constraints under it that could be integrated in itself. This allows for some elegant specification of scalar products that is still efficient.
  • AllDIff
            AllDiff(VarArray)
            AllDiff([var1, var2, var3])
           
    The classic global constraint, this constraints all the variables specified as a list argument to take on different values.
  • Element

    We have already covered the element constraint in the VarArray and Matrix sections.

Reification

Since all boolean constraints are also expressions reification is possible in Numberjack. All you have to do is treat these constraints as expressions. For example to count the number of times 5 appears in a VarArray all you need to do is

Sum([var == 5 for var in VarArray])

Optimisation

Optimisation is possible in Numberjack. To specify an objective function to be maximised or minimised just use the following functions

model.add(Maximise(obj)) # For maximisation
model.add(Minimise(obj)) # For minimisation

where obj is an expression representing what needs to be optimised.

Solvers

There are currently four solvers available with Numberjack. Their support of constraints varies wildly. They do all share a common API though, some useful methods are

  •                 solver = Solver(model)
                   
    This creates the solver object
  •                 solve()
                   
    This attempts to solve the problem. Returns true if the problem is satisfiable and false otherwise.
  •                 printStatistics()
                   
    This prints some useful statistics about solving.
  • }
                    setVerbosity(n)
                   
    This will set the solver verbosity level to different levels, usually 0, 1 and 2

Mistral

Mistral is the best supported solver in Numberjack. It supports all the constraints available. It is a state of the art C++ solver. It has added functionality on the normal solver of allowing you to specify the decision variables.

solver = Solver(model, decision_variables)
where decision\_variables is a list containing the decision variables.

To use Mistral you have to either

import Mistral
solver = Mistral.Solver(model)
# or
from Mistral import Solver
solver = Solver(model)

SCIP

SCIP is a state of the art open source MIP solver. It can handle a wide range of constraints. It has the extra functionality of being able to handle continuous variables. To create a continuous variable for SCIP to use all you need to do is specify the variable bounds as floats as opposed to integers e.g.

var = Variable(0.0, 10.0) # As opposed to
var = Variable(0, 10)

To use SCIP you have to either

import SCIP
solver = SCIP.Solver(model)
# or
from SCIP import Solver
solver = Solver(model)

SCIP is excellent at optimisation problems where as it struggles at some satisfiability problems.

MiniSat

MiniSat as an underlying solver is still very much in development. There is a small subset of constraints currently supported.

To use MiniSat you have to either

import MiniSat
solver = MiniSat.Solver(model)
# or
from MiniSat import Solver
solver = Solver(model)

NumberjackSolver

NumberjackSolver is a native python constraint solver that is almost fully supports the constraints in Numberjack. It is useful for testing and for finding out how a solver works. It is also quite portable. It is very slow though and not recommended for large problems.

To use NumberjackSolver you have to either

import NumberjackSolver
solver = NumberjackSolver.Solver(model)
# or
from NumberjackSolver import Solver
solver = Solver(model)