Prolog - golomb size 13 solved by clp(FD)

Author

golomb size 13 solved by clp(FD)

nengfazhou@gmail.com

2007-11-20, 7:09 pm

c:\george>bp
B-Prolog Version 7.1b1, All rights reserved, (C) Afany Software
1994-2007.
Licensed for educational and nonprofit research uses only.

| ?- cl(golomb)
Compiling::golomb.pl
compiled in 16 milliseconds
loading::golomb.out

yes
| ?- go
[0,2,5,25,37,43,59,70,85,89,98,99,106]
time(-217433257)

A solution to the golomb 13 problem was found over the w

end
(obviously the time integer overflowed) on my PC (Pentium 4, 3GHz,
1GRAM). Is this the largest problem instance that has been solved by
CLP(FD)? In the tutorial, solutions are given to instances up to size
12.

go:-
cputime(Start),
golomb(13,Sol),
cputime(End),
T is End-Start,
writeln(Sol),
writeln(time(T)).

/*
Taken from PRACTICAL CONSTRAINTS: A TUTORIAL ON MODELLING WITH
CONSTRAINTS,
by ROMAN BART=81=C1K
*/
golomb(M,Sol):-
Sol =3D [0|_],
UpperBound is M*M,
ruler(M,-1,UpperBound,Sol),
last(Sol,XM),
distances(Sol,1,M,XM,Dist),
all_distinct(Dist),
(Dist=3D[DF,_|_] ->
last(Dist,DL), DF#<DL
;
true
),
minimize(labeling([ff],Sol),XM).

ruler(0,_,_,[]).
ruler(K,PrevX,UpperBound,[X|Rest]):-
K>0,
PrevX#<X, X#=3D<UpperBound,
K1 is K-1,!,
ruler(K1,X,UpperBound,Rest).

distances([],_,_,_,[]).
distances([X|Rest],I,M,XM,Dist):-
J is I+1,
distances_from_x(Rest,X,I,J,M,XM,Dist,Re
stDist),
I1 is I+1,!,
distances(Rest,I1,M,XM,RestDist).
distances_from_x([],_,_,_,_,_,RestDist,R
estDist).

distances_from_x([Y|Rest],X,I,J,M,XM,[DX
Y|Dist],RestDist):-
DXY #=3D Y-X,
LowerBound is integer(((J-I)*(J-I+1))/2),
LowerBound #=3D< DXY,
UpperBoundP is integer(((M-1-J+I)*(M-J+I))/2),
DXY #=3D< XM - UpperBoundP,
J1 is J+1,!,
distances_from_x(Rest,X,I,J1,M,XM,Dist,R
estDist).

last([X],X):-!.
last([_|Xs],X):-last(Xs,X).

minimize(Choice,Exp):-minof(Choice,Exp).

zayenz@gmail.com

2007-11-22, 8:07 am

On Nov 20, 4:53 pm, nengfaz...@gmail.com wrote:
> c:\george>bp
> B-Prolog Version 7.1b1, All rights reserved, (C) Afany Software
> 1994-2007.
> Licensed for educational and nonprofit research uses only.
>
> | ?- cl(golomb)
> Compiling::golomb.pl
> compiled in 16 milliseconds
> loading::golomb.out
>
> yes
> | ?- go
> [0,2,5,25,37,43,59,70,85,89,98,99,106]
> time(-217433257)
>
> A solution to the golomb 13 problem was found over the w

end
> (obviously the time integer overflowed) on my PC (Pentium 4, 3GHz,
> 1GRAM). Is this the largest problem instance that has been solved by
> CLP(FD)? In the tutorial, solutions are given to instances up to size
> 12.

Out of interest, I tested the Golomb ruler example supplied with
Gecode [1] on my machine (AMD Athlon(tm) 64 Processor 3500+, 2 GB RAM,
running Linux 2.6.15). The example has two models using lower bounds
from [2]. The simpler one uses an algebraic lower bound, while the
more advanced uses bounds from smaller rulers (which are assumed to be
known).

With the simple model, it took 48 minutes of user-time to find the
solution for a 13-marker Golomb Ruler. Using the more advanced model,
it took 14 minutes. Full output of the runs of the program is included
below.

Cheers,
Mikael Lagerkvist

