Constraint-directed search for all-interval series. (English) Zbl 1387.90225

Polash, Md Masbaul Alam; Newton, M. A. Hakim; Sattar, Abdul

Constraints 22, No. 3, 403-431 (2017).

Summary: All-interval series is a standard benchmark problem for constraint satisfaction search. An all-interval series of size \(n\) is a permutation of integers \([0,n)\) such that the differences between adjacent integers are a permutation of \([1, n)\). Generating each such all-interval series of size \(n\) is an interesting challenge for constraint community. The problem is very difficult in terms of the size of the search space. Different approaches have been used to date to generate all the solutions of AIS but the search space that must be explored still remains huge. In this paper, we present a constraint-directed backtracking-based tree search algorithm that performs efficient lazy checking rather than immediate constraint propagation. Moreover, we prove several key properties of all-interval series that help prune the search space significantly. The reduced search space essentially results into fewer backtracking. We also present scalable parallel versions of our algorithm that can exploit the advantage of having multi-core processors and even multiple computer systems. Our new algorithm generates all the solutions of size up to 27 while a satisfiability-based state-of-the-art approach generates all solutions up to size 24.

MSC:

90C27

Combinatorial optimization

Keywords:

all-interval series; backtracking search; constraint programming; lazy constraint propagation

Software:

clasp; Kangaroo; Gelisp

References:

[1]	Ilog solver. http://www.cs.cornell.edu/w8/iisi/ilog/cp11/usrsolver/usrsolverpreface.html.
[2]	Minizinc challenge 2013 results. https://www.minizinc.org/challenge2013/results2013.html.
[3]	Adamaszek, M. (2006). Efficient enumeration of graceful permutations. arXiv:math/0608513. · Zbl 1297.05007
[4]	Alsinet, T., Bejar, R., Cabiscol, A., Fernandez, C., & Manya, F. (2002). Minimal and redundant SAT encodings for the all-interval series problem. In Topics in artificial intelligence, 5th catalonian conference on AI (CCIA), LNCS, (Vol. 2504 pp. 139-144). · Zbl 1028.68627
[5]	Beldiceanu, N; Contejean, E, Introducing global constraints in CHIP, Journal of Mathematical and Computer Modelling, 20, 97-123, (1994) · Zbl 0816.68048
[6]	Béjar, R; Manyà, F; Cabiscol, A; Fernàndez, C; Gomes, C, Regular-sat: a many-valued approach to solving combinatorial problems, Discrete Applied Mathematics, 155, 1613-1626, (2007) · Zbl 1121.68104
[7]	Choi, C., & Lee, J. (2002). On the pruning behaviour of minimal combined models for permutation csps. In International workshop on reformulating constraint satisfaction problems.
[8]	Codognet, P., & Diaz, D. (2001). Yet another local search method for constraint solving. In Proceedings of the international symposium on stochastic algorithms: foundations and applications, SAGA ’01 (pp. 73-90): Springer. · Zbl 1054.68646
[9]	Colles, H. (1940). Grove’s dictionary of music and musicians. New York: The MacMillan Company.
[10]	Dent, M.J., & Mercer, R.E. (1994). Minimal forward checking. In Proceedings of the 6th international conference on tools with artificial intelligence. (pp. 432-438): IEEE.doi:10.1109/TAI.1994.346460
[11]	Gebser, M; Kaufmann, B; Schaub, T, The conflict-driven answer set solver clasp, Lecture Notes in Computer Science, Springer, 5753, 509-514, (2009)
[12]	Gent, I. P., McDonald, I., & Smith, B. M. (2003). Conditional symmetry in the all-interval series problem. In Proceedings of the 3rd international workshop on symmetry in constraint satisfaction problems, (Vol. 3 pp. 55-65).
[13]	Hoos, H. H. (1998). Stochastic local search - methods, models, applications. Ph.D. thesis, Department of Computer Science, Technical University of Darmstadt, Germany.
[14]	Hudson, S, Incremental attribute evaluation: a flexible algorithm for lazy update, ACM Transactions on Programming Language and Systems, 13, 315-341, (1991)
[15]	Krenek, E. (1974). Horizons circled-reflections on my music. Berkeley: University of California Press.
[16]	Moisan, T., Gaudreault, J., & Quimper, C. G. (2013). Parallel discrepancy-based search. In International conference on principles and practice of constraint programming (pp. 30-46): Springer. · Zbl 1407.68459
[17]	Newton, M; Pham, D; Sattar, A; Maher, M, Kangaroo: an efficient constraint-based local search system using lazy propagation, CP. LNCS, Springer, Heidelberg, 6876, 645-659, (2011)
[18]	Nguyen, V., & Son, M. (2014). Solving the all-interval series problem: SAT vs CP. In Proceedings of the 5th symposium on information and communication technology (pp. 65-74). · Zbl 0816.68048
[19]	Petrie, K. E., & Smith, B. M. (2003). Symmetry breaking in graceful graphs. In Rossi, F. (Ed.) Proceedings of principles and practice of constraint programming: Springer.
[20]	Puget, J., & Regin, J. Solving the all-interval problem. http://www.cs.st-andrews.ac.uk/ianm/CSPLib/prob/prob007/puget.pdf.
[21]	Remzi, H.A.D., & Andrea, C.A.D. (2014). Operating systems: three easy steps Arpaci-Dusseau books. · Zbl 0816.68048
[22]	Schuurmans, D; Southey, F, Local search characteristics of incomplete SAT procedures, 297-302, (2000), Austin/TX, USA · Zbl 0983.68180
[23]	Simonis, H., Beldiceanu, N., & Sa, C. (1998). A note on CSPLIB prob007. Tech. rep., Normale.
[24]	Solnon, C. (2000). Solving permutation constraint satisfaction problems with artificial ants. In Proceedings of ECAI’2000 (pp. 118-122): IOS Press. · Zbl 0983.68180
[25]	Toro, M., Rueda, C., Agon, C., & Assayag, G. (2015). Gelisp: a library to represent musical csps and search strategies. Computing Research Repository. arXiv:1510.02828.
[26]	Truchet, C., Richoux, F., & Codognet, P. (2012). Prediction of parallel speed-ups for las vegas algorithms. arXiv:1212.4287.
[27]	Walsh, T. (2010). Parameterized complexity results in symmetry breaking. In Proceedings of 5th international symposium, IPEC, Chennai, India, LNCS, (Vol. 6478 pp. 4-13): Springer. · Zbl 1309.68104
[28]	Worister, M., Steinlechner, H., Maierhofer, S., & Tobler, R. (2013). Lazy incremental computation for efficient scene graph rendering. In Proceedings of the 5th high-performance graphics conference. doi:10.1145/2492045.2492051 (pp. 53-62). New York, NY, USA: ACM.
[29]	Yadav, S.C., & Singh, S.K. (2009). An introduction to Client/Server Computing, New Age International Publishers Limited.