# 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
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 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.

### Operands

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)
my_enum.must_be.distinct
```

### 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:
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)
```

### 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
end
end
```
```class Foo
include Gecode::Mixin

def initialize
digit_is_an int_var(0..9)

branch_on digit
end
end
```

## Constraints

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

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

`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
```