[1] http://www.gecode.org/gecode-doc-la...olombRuler.html
[2] "Modelling the Golomb Ruler Problem", Barbara M. Smith, Kostas
Stergiou, Toby Walsh, IJCAI'99 Workshop on Non-binary Constraints,
http://citeseer.ist.psu.edu/282979.html

Output from the runs of the program:
zayenz@emma:~/gecode$ time ./examples/golomb-ruler 12
GolombRuler
m[12] = {0, 1, 3, 7, 12, 20, 30, 44, 65, 80, 96, 122}
m[12] = {0, 1, 3, 7, 12, 20, 30, 44, 65, 90, 105, 121}
m[12] = {0, 1, 3, 7, 12, 20, 30, 45, 61, 82, 96, 118}
m[12] = {0, 1, 3, 7, 12, 20, 34, 49, 72, 90, 100, 116}
m[12] = {0, 1, 3, 7, 12, 20, 34, 50, 60, 75, 96, 114}
m[12] = {0, 1, 3, 7, 12, 22, 38, 46, 63, 86, 99, 113}
m[12] = {0, 1, 3, 7, 12, 22, 38, 51, 65, 85, 93, 110}
m[12] = {0, 1, 3, 7, 12, 26, 34, 50, 63, 78, 98, 108}
m[12] = {0, 1, 3, 7, 12, 26, 42, 59, 74, 87, 95, 105}
m[12] = {0, 1, 3, 7, 15, 32, 56, 65, 76, 86, 99, 104}
m[12] = {0, 1, 3, 7, 16, 26, 40, 48, 68, 86, 98, 103}
m[12] = {0, 1, 3, 7, 16, 27, 39, 58, 68, 76, 93, 98}
m[12] = {0, 1, 3, 8, 18, 32, 38, 60, 71, 83, 87, 96}
m[12] = {0, 1, 3, 8, 19, 31, 48, 57, 70, 84, 90, 94}
m[12] = {0, 1, 3, 14, 33, 40, 56, 64, 76, 81, 85, 91}
m[12] = {0, 2, 6, 24, 29, 40, 43, 55, 68, 75, 76, 85}

Initial
propagators: 67
branchings: 1

Summary
runtime: 169320
solutions: 16
propagations: 806264749
failures: 2656663
clones: 2656694
commits: 8268929
peak memory: 199 KB

real 3m16.221s
user 2m49.199s
sys 0m0.136s

zayenz@emma:~/gecode$ time ./examples/golomb-ruler 13
GolombRuler
m[13] = {0, 1, 3, 7, 12, 20, 30, 44, 65, 80, 96, 122, 147}
m[13] = {0, 1, 3, 7, 12, 20, 30, 44, 69, 90, 105, 121, 143}
m[13] = {0, 1, 3, 7, 12, 20, 30, 45, 61, 85, 107, 128, 142}
m[13] = {0, 1, 3, 7, 12, 20, 34, 49, 72, 90, 100, 116, 140}
m[13] = {0, 1, 3, 7, 12, 20, 34, 52, 62, 77, 100, 116, 137}
m[13] = {0, 1, 3, 7, 12, 20, 35, 53, 75, 91, 112, 122, 136}
m[13] = {0, 1, 3, 7, 12, 22, 30, 46, 66, 79, 104, 121, 135}
m[13] = {0, 1, 3, 7, 12, 22, 35, 49, 73, 89, 106, 114, 132}
m[13] = {0, 1, 3, 7, 12, 22, 39, 53, 73, 86, 102, 110, 128}
m[13] = {0, 1, 3, 7, 12, 26, 43, 58, 71, 87, 95, 105, 125}
m[13] = {0, 1, 3, 7, 12, 27, 44, 60, 74, 82, 95, 105, 124}
m[13] = {0, 1, 3, 7, 15, 28, 38, 47, 64, 88, 106, 117, 122}
m[13] = {0, 1, 3, 7, 15, 32, 56, 72, 82, 93, 102, 115, 120}
m[13] = {0, 1, 3, 7, 17, 35, 50, 62, 71, 91, 102, 110, 115}
m[13] = {0, 1, 3, 9, 33, 45, 61, 74, 88, 92, 99, 109, 114}
m[13] = {0, 1, 3, 10, 26, 41, 46, 65, 78, 95, 99, 107, 113}
m[13] = {0, 1, 3, 11, 26, 45, 59, 65, 83, 96, 100, 105, 112}
m[13] = {0, 1, 3, 12, 19, 36, 59, 73, 81, 86, 101, 107, 111}
m[13] = {0, 1, 3, 23, 32, 42, 47, 58, 85, 92, 98, 106, 110}
m[13] = {0, 1, 10, 27, 35, 47, 50, 66, 80, 98, 102, 104, 109}
m[13] = {0, 2, 5, 25, 37, 43, 59, 70, 85, 89, 98, 99, 106}

