next up previous
Next: Schur numbers Up: A comparison of Constraint Previous: K-Coloring

Hamiltonian circuit

CLP(FD) code:
hamiltonian.pl (SICStus)

ASP code:
hamiltonian.lp

Results:
Hamiltonian circuit (`-' denotes no answer within 3 hours of CPU-time):
    Hamiltonian?
Instance nodes$ \times$edges   SModels CModels SICStus
        mChaff Simo zChaff  
hc1 .pl.lp 200$ \times$1250 Y 3.01 37.60 14.30 5.53 0.33
hc2 .pl.lp 200$ \times$1250 Y 3.03 1390.15 3.48 3.25 0.35
hc3 .pl.lp 200$ \times$1250 Y 3.06 20.08 6.52 10.71 0.31
hc4 .pl.lp 200$ \times$1250 Y 3.02 92.99 6.54 4.11 0.33
hc5 .pl.lp 200$ \times$1250 N 1.45 0.22 0.21 0.21 0.24
hc6 .pl.lp 200$ \times$1250 N 1.46 0.21 0.21 0.21 0.10
hc7 .pl.lp 200$ \times$1250 N 1.46 0.21 0.21 0.21 0.24
hc8 .pl.lp 200$ \times$1250 N 1.46 0.21 0.21 0.21 0.23
np10c .pl.lp 10$ \times$90 Y 0.01 0.04 0.01 0.01 $ <$0.01
np20c .pl.lp 20$ \times$380 Y 0.07 0.81 0.05 0.07 0.01
np30c .pl.lp 30$ \times$870 Y 0.26 0.26 0.20 0.27 0.01
np40c .pl.lp 40$ \times$1560 Y 0.84 4.35 0.68 0.76 0.02
np50c .pl.lp 50$ \times$2450 Y 2.69 117.77 1.55 1.72 0.03
np60c .pl.lp 60$ \times$3540 Y 7.34 24.72 5.54 3.77 0.04
np70c .pl.lp 70$ \times$4830 Y 15.58 9.46 7.46 5.91 0.07
np80c .pl.lp 80$ \times$6320 Y 27.88 12.53 12.60 9.20 0.10
np90c .pl.lp 90$ \times$8010 Y 46.07 127.31 42.32 14.24 0.14
2xp30 .pl.lp 60$ \times$316 N 0.14 0.02 0.02 0.02 0.01
2xp30.1 .pl.lp 60$ \times$318 Y 0.19 4.59 377.09 371.81 0.03
2xp30.2 .pl.lp 60$ \times$318 Y 7931.75 2.68 3.90 21.47 5.42
2xp30.3 .pl.lp 60$ \times$318 Y 7910.75 2.69 3.87 21.49 5.39
2xp30.4 .pl.lp 60$ \times$318 N - 5692.11 - 553.54 -
4xp20 .pl.lp 80$ \times$392 N 0.24 0.04 0.04 0.04 0.04
4xp20.1 .pl.lp 80$ \times$395 N - 1.48 36.36 3.56 0.03
4xp20.2 .pl.lp 80$ \times$396 Y 0.37 3.32 3.42 7.43 0.05
4xp20.3 .pl.lp 80$ \times$396 N 0.24 2.62 51.45 1.46  
nv50a240 .pl.lp 50$ \times$233 Y 0.12 0.52 0.18 0.12 0.01
nv50a260 .pl.lp 50$ \times$239 Y 0.12 0.96 0.09 0.12 0.02
nv50a280 .pl.lp 50$ \times$263 Y 0.13 0.51 0.16 0.13 0.02
nv50a300 .pl.lp 50$ \times$280 Y 0.14 0.15 0.15 0.15 0.03
nv50a340 .pl.lp 50$ \times$303 Y 0.14 1.24 0.23 0.14 0.03
nv50a360 .pl.lp 50$ \times$329 Y 0.15 1.16 0.09 0.14 0.03
nv50a380 .pl.lp 50$ \times$354 Y 0.16 0.63 0.09 0.12 0.02
nv50a400 .pl.lp 50$ \times$365 Y 0.16 0.18 0.10 0.12 0.03
nv50a420 .pl.lp 50$ \times$375 Y 0.15 0.18 0.15 0.12 0.01
nv50a440 .pl.lp 50$ \times$401 Y 0.16 3.08 0.09 0.07 0.02
nv50a460 .pl.lp 50$ \times$416 Y 0.17 0.22 0.06 0.08 0.03
nv50a480 .pl.lp 50$ \times$422 Y 0.17 2.99 0.12 0.16 0.02
nv50a500 .pl.lp 50$ \times$438 Y 0.17 0.71 0.09 0.11 0.02
nv50a520 .pl.lp 50$ \times$459 Y 0.18 0.70 0.26 0.11 0.03
nv50a540 .pl.lp 50$ \times$480 Y 0.17 1.20 0.12 0.10 0.02
nv50a560 .pl.lp 50$ \times$500 Y 0.19 0.27 0.13 0.14 0.02
nv50a580 .pl.lp 50$ \times$509 Y 0.18 0.43 0.11 0.13 0.02
nv60a320 .pl.lp 60$ \times$304 Y 0.19 0.80 0.19 0.32 0.03
nv60a360 .pl.lp 60$ \times$343 Y 0.19 8.18 0.43 0.44 0.03
nv60a420 .pl.lp 60$ \times$389 Y 0.22 0.96 0.28 0.29 0.03
nv60a440 .pl.lp 60$ \times$412 Y 0.23 8.91 0.41 0.11 0.02
nv60a460 .pl.lp 60$ \times$423 Y 0.22 0.83 0.36 0.17 0.03
nv60a480 .pl.lp 60$ \times$425 Y 0.22 1.62 0.17 0.17 0.04
nv60a500 .pl.lp 60$ \times$455 Y 0.23 2.20 0.29 0.16 0.02
nv60a520 .pl.lp 60$ \times$582 Y 0.23 0.36 0.28 0.13 0.04
nv60a540 .pl.lp 60$ \times$587 Y 0.25 0.56 0.19 0.26 0.04
nv60a560 .pl.lp 60$ \times$513 Y 0.25 0.20 0.13 0.11 0.05
nv60a580 .pl.lp 60$ \times$532 Y 0.25 0.97 0.16 0.22 0.04
nv70a300 .pl.lp 70$ \times$287 Y 0.21 0.81 0.34 0.24 0.04
nv70a320 .pl.lp 70$ \times$306 Y 0.23 4.25 1.01 0.19 0.04
nv70a340 .pl.lp 70$ \times$328 Y 0.24 1.88 0.28 0.35 0.04
nv70a360 .pl.lp 70$ \times$346 Y 0.24 1.44 0.48 0.16 0.04
nv70a380 .pl.lp 70$ \times$359 Y 0.25 0.44 0.13 0.17 0.04
nv70a400 .pl.lp 70$ \times$386 Y 0.26 4.21 0.39 0.34 0.04
nv70a420 .pl.lp 70$ \times$404 Y 0.27 4.60 0.56 0.48 0.05
nv70a440 .pl.lp 70$ \times$423 Y 0.28 1.31 0.86 0.27 0.04
nv70a460 .pl.lp 70$ \times$429 Y 0.28 3.00 0.36 0.30 0.04
nv70a480 .pl.lp 70$ \times$460 Y 0.29 1.65 0.22 0.11 0.05
nv70a500 .pl.lp 70$ \times$473 Y 0.29 1.72 0.41 0.45 0.03
nv70a520 .pl.lp 70$ \times$478 Y 0.29 0.35 0.39 0.26 0.05
nv70a540 .pl.lp 70$ \times$507 Y 0.31 4.16 0.21 0.63 0.04
nv70a560 .pl.lp 70$ \times$516 Y 0.32 0.62 0.26 0.22 0.04
nv70a580 .pl.lp 70$ \times$540 Y 0.32 1.01 0.97 0.18 0.05
Sources of instances:http://www.cs.uky.edu/ai/benchmark-suite/hamiltonian-cycle.html and http://assat.cs.ust.hk/Assat-2.0/hc-2.0.html.


next up previous
Next: Schur numbers Up: A comparison of Constraint Previous: K-Coloring
Last update: 21-12-2005 by andy