New Gecode/R models: langford, all_interval, alpha, golomb_ruler and some more
I have now started to model some of the Gecode examples, and some other things, in Gecode/R.
Langford's number problem (CSPLib problem 24
Langford's number problem is a classic problem in constraint programming. It is the problem 24 in the CSPLib collection.
The problem is defined as:
Arrange 2 sets of positive integers 1..k to a sequence,
such that, following the first occurence of an integer i,
each subsequent occurrence of i, appears i+1 indices later
than the last.
For example, for k=4, a solution would be 41312432
Also see
* John E. Miller: Langford's Problem
* Encyclopedia of Integer Sequences for the number of solutions for each k
* My MiniZinc model langford2.mzn
The Gecode/R model for this problem is langford.rb.
All interval problem (CSPLib problem 7)
Another CSP classic. CSPLib formulates the problem such:
Given the twelve standard pitch-classes (c, c#, d, ...), represented by
numbers 0,1,...,11, find a series in which each pitch-class occurs exactly
once and in which the musical intervals between neighbouring notes cover
the full set of intervals from the minor second (1 semitone) to the major
seventh (11 semitones)....
The constraints in the Gecode/R model all_interval.rb are simply
x_is_an int_var_array(n, 1..n) # The sequence
diffs_is_an int_var_array(n-1, 1..n-1) # The differences
x.must_be.distinct
diffs.must_be.distinct
(0..n-2).each{|k| diffs[k].must == (x[k+1] - x[k]).abs }
And two symmetry breaking constraints which, for n=12, which reduces the number of unique solution from 1328 (in 11 seconds) to 332 solutions (in 3 seconds).
x[0].must < x[1]
diffs[0].must > diffs[n-2]
The Gecode model all-interval (implemented in C++) solves the problem for n=1000 in 1 seconds. This Gecode/R model takes about 7 seconds after some tweaking with the :strength parameter.
Maybe I should benchmark the propagation strategies as for the Golomb ruler problem, see below.
Golomb ruler (CSPLib problem 6)
Yet another classic. See CSPLib problem number 6 for a formulation, and here for more references. Wikipedia's
This Gecode/R model golomb_ruler.rb was quite slow at first. When testing for m = 10 it took about 15 seconds, which was about twice as slow as the MiniZinc model (this is from the MiniZinc online examples).
Gecode's program golomb-ruler solves n = 12 slightly under 1 seconds (with default settings). Something had to be done!
After some tweaking, like setting :strength => :bounds without any satisfying result, I decided on a more "scientific" approach, and benchmarked (some of) the different branch/search strategies for the branch_on method. There is a lot of these in Gecode/R.
After about 30 minutes of running, the ranking list below was completed. Note: the time is for running the specific model, not counting the time for startup of the program.
The winner was
:variable => :largest_size, :value =>: split_min
which is used for all three variables in the model. Now m = 10 takes about 1 second.
The listing below states the time for the combination of the different strategies as
variable strategy ":" value strategy "->" running time
largest_size:split_min -> 1.114403 smallest_min:split_min -> 5.275035 smallest_min_regret:split_min -> 5.289433 none:split_min -> 5.320299 smallest_degree:split_min -> 5.344738 smallest_degree:min -> 5.551923 none:min -> 5.556326 smallest_min:min -> 5.567722 largest_max_regret:split_min -> 5.621116 smallest_min_regret:min -> 5.657271 largest_max_regret:min -> 5.783116 largest_size:min -> 6.067107 smallest_size:split_min -> 7.006949 largest_min:split_min -> 8.229713 smallest_size:min -> 11.800805 largest_min:split_max -> 14.558584 largest_min:min -> 14.736679 largest_min:max -> 17.301876 largest_size:split_max -> 17.564312 largest_min:med -> 23.655615 largest_size:max -> 26.835556 smallest_min:split_max -> 60.566207 largest_max_regret:split_max -> 60.605995 smallest_min_regret:split_max -> 60.79834 smallest_degree:split_max -> 60.948791 none:split_max -> 63.229398 smallest_size:split_max -> 80.155812 smallest_min_regret:max -> 84.988649 none:max -> 85.208536 smallest_degree:max -> 85.541162 largest_max_regret:max -> 85.64104 smallest_min:max -> 85.859321 smallest_size:max -> 93.474409 none:med -> 102.263753 largest_max_regret:med -> 103.352322 smallest_degree:med -> 103.688327 smallest_min:med -> 103.78953 smallest_size:med -> 131.829423 largest_size:med -> 160.26752 smallest_min_regret:med -> 181.760703
It is quite a span from the fastest to the slowest. It seems that :value => :med is bad for this problem.
alpha (alphametic problem)
Gecode/R model alpha.rb.
This alphametic problem asks for a solution of the equations below. The letters "a".."z" shall be unique assigned one and each of the numbers 1..26.
b+a+l+l+e+t == 45 c+e+l+l+o == 43 c+o+n+c+e+r+t == 74 f+l+u+t+e == 30 f+u+g+u+e == 50 g+l+e+e == 66 j+a+z+z == 58 l+y+r+e == 47 o+b+o+e == 53 o+p+e+r+a == 65 p+o+l+k+a == 59 q+u+a+r+t+e+t == 50 s+a+x+o+p+h+o+n+e == 134 s+c+a+l+e == 51 s+o+l+o == 37 s+o+n+g == 61 s+o+p+r+a+n+o == 82 t+h+e+m+e == 72 v+i+o+l+i+n == 100 w+a+l+t+z == 34
See also
* the Gecode program alpha.ccp
* the MiniZinc models crypto.mzn, crypto_ip.mzn (integer programming model).
global cardinality
global_cardinality.rb implements the global constraint global_cardinality (the link is to the wonderful collections of global constraints: Global Constraint Catalog).Nothing fancy, just this method, using the built in method count:
class Array
def global_cardinality(gcc)
@n = self.length
(@n).times{|i|
gcc[i].must == self.count(i)
}
end
end
Please note that this global constraint is just on the modellering level; there is no special (Gecode) code with optimized propagations etc. Even of they are not faster than "inline code", I see global constraints as conceptual building blocks, very useful in the modelling.
I intend to implement more global constraints in the future.
sliding sum
sliding_sum.rb implements another global constraint: sliding_sum, which constrain all sliding (running) sums to be between
low and high.