Initial
propagators: 79
branchings: 1

Summary
runtime: 2.86544e+06
solutions: 21
propagations: 13982453653
failures: 35497249
clones: 35497290
commits: 109114896
peak memory: 264 KB

real 51m53.406s
user 47m43.523s
sys 0m1.928s

zayenz@emma:~/gecode$ time ./examples/golomb-ruler -model ruler 13
GolombRuler
m[13] = {0, 1, 3, 7, 12, 20, 30, 44, 65, 80, 96, 122, 147}
m[13] = {0, 1, 3, 7, 12, 20, 30, 44, 69, 90, 105, 121, 143}
m[13] = {0, 1, 3, 7, 12, 20, 30, 45, 61, 85, 107, 128, 142}
m[13] = {0, 1, 3, 7, 12, 20, 34, 49, 72, 90, 100, 116, 140}
m[13] = {0, 1, 3, 7, 12, 20, 34, 52, 62, 77, 100, 116, 137}
m[13] = {0, 1, 3, 7, 12, 20, 35, 53, 75, 91, 112, 122, 136}
m[13] = {0, 1, 3, 7, 12, 22, 30, 46, 66, 79, 104, 121, 135}
m[13] = {0, 1, 3, 7, 12, 22, 35, 49, 73, 89, 106, 114, 132}
m[13] = {0, 1, 3, 7, 12, 22, 39, 53, 73, 86, 102, 110, 128}
m[13] = {0, 1, 3, 7, 12, 26, 43, 58, 71, 87, 95, 105, 125}
m[13] = {0, 1, 3, 7, 12, 27, 44, 60, 74, 82, 95, 105, 124}
m[13] = {0, 1, 3, 7, 15, 28, 38, 47, 64, 88, 106, 117, 122}
m[13] = {0, 1, 3, 7, 15, 32, 56, 72, 82, 93, 102, 115, 120}
m[13] = {0, 1, 3, 7, 17, 35, 50, 62, 71, 91, 102, 110, 115}
m[13] = {0, 1, 3, 9, 33, 45, 61, 74, 88, 92, 99, 109, 114}
m[13] = {0, 1, 3, 10, 26, 41, 46, 65, 78, 95, 99, 107, 113}
m[13] = {0, 1, 3, 11, 26, 45, 59, 65, 83, 96, 100, 105, 112}
m[13] = {0, 1, 3, 12, 19, 36, 59, 73, 81, 86, 101, 107, 111}
m[13] = {0, 1, 3, 23, 32, 42, 47, 58, 85, 92, 98, 106, 110}
m[13] = {0, 1, 10, 27, 35, 47, 50, 66, 80, 98, 102, 104, 109}
m[13] = {0, 2, 5, 25, 37, 43, 59, 70, 85, 89, 98, 99, 106}

Initial
propagators: 79
branchings: 1

Summary
runtime: 859110
solutions: 21
propagations: 3939884229
failures: 12382805
clones: 12382846
commits: 38159669
peak memory: 264 KB

real 14m58.649s
user 14m18.526s
sys 0m0.596s

Mikael Zayenz Lagerkvist

2007-11-22, 7:08 pm

On Nov 22, 2:03 pm, "zay...@gmail.com" <zay...@gmail.com> wrote:
> Out of interest, I tested the Golomb ruler example supplied with
> Gecode [1] on my machine (AMD Athlon(tm) 64 Processor 3500+, 2 GB RAM,
> running Linux 2.6.15). The example has two models using lower bounds
> from [2]. The simpler one uses an algebraic lower bound, while the
> more advanced uses bounds from smaller rulers (which are assumed to be
> known).
>
> With the simple model, it took 48 minutes of user-time to find the
> solution for a 13-marker Golomb Ruler. Using the more advanced model,
> it took 14 minutes. Full output of the runs of the program is included
> below.

As an update, I also ran the advanced model to find an optimal golomb
ruler with 14 marks. On the same machine as before it took
approximately 4 1/2 hours. Full output below.

Cheers,
Mikael Lagerkvist

