Getting Started

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.

Toy Example

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

Setting Up

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.

Formulating the Problem

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.

Finding the Solution

solve!
puts x.value

The first line searches for a solution. The second line displays the value assigned to the variable in the solution.

Modelling Problems

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.