Accelerating backtrack search with a best-first-search strategy

Mann, Z. Á. ; Szép, T.

International Journal of Applied Mathematics and Computer Science, Tome 24 (2014) no. 4, pp. 901-916.

Résumé

Backtrack-style exhaustive search algorithms for NP-hard problems tend to have large variance in their runtime. This is because “fortunate” branching decisions can lead to finding a solution quickly, whereas “unfortunate” decisions in another run can lead the algorithm to a region of the search space with no solutions. In the literature, frequent restarting has been suggested as a means to overcome this problem. In this paper, we propose a more sophisticated approach: a best-first-search heuristic to quickly move between parts of the search space, always concentrating on the most promising region. We describe how this idea can be efficiently incorporated into a backtrack search algorithm, without sacrificing optimality. Moreover, we demonstrate empirically that, for hard solvable problem instances, the new approach provides significantly higher speed-up than frequent restarting.

Détail

Keywords: best first search, backtrack, branch and bound, constraint satisfaction problem (CSP), frequent restarting
Mots-clés : algorytm wyszukiwania, system backtrack, metoda podziału i ograniczeń, programowanie z ograniczeniami

Bibliographie

[1] Appel, A.W. and George, L. (1996). Register interference graphs, http://www.cs.princeton.edu/~appel/graphdata/.

[2] Bender, E.A. and Wilf, H.S. (1985). A theoretical analysis of backtracking in the graph coloring problem, Journal of Algorithms 6(2): 275–282.

[3] Biere, A. (2008). Adaptive restart strategies for conflict driven SAT solvers, in H. Kleine Büning and X. Zhao (Eds.), Theory and Applications of Satisfiability Testing—SAT 2008, Springer, Berlin, pp. 28–33.

[4] Brélaz, D. (1979). New methods to color the vertices of a graph, Communications of the ACM 22(4): 251–256.

[5] Brown, C.A., Finkelstein, L. and Purdom, P.W.J. (1996). Backtrack searching in the presence of symmetry, Nordic Journal of Computing 3(3): 203–219.

[6] Brown, J.R. (1972). Chromatic scheduling and the chromatic number problem, Management Science 19(4): 456–463.

[7] Cheeseman, P., Kanefsky, B. and Taylor, W.M. (1991). Where the really hard problems are, 12th International Joint Conference on Artificial Intelligence (IJCAI ’91), Sydney, Australia, pp. 331–337.

[8] Davis, M., Logemann, G. and Loveland, D. (1962). A machine program for theorem proving, Communications of the ACM 5(7): 394–397.

[9] Davis, M. and Putnam, H. (1960). A computing procedure for quantification theory, Journal of the ACM 7(3): 201–215.

[10] Dechter, R. (1990). Enhancement schemes for constraint processing: Backjumping, learning and cutset decomposition, Artificial Intelligence 41(3): 273–312.

[11] Dechter, R. (2003). Constraint Processing, Morgan Kaufmann, San Francisco, CA.

[12] Dechter, R. and Frost, D. (2002). Backjump-based backtracking for constraint satisfaction problems, Artificial Intelligence 136(2): 147–188.

[13] Eén, N. and Sörensson, N. (2004). An extensible SAT-solver, in E. Giunchiglia and A. Tacchella (Eds.), Theory and Applications of Satisfiability Testing, Lecture Notes in Computer Science, Vol. 2919, Springer, Berlin/Heidelberg, pp. 502–518.

[14] Geelen, P.A. (1992). Dual viewpoint heuristics for binary constraint satisfaction problems, Proceedings of the 10th European Conference on Artificial Intelligence, Vienna, Austria, pp. 31–35.

[15] Gomes, C.P., Selman, B., Crato, N. and Kautz, H. (2000). Heavy-tailed phenomena in satisfiability and constraint satisfaction problems, Journal of Automated Reasoning 24(1–2): 67–100.