zayenz@emma:~/gecode$ time ./examples/golomb-ruler -model ruler 14
GolombRuler
m[14] = {0, 1, 3, 7, 12, 20, 30, 44, 65, 80, 96, 122, 147,
181}
m[14] = {0, 1, 3, 7, 12, 20, 30, 44, 65, 80, 96, 122, 155,
177}
m[14] = {0, 1, 3, 7, 12, 20, 30, 44, 65, 80, 105, 136, 152,
174}
m[14] = {0, 1, 3, 7, 12, 20, 30, 44, 69, 90, 105, 121, 143,
169}
m[14] = {0, 1, 3, 7, 12, 20, 30, 45, 61, 82, 104, 128, 154,
168}
m[14] = {0, 1, 3, 7, 12, 20, 34, 49, 59, 77, 100, 121, 145,
161}
m[14] = {0, 1, 3, 7, 12, 20, 35, 57, 71, 87, 97, 118, 136,
160}
m[14] = {0, 1, 3, 7, 12, 22, 35, 49, 65, 82, 90, 121, 141,
159}
m[14] = {0, 1, 3, 7, 12, 22, 35, 49, 75, 92, 100, 116, 136,
154}
m[14] = {0, 1, 3, 7, 12, 22, 36, 49, 66, 74, 94, 117, 135,
151}
m[14] = {0, 1, 3, 7, 12, 25, 39, 54, 62, 82, 103, 122, 138,
148}
m[14] = {0, 1, 3, 7, 12, 25, 39, 56, 76, 86, 102, 121, 136,
144}
m[14] = {0, 1, 3, 7, 15, 31, 41, 52, 77, 96, 116, 125, 138,
143}
m[14] = {0, 1, 3, 7, 15, 32, 37, 56, 72, 82, 95, 115, 133,
142}
m[14] = {0, 1, 3, 7, 16, 30, 54, 64, 85, 96, 104, 124, 129,
141}
m[14] = {0, 1, 3, 7, 18, 39, 51, 73, 82, 98, 108, 122, 127,
135}
m[14] = {0, 1, 3, 9, 23, 28, 38, 70, 77, 88, 101, 118, 122,
134}
m[14] = {0, 1, 3, 23, 28, 39, 57, 71, 83, 92, 116, 123, 129,
133}
m[14] = {0, 1, 5, 14, 17, 37, 48, 55, 70, 94, 100, 119, 121,
129}
m[14] = {0, 4, 6, 20, 35, 52, 59, 77, 78, 86, 89, 99, 122,
127}

Initial
propagators: 92
branchings: 1

Summary
runtime: 1.60864e+07
solutions: 20
propagations: 76109842005
failures: 177880102
clones: 177880141
commits: 552440226
peak memory: 329 KB

real 278m56.403s
user 267m55.313s
sys 0m11.065s

Christian Schulte

2007-11-22, 7:08 pm

Hi Neng-Fa,

I have to admit that I have been quite puzzled by your statement "over the
w

end" while not spelling out which level of consistency you have been
using for the alldifferent constraint: naive (or value propagation on the
decomposition to a clique of disequality constraints), bounds, or domain (or
hyper-arc aka GAC). Neither seems likely.

Even if solving with the weakest consistency (known to be inadequate) using
the naive model described by Mikael with Gecode, the optimal solution can be
found and proved optimal within 1h 45 min using a Core 2 Duo (but just using
a single core) at 2.2 GHz running Windows Vista, using around 200K main
memory.

So my questions are:
- What consistency level have you been using (we know that domain
consistency is provably the same as bounds consistency for this problem)?
- Are you really sure that B-Prolog does not have a bug here? Give or take,
my understanding is that ILOG Solver and SICStus
will show very similar performance to Gecode. ILOG CP Optimizer should be
even better (just an educated guess).

I am quite curious, in particular due to the mismatch between the boldly
claimed perfomance of B-Prolog and the actual timing you just reported.

All the best
Christian

PS: We should all agree that CP is not really competetive for this problem:
just Google "Golomb Ruler" ;-)

