Google SoC Series: Constraint programming with Ruby

Posted by Werner Schuster on Jun 08, 2007

Sections

Development,

Architecture & Design

Topics

Programming ,

Ruby ,

Domain Specific Languages

Tags

SoftwareParadigm ,

Google Summer of Code

Gecode/R, a Ruby Google SoC sponsored project, aims to make constraint programming available to Ruby developers. Andreas Launila, who develops the project, explains constraint programming: 

Constraint programming is a declarative programming paradigm, you describe what kind of solution you want rather than how you want it computed. When using constraint programming you try to model the problem and then feed that model to the solver. The solver then searches for a solution by exploring the space of all possible solutions while using the constraints in the model to prune parts without having to visit them.

A popular example would be Soduko, to solve a Soduko with constraint programming you feed the rules (all numbers in each row must be distinct etc) to the solver, which then searches for a solution satisfying all the constraints.

Asked for some examples of real world problems tackled with constraint programming, Andreas explains:

Constraint programming is typically used for NP-hard combinatorial problems where you have little choice but to do a search of some kind. Real world examples include scheduling, frequency allocation and crew rostering.

Gecode/R is actually a wrapper around Gecode, a C++ library for constraint programming. Andreas explains why he decided to make Gecode available in Ruby:

For me constraint programming is just another useful tool in the toolbox. It's a situational tool, but when used on the correct types of problems it saves time and performance. It can also be used to quickly (as in quick to code) solve problems where better algorithms are known but runtime performance is not of the essence (or the performance difference doesn't justify the additional time needed research and implement the algorithm).

An interesting aspect is the question of how to define the constraints with Ruby:

The goal is to make a front-end beyond mere bindings. I would call it more of a library than a DSL, but the boundaries are somewhat blurry. The exact syntax has not yet been decided (since the project has yet to start). The following quick mockup might give a small hint of the direction, but it's unlikely to be the syntax used. It solves the send+more=money problem.

In this approach the comparisons and arithmetic methods are used to express linear constraints. Array is extended to express distinct constraints and to select branching. The creation of variables would have to be hooked in order to keep track of them. A downside is that != is not defined as a method, so the syntax for inequality would be different from the rest.

Here how this would look like:

# The classic send+more=money problem.
class SendMoreMoneyProblem < Gecode::Space
 def initialize
  # Set up the variables, 8 letters with domain 0..9.
  s,e,n,d,m,o,r,y = letters = IntVar.array(8, 0..9)
  # Set up the constraints.
  constrain equation_row(s, e, n, d) + 
                 equation_row(m, o, r, e) ==
                 equation_row(m, o, n, e, y)
  constrain s.not_equal(0) # Not "s != 0" since we can't redefine != .
  constrain m.not_equal(0)
  letters.all_distinct
  # Pick a branch heuristic to use while searching for a solution.
  letters.branch_using(:variable => :min_size, :value => :min)
 end
private 
 # A helper to make the linear equation a bit tidier. Takes a number of 
 # variables and computes the linear combination as if the variable 
 # were digits in a base 10 number. E.g. x,y,z becomes
 # 100*x + 10*y + z .
 def equation_row(*variables)
  variables.inject(0){ |result, variable| variable + 10*result } 
 end
end

# Print the first solution to the problem.
p SendMoreMoneyProblem.new.solutions(:first)        

For more details about the  "send+more=money" problem see its  Wikipedia article.

When defining logic or or data in Ruby, there is always the possibility of using an internal DSL to allow for more concise, readable code. Andreas shows his ideas of how this might look:

Another approach would be to make something that looks more like a DSL, skipping classes and so on. This approach might be nicer for solving single simple problems quickly, but might hamper using constraint programming in conjunction with other Ruby code.

Here the code using the DSL approach:

find_first_solution_to define_problem do |p|
 # Set up the variables, 8 letters with domain 0..9.
 s,e,n,d,m,o,r,y = letters = p.create_int_vars(8, 0..9)
 # Set up the constraints.
 p.add 1000*s + 100*e + 10*n + d +
          1000*m + 100*o + 10*r + e ==
          10000*m + 1000*o + 100*n + 10*e + y
 p.add s.not_equal(0)
 p.add m.not_equal(0) 
 p.add all_distinct(letters) 
 # Pick a branch heuristic.
 p.branch_on letters, :variable => :min_size, :value => :min
end   

Since Gecode/R is a binding to a native library, there's the question of potential bottlenecks. Andreas is confident that this won't be a problem:

The propagators for the common constraints are implemented in Gecode, so the actual propagation of those constraints is done there. If the user defines custom propagators then there might be some jumping back and forth between C and Ruby (with the associate overhead), whether that will be a performance problem is unknown to me. Gecode is designed to be interfaced with from the outside though, and it works fine for Java, so I would be surprised if that part becomes a problem.

Gecode/R is a project hosted at RubyForge, so this would be a good place to start for interested developers. Ideas about the API or syntax for constraint specifications are collected in a dedicated Wiki page. Andreas also has a blog post about Gecode/R in the O'Reilly Ruby blog.

1. Back to top

   not_equal

   by Ola Bini

   Well, you can always make it easy for you and define not= instead.
   Then, instead of
   constrain m.not_equal(0)
   you have
   constrain m.not = 0

   Reply

• Older >