Formulating Problems

Problems are formulated by using Gecode::Mixin to create variables and constraints such that the problem is solved by finding an assignment of the variables that satisfy all constraints.

Three things should always be specified:

Variables specify how to view the problem. A solution is an assignment of the variables.
Constraints are placed on the variables to ensure that a valid assignment of the variables is a solution to the problem.
Branching specifies how the search space should be explored and which variables that must be assigned.

Variables and Operands

Variables represent the problem’s search space. Each variable has a domain which represents all values that the variable can take. An integer variable with domain {0,1,...,9} can for instance take any value between 0 and 9.

Gecode deduces which values that a variable can not take and removes them from the domain. Once a variable only has one value left in its domain its said to be assigned that value. A solution to a problem is a valid assignment of the variables.

The different types of variables are:

Integer variables
Can be assigned integer values.
Boolean variables
Can be assigned either true or false.
Set variables
Can be assigned sets of integer values.


Variables are the most basic type of operands. It is common to work with arrays or enumerations of variables, which are also operands.

The different types of variables correspond to the following types of operands.

Integer variables
Act as integer operands. Enumerations of integer variables act as integer enumeration operands.
Boolean variables
Act as boolean operands. Enumerations of boolean variables act as boolean enumeration operands.
Set variables
Act as set operands. Enumerations of set variables act as set enumeration operands.

Creating Integer Variables

Use Mixin#int_var to create a new integer variable. The method takes one argument, the domain of the integer variable. The domain represents the values that the variable can take. A variable with domain 0..9 can for instance take any value in the range 0 to 9.

digit = int_var(0..9) # Creates an integer variable with domain 0..9.

The domain can be omitted, in which case the largest possible domain (Gecode::Mixin::MIN_INT to Gecode::Mixin::MAX_INT) is used.

number = int_var # An integer variable with the largest possible domain.

Alternatively one can also create multiple integer variables with the same domain at once using Mixin#int_var_array which returns an array of variables.

numbers = int_var_array(8, 0..9) # Creates 8 variables with domains 0..9.

The domain specified does not have to be a range, it can also be an enumeration of elements. The following creates an integer variable with the odd numbers in 0..9 as domain.

odd_number = int_var([1,3,5,7,9])

Matrices can be created using Mixin#int_var_matrix (returns an instance of Matrix).

number_matrix = int_var_matrix(5, 4, 0..9) # 5 rows and 4 columns.

Additional custom enumerations containing variables can be used, but they have to be wrapped using Mixin#wrap_enum first.

my_enum = wrap_enum(my_enum)

Creating Boolean Variables

Use any of Mixin#bool_var, Mixin#bool_var_array and Mixin#bool_var_matrix to create boolean variables. The methods work like the ones for integer variables, but do not require a domain.

bool = bool_var # Creates a boolean variable
bools = bool_var_array(3) # Creates 3 boolean variables.
bool_matrix = bool_var_matrix(3, 4) # Creates a 3x4 matrix of boolean variables.

Creating Set Variables

Use any of Mixin#set_var, Mixin#set_var_array and Mixin#set_var_matrix to create set variables. The domain of a set variable is specified through a greatest lower bound (GLB), a least upper bound (LUB) and the allowed cardinality (which is optional).

The greatest lower bound is the largest set of elements that are certain to be in the set. The least upper bound is the smallest set of elements that might be in the set (which should include the greatest lower bound). I.e. the greatest lower bound is a subset of the assigned set which is a subset of the least upper bound.

The bounds are specified as constant sets. The cardinality can only be specified with ranges or as a single number, which is then used as the minimum cardinality.

If no bounds are specified then the empty set is used as lower bound and the largest possible set as upper bound.

A constant set can be represented with instances of the following classes:
Represents a singleton set.
Represents a set containing all elements in the range. This represents the set more efficiently than when another enumeration with the same elements are used.
Enumeration of Fixnum
Represents a set containing the enumeration’s elements.
# Creates a set variable with glb 1..2 and lub 1..6 .
set = set_var(1..2, 1..6) 
# Creates an array of 3 set variables with the above bounds and a minimum 
# cardinality of 3.
sets = set_var_array(3, 1..2, 1..6, 3)
# Creates a 7x9 matrix of set variables with the above bounds and a cardinality 
# between 2 and 5
set_matrix = set_var_matrix(7, 9, 1..2, 1..6 2..5)

Accessing Variables from the Outside

It is often desirable to be able to access a variable from outside the class in order to e.g. access the selected values of the solution. One way to do this is to assign the variable to an instance variable and then add an accessor, but since it’s such a common operation a more convenient way has been added. Write <variable_name>_is_a <variable> or <variable_name>_is_an <variable>, replacing <variable_name> with the variable’s name and <variable> with the variable, to add an instance variable and accessor with the specified name.

To exemplify, The following two pieces of code are equivalent.
class Foo
  include Gecode::Mixin

  attr :digit

  def initialize
    @digit = int_var 0..9

    branch_on @digit
class Foo
  include Gecode::Mixin

  def initialize
    digit_is_an int_var(0..9)

    branch_on digit


Constraints specify what must hold for something to be a solution. They are placed on operands using using #must and #must_not in the following fashion:


For example, the following constrains int_operand to be strictly greater than 5.

int_operand.must > 5

Different operands support different constraints. See the documentation of each operand for a complete list.


Branching is when the solver has to make a guess about a variable’s value (possibly having to backtrack later if the guess was wrong). Branching is used as a last resort if the variable’s domain can’t be pruned any further using pure deduction.

The variables to branch over are specified using Mixin#branch_on.

branch_on numbers

Variables that are branched over are guaranteed to be assigned in the solution. Therefore branch over all variables that represent the solution to the problem. Multiple calls to branch_on can be used to branch over more than one enumeration of variables.

branch_on numbers
branch_on other_numbers

Branching Heuristics

The branching heuristic decides in which order guesses should be made when branching. Picking a good heuristic helps cut down the search space.

A common heuristic is first fail, which makes guesses about the variable with the smallest domain first. This exhausts the remaining possibilities of variables with small domains first, which reveals failures early in the search.

branch_on numbers, :variable => :smallest_size, :value => :min


Gecode::Model is a convenient class that only mixes in Gecode::Mixin. It is useful for creating models without mixin in Gecode::Mixin into the current context or creating a new class.

model =
var = model.int_var(0..9)
var.must > 5
model.branch_on var

p var.value