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 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:
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.
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) my_enum.must_be.distinct
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.
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:# 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)
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.
class Foo include Gecode::Mixin attr :digit def initialize @digit = int_var 0..9 branch_on @digit end end
class Foo include Gecode::Mixin def initialize digit_is_an int_var(0..9) branch_on digit end end
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:
operand.must.constraint_method(params)
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
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 = Gecode::Model.new var = model.int_var(0..9) var.must > 5 model.branch_on var model.solve! p var.value