[16] Gomes, C., Selman, B. and Kautz, H. (1998). Boosting combinatorial search through randomization, Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI-98), Madison, WI, USA, pp. 431–437.

[17] Haim, S. and Heule, M. (2010). Towards ultra rapid restarts, Technical report, UNSW/TU Delft, Sydney/Delft.

[18] Hogg, T. and Williams, C.P. (1994). The hardest constraint problems: A double phase transition, Artificial Intelligence 69(1–2): 359–377.

[19] Hutter, F., Hamadi, Y., Hoos, H. and Leyton-Brown, K. (2006). Performance prediction and automated tuning of randomized and parametric algorithms, in F. Benhamou (Ed.), Principles and Practice of Constraint Programming—CP 2006, Springer, Berlin/Heidelberg, pp. 213–228.

[20] Jia, H. and Moore, C. (2004). How much backtracking does it take to color random graphs? Rigorous results on heavy tails, Principles and Practice of Constraint Programming (CP 2004), Toronto, Canada, pp. 742–746.

[21] Kautz, H., Horvitz, E., Ruan, Y., Gomes, C. and Selman, B. (2002). Dynamic restart policies, 18th National Conference on Artificial Intelligence, Edmonton, Canada, pp. 674–681.

[22] Knuth, D.E. (1975). Estimating the efficiency of backtrack programs, Mathematics of Computation 29(129): 121–139.

[23] Luby, M., Sinclair, A. and Zuckerman, D. (1993). Optimal speedup of Las Vegas algorithms, Information Processing Letters 47(4): 173–180.

[24] Mann, Z. (2011). Optimization in Computer Engineering—Theory and Applications, Scientific Research Publishing, Irvine, CA.

[25] Mann, Z. and Szajkó, A. (2012). Complexity of different ILP models of the frequency assignment problem, in Z. Mann (Ed.), Linear Programming—New Frontiers in Theory and Applications, Nova Science Publishers, New York, NY, pp. 305–326.

[26] Mann, Z. and Szajkó, A. (2010a). Determining the expected runtime of exact graph coloring, Proceedings of the 13th International Multiconference on Information Society—IS 2010, Ljubljana, Slovenia, Vol. A, pp. 389–393.

[27] Mann, Z. and Szajkó, A. (2010b). Improved bounds on the complexity of graph coloring, Proceedings of the 12th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Timisoara, Romania, pp. 347–354.

[28] Mann, Z. and Szép, T. (2010). BCAT: A framework for analyzing the complexity of algorithms, 8th IEEE International Symposium on Intelligent Systems and Informatics, Subotica, Serbia, pp. 297–302.

[29] Moskewicz, M.W., Madigan, C.F., Zhao, Y., Zhang, L. and Malik, S. (2001). Chaff: Engineering an efficient SAT solver, Proceedings of the 38th Annual Design Automation Conference, Las Vegas, NV, USA, pp. 530–535.

[30] Russell, S.J. and Norvig, P. (2010). Artificial Intelligence: A Modern Approach, 3rd Edn., Prentice Hall, Upper Saddle River, NJ.

[31] Schaefer, R., Byrski, A., Kołodziej, J. and Smołka, M. (2012). An agent-based model of hierarchic genetic search, Computers and Mathematics with Applications 64(12): 3763–3776.

[32] Trick, M. (2003). COLOR03 graph coloring benchmarks, http://mat.gsia.cmu.edu/COLOR03/.

[33] Walsh, T. (1999). Search in a small world, Proceedings of the 16th International Joint Conference on Artificial Intelligence, Stockholm, Sweden, pp. 1172–1177.

[34] Wilf, H.S. (1984). Backtrack: An O(1) expected time algorithm for the graph coloring problem, Information Processing Letters 18(3): 119–121.

[35] Wu, H. and van Beek, P. (2003). Restart strategies: Analysis and simulation, Principles and Practice of Constraint Programming—CP 2003, Kinsale, Ireland, p. 1001.