"Mikael Zayenz Lagerkvist" <zayenz@gmail.com> wrote in message
news:ddd7aeaf-347c-42dc-81e0-3a2c277f2e17@s12g2000prg.googlegroups.com...
> On Nov 22, 2:03 pm, "zay...@gmail.com" <zay...@gmail.com> wrote:
>
> As an update, I also ran the advanced model to find an optimal golomb
> ruler with 14 marks. On the same machine as before it took
> approximately 4 1/2 hours. Full output below.
>
> Cheers,
> Mikael Lagerkvist
>
>
> zayenz@emma:~/gecode$ time ./examples/golomb-ruler -model ruler 14
> GolombRuler
> m[14] = {0, 1, 3, 7, 12, 20, 30, 44, 65, 80, 96, 122, 147,
> 181}
> m[14] = {0, 1, 3, 7, 12, 20, 30, 44, 65, 80, 96, 122, 155,
> 177}
> m[14] = {0, 1, 3, 7, 12, 20, 30, 44, 65, 80, 105, 136, 152,
> 174}
> m[14] = {0, 1, 3, 7, 12, 20, 30, 44, 69, 90, 105, 121, 143,
> 169}
> m[14] = {0, 1, 3, 7, 12, 20, 30, 45, 61, 82, 104, 128, 154,
> 168}
> m[14] = {0, 1, 3, 7, 12, 20, 34, 49, 59, 77, 100, 121, 145,
> 161}
> m[14] = {0, 1, 3, 7, 12, 20, 35, 57, 71, 87, 97, 118, 136,
> 160}
> m[14] = {0, 1, 3, 7, 12, 22, 35, 49, 65, 82, 90, 121, 141,
> 159}
> m[14] = {0, 1, 3, 7, 12, 22, 35, 49, 75, 92, 100, 116, 136,
> 154}
> m[14] = {0, 1, 3, 7, 12, 22, 36, 49, 66, 74, 94, 117, 135,
> 151}
> m[14] = {0, 1, 3, 7, 12, 25, 39, 54, 62, 82, 103, 122, 138,
> 148}
> m[14] = {0, 1, 3, 7, 12, 25, 39, 56, 76, 86, 102, 121, 136,
> 144}
> m[14] = {0, 1, 3, 7, 15, 31, 41, 52, 77, 96, 116, 125, 138,
> 143}
> m[14] = {0, 1, 3, 7, 15, 32, 37, 56, 72, 82, 95, 115, 133,
> 142}
> m[14] = {0, 1, 3, 7, 16, 30, 54, 64, 85, 96, 104, 124, 129,
> 141}
> m[14] = {0, 1, 3, 7, 18, 39, 51, 73, 82, 98, 108, 122, 127,
> 135}
> m[14] = {0, 1, 3, 9, 23, 28, 38, 70, 77, 88, 101, 118, 122,
> 134}
> m[14] = {0, 1, 3, 23, 28, 39, 57, 71, 83, 92, 116, 123, 129,
> 133}
> m[14] = {0, 1, 5, 14, 17, 37, 48, 55, 70, 94, 100, 119, 121,
> 129}
> m[14] = {0, 4, 6, 20, 35, 52, 59, 77, 78, 86, 89, 99, 122,
> 127}
>
> Initial
> propagators: 92
> branchings: 1
>
> Summary
> runtime: 1.60864e+07
> solutions: 20
> propagations: 76109842005
> failures: 177880102
> clones: 177880141
> commits: 552440226
> peak memory: 329 KB
>
> real 278m56.403s
> user 267m55.313s
> sys 0m11.065s

Neng-Fa Zhou

2007-11-23, 7:08 pm

A student in my PL class brought this problem to my attention (see his web
page on Constraint Programming at http://www.geocities.com/georgerabanca/).
I re-ran the program on my slow notebook (1.4GHz, 1GRAM, XP) after changing
"labeling_ff" to "labeling" and "all_distinct" to "all_different" and I got
the following:

| ?- go
[0,2,5,25,37,43,59,70,85,89,98,99,106]
time(20057797)

The time is 5.57 in hours, which is not as good as Gecode's even if the
difference in the running platforms is taken into account, but I don't know
if Roman's model is the same as one of Gecode's two models.

In B-Prolog, "all_distinct" enforces weak arc consistency using channeling
constraints if the numbers of variables and values are the same and
"all_different" uses a naive propagator. Apparently, naive propagation is
better than the weak arc consistency one for this problem. I found later in
the appendix of Roman Bartak's tutorial that a solution to size 13 had been
found in "a couple of days" using SICStus. I guess it wouldn't have taken
that long had all_different/labeling been used instead of
all_distinct/labeling_ff.

Cheers,
Neng-Fa

Sponsored Links