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

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.

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:- Fixnum
- Represents a singleton set.
- Range
- 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)

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