Constraint programming is declarative. You formulate the problem and then ask the solver (Gecode) to find a solution. Problems are formulated as variables that have to be assigned values to satisfy specified constraints.
The following script formulates and solves the toy problem of finding
the integer x
such that x
times 5 equals 25.
require 'rubygems' require 'gecoder' include Gecode::Mixin x = int_var (x*5).must == 25 branch_on x solve! puts x.value
require 'rubygems' require 'gecoder' include Gecode::Mixin
Gecode::Mixin
is a mixin that provides all the methods used.
Mixing it into a class rather than into the top level context is advised
for serious use.
x = int_var (x*5).must == 25
Formulates the problem by, on the first line, creating an integer
variable x
and
then, on the second line, constraining 5 times any value assigned to x
to equal 25 (constraining the value assigned to x
to be a solution to
the problem).
There are many types of variables and ways to create
them. All
constraints can be recognized by
the use of #must
. The second line uses a property and a constraint
belonging to integer operands.
branch_on x
Tells Gecode/R that x
should be assigned a value to solve the problem.
In more complex examples there can be temporary variables that are only
used to help formulate the problem and do not need to be assigned a
specific value.
Branching is also used to specify how to explore the search space.
solve! puts x.value
The first line searches for a solution. The second line displays the value assigned to the variable in the solution.
Translating a problem into variables and constraints is not trivial. The translation affects how fast a solution is found. The modelling tutorial gives an introduction of how to perform the translation along with detailed examples.