×

A unified framework for partial and hybrid search methods in constraint programming. (English) Zbl 1086.90051

We present a library called ToOLS for the design of complex tree search algorithms in constraint programming (CP). We separate the description of a search algorithm into three parts: a refinement-based search scheme that defines a complete search tree, a set of conditions for visiting nodes that specifies a parameterized partial exploration, and a strategy for combining several partial explorations. This library allows the expression of most of the partial, i.e. nonsystematic backtracking, search methods, and also a specific class of hybrid local/global search methods called large neighborhood search, which are very naturally suited to CP. Variants of these methods are easy to implement with the ToOLS primitives. We demonstrate the expressiveness and efficiency of the library by solving a satellite mission management benchmark that is a mix between a traveling salesman problem with time windows and a Knapsack problem. Several partial and hybrid search methods are compared. Our results dramatically outperform CP approaches based on classical depth-first search methods.

MSC:

90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] ILOG SA. ILOG: ILOG Solver 6.0 user’s manual, 2003.; ILOG SA. ILOG: ILOG Solver 6.0 user’s manual, 2003.
[2] Cosytec SA. CHIP V5, 1997.; Cosytec SA. CHIP V5, 1997.
[3] Beldiceanu N, Bourreau E, Chan P, Rivreau D. Partial search strategy in CHIP. In: Proceedings of the second international conference on meta-heuristics, Sophia-Antipolis, France, 1997.; Beldiceanu N, Bourreau E, Chan P, Rivreau D. Partial search strategy in CHIP. In: Proceedings of the second international conference on meta-heuristics, Sophia-Antipolis, France, 1997.
[4] Shaw P. Using constraint programming and local search methods to solve vehicle routing problems. In: Proceedings of CP-98, Pisa, Italy, 1998. p. 417-31.; Shaw P. Using constraint programming and local search methods to solve vehicle routing problems. In: Proceedings of CP-98, Pisa, Italy, 1998. p. 417-31.
[5] Michel, L.; Van Hentenryck, P., Localizer. Constraints, 5, 1,2, 43-84 (2000) · Zbl 0988.90015
[6] Van Hentenryck, P., OPLThe optimization programming language (1999), The MIT Press: The MIT Press Cambridge, MA
[7] Laburthe, F.; Caseau, Y., \(SALSA\) a language for search algorithms, Constraints, 7, 3, 255-288 (2002) · Zbl 1020.68028
[8] de Givry S, Jeannin L, Josset F, Mattioli J, Museux N, Savéant P. The THALES constraint programming framework for hard and soft real-time applications. The PLANET Newsletter, Issue 5 ISSN 1610-0212, December 2002. p. 5-7. http://planet.dfki.de/service/Resources/Rome/degivry.pdf; de Givry S, Jeannin L, Josset F, Mattioli J, Museux N, Savéant P. The THALES constraint programming framework for hard and soft real-time applications. The PLANET Newsletter, Issue 5 ISSN 1610-0212, December 2002. p. 5-7. http://planet.dfki.de/service/Resources/Rome/degivry.pdf
[9] PLATON Team. Eclair reference manual. PLATON, THALES Research & Technology, Orsay, France, version 6.0 edition, 2001.; PLATON Team. Eclair reference manual. PLATON, THALES Research & Technology, Orsay, France, version 6.0 edition, 2001.
[10] Caseau Y, Josset FX, Laburthe F. Claire: combining sets, search and rules to better express algorithms. In: Proceedings of ICLP’99, Las Cruces, New Mexico, 1999. p. 245-59.; Caseau Y, Josset FX, Laburthe F. Claire: combining sets, search and rules to better express algorithms. In: Proceedings of ICLP’99, Las Cruces, New Mexico, 1999. p. 245-59. · Zbl 1105.68339
[11] de Givry S, Savéant P, Jourdan J. Optimisation combinatoire en temps limité: Depth first branch and bound adaptatif. In: Proceedings of JFPLC-99, Lyon, France, 1999. p. 161-78.; de Givry S, Savéant P, Jourdan J. Optimisation combinatoire en temps limité: Depth first branch and bound adaptatif. In: Proceedings of JFPLC-99, Lyon, France, 1999. p. 161-78. · Zbl 0944.90072
[12] Jourdan J, de Givry S, Savéant P. Designing limited search algorithms for time constrained combinatorial optimization problems. Technical report, Thales Research & Development, 1999. http://www.inra.fr/bia/T/degivry/Givry99c.ps.gz; Jourdan J, de Givry S, Savéant P. Designing limited search algorithms for time constrained combinatorial optimization problems. Technical report, Thales Research & Development, 1999. http://www.inra.fr/bia/T/degivry/Givry99c.ps.gz
[13] de Givry S, Hamadi Y, Mattioli J, Gérard P, Lemaître M, Verfaillie G, Aggoun A, Gouachi I, Benoist T, Bourreau E, Laburthe F, David P, Loudni S, Bourgault S. Towards an on-line optimisation framework. In: CP-2001 workshop on on-line combinatorial problem solving and constraint programming (OLCP’01), Paphos, Cyprus, December 1, 2001. p. 45-61. http://www.inra.fr/bia/T/degivry/Givry01d.ps.gz; de Givry S, Hamadi Y, Mattioli J, Gérard P, Lemaître M, Verfaillie G, Aggoun A, Gouachi I, Benoist T, Bourreau E, Laburthe F, David P, Loudni S, Bourgault S. Towards an on-line optimisation framework. In: CP-2001 workshop on on-line combinatorial problem solving and constraint programming (OLCP’01), Paphos, Cyprus, December 1, 2001. p. 45-61. http://www.inra.fr/bia/T/degivry/Givry01d.ps.gz
[14] Hogg, T.; Huberman, B. A.; Williams, C. P., Phase transitions and the search problem. Artificial Intelligence, 81, 1-2, 1-15 (1996) · Zbl 1508.68334
[15] Gomes C, Selman B, Kautz H. Boosting combinatorial search through randomization. In: Proceedings of AAAI-98, Madison, WI, 1998.; Gomes C, Selman B, Kautz H. Boosting combinatorial search through randomization. In: Proceedings of AAAI-98, Madison, WI, 1998.
[16] Ginsberg, M. L.; Harvey, W. D., Iterative broadening, Artificial Intelligence, 55, 367-383 (1992)
[17] Harvey WD, Ginsberg ML. Limited discrepancy search. In: Proceedings of IJCAI-95, Montréal, Canada, 1995. p. 607-13.; Harvey WD, Ginsberg ML. Limited discrepancy search. In: Proceedings of IJCAI-95, Montréal, Canada, 1995. p. 607-13.
[18] Walsh T. Depth-bounded discrepancy search. In: Proceedings of IJCAI-97, Nagoya, Japan, 1997.; Walsh T. Depth-bounded discrepancy search. In: Proceedings of IJCAI-97, Nagoya, Japan, 1997.
[19] Beck JC, Perron L. Discrepancy-bounded depth first search. In: Proceedings of CP-AI-OR’2000, Paderborn, Germany, March 8-10, 2000.; Beck JC, Perron L. Discrepancy-bounded depth first search. In: Proceedings of CP-AI-OR’2000, Paderborn, Germany, March 8-10, 2000.
[20] Michel, L.; Van Hentenryck, P., A decomposition-based implementation of search strategies, ACM Transactions on Computational Logic, 5, 2 (2004) · Zbl 1367.68267
[21] Chu L-C, Wah BW. Optimization in real time. In: Proceedings of the twelfth real time systems symposium, Washington, DC, 1991. p. 150-9.; Chu L-C, Wah BW. Optimization in real time. In: Proceedings of the twelfth real time systems symposium, Washington, DC, 1991. p. 150-9.
[22] Korf, R. E., Real-time heuristic search, Artificial Intelligence, 42, 189-211 (1990) · Zbl 0718.68082
[23] Bresina JL. Heuristic-biased stochastic sampling. In: Proceedings of AAAI-96, Portland, OR, 1996. p. 271-8.; Bresina JL. Heuristic-biased stochastic sampling. In: Proceedings of AAAI-96, Portland, OR, 1996. p. 271-8.
[24] Meseguer P. Interleaved depth-first search. In: Proceedings of IJCAI-97, Nagoya, Japan, 1997. p. 1382-7.; Meseguer P. Interleaved depth-first search. In: Proceedings of IJCAI-97, Nagoya, Japan, 1997. p. 1382-7.
[25] Gomes, C.; Selman, B., Algorithm portfolios, Artificial Intelligence, 126, 1,2, 43-62 (2001) · Zbl 0969.68047
[26] Prcovic N, Neveu B. Progressive focusing search. In: Proceedings of ECAI-02, Lyon, France, 2002. p. 126-30.; Prcovic N, Neveu B. Progressive focusing search. In: Proceedings of ECAI-02, Lyon, France, 2002. p. 126-30.
[27] Perron L. Fast restart policies and large neighborhood search. In: Proceedings of CP-AI-OR’2003, Montréal, Canada, 2003. p. 246-60.; Perron L. Fast restart policies and large neighborhood search. In: Proceedings of CP-AI-OR’2003, Montréal, Canada, 2003. p. 246-60.
[28] Pesant, G.; Gendreau, M., A constraint programming framework for local search methods, Journal of Heuristics, 5, 255-279 (1999) · Zbl 1064.90577
[29] Applegate, D.; Cook, B., A computational study of the job shop scheduling problem, Operations Research Society of America, 3, 2 (1991) · Zbl 0755.90039
[30] Caseau Y, Laburthe F. Disjunctive scheduling with task intervals. Technical report, LIENS Technical report 95-25, Paris, 1995.; Caseau Y, Laburthe F. Disjunctive scheduling with task intervals. Technical report, LIENS Technical report 95-25, Paris, 1995. · Zbl 0949.90058
[31] Caseau Y, Laburthe F. Effective forget-and-extend heuristics for scheduling problems. In: Proceedings of CP-AI-OR’1999, Ferrara, Italy, February 1999.; Caseau Y, Laburthe F. Effective forget-and-extend heuristics for scheduling problems. In: Proceedings of CP-AI-OR’1999, Ferrara, Italy, February 1999. · Zbl 1064.90508
[32] Loudni S, Boizumault P. Solving constraint optimization problems in anytime contexts. In: Proceedings of IJCAI-03, Acapulco, Mexico, 2003. p. 251-6.; Loudni S, Boizumault P. Solving constraint optimization problems in anytime contexts. In: Proceedings of IJCAI-03, Acapulco, Mexico, 2003. p. 251-6. · Zbl 1160.90661
[33] de Givry S, Jeannin L. ToOLS: a library for partial and hybrid search methods. In: Proceedings of CP-AI-OR’2003, Montréal, Canada, 2003. p. 124-38.; de Givry S, Jeannin L. ToOLS: a library for partial and hybrid search methods. In: Proceedings of CP-AI-OR’2003, Montréal, Canada, 2003. p. 124-38.
[34] Mladenovic, N.; Hansen, P., Variable neighbourhood search, Computer and Operations Research, 24, 1097-1100 (1997) · Zbl 0889.90119
[35] Gendreau, M.; Rousseau, L.-M.; Pesant, G., Using constraint-based operators to solve the vehicle routing problem with time windows, Journal of Heuristics, 8, 43-58 (2002) · Zbl 1073.90056
[36] Hansen, P.; Mladenovic, N.; Perez-Brito, D., Variable neighborhood decomposition search, Journal of Heuristics, 7, 335-350 (2001) · Zbl 1041.68623
[37] Lin, S.; Kernighan, B. W., An effective heuristic algorithm for the traveling salesman problem, Operations Research, 21, 498-516 (1973) · Zbl 0256.90038
[38] Bockmayr, A.; Kasper, T., Branch-and-infera unifying framework for integer and finite domain constraint programming, INFORMS Journal of Computing, 10, 3, 287-300 (1998) · Zbl 1034.90517
[39] Van Hentenryck, P., Constraint satisfaction in logic programming. Logic programming series (1989), The MIT Press: The MIT Press Cambridge, MA
[40] Van Hentenryck, P., Intelligent scheduling. Chapterscheduling and packing in the constraint language cc(FD) (1994), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA
[41] Beldiceanu N, Bourreau E, Simonis H. A note on perfect square placement. CSPLib, 1999.; Beldiceanu N, Bourreau E, Simonis H. A note on perfect square placement. CSPLib, 1999.
[42] Harvey WD. Nonsystematic backtracking search. Ph.D. thesis, Stanford University, March 1995.; Harvey WD. Nonsystematic backtracking search. Ph.D. thesis, Stanford University, March 1995.
[43] Bedrax-Weiss T. Optimal search protocols. Ph.D. thesis, University of Oregon, 1999.; Bedrax-Weiss T. Optimal search protocols. Ph.D. thesis, University of Oregon, 1999.
[44] Verfaillie G, Lemaître M. Selecting and scheduling observations for agile satellites: some lessons from the constraint reasoning community point of view. In: Proceedings of CP-01, Paphos, Cyprus, 2001.; Verfaillie G, Lemaître M. Selecting and scheduling observations for agile satellites: some lessons from the constraint reasoning community point of view. In: Proceedings of CP-01, Paphos, Cyprus, 2001. · Zbl 1067.68680
[45] Lemaître, M.; Verfaillie, G.; Jouhaud, F.; Lachiver, J.-M.; Bataille, N., Selecting and scheduling observations of agile satellites, Aerospace Sciences and Technology, 6, 367-381 (2002)
[46] Laburthe F and the OCRE project team. CHOCO: implementing a CP kernel. In: CP-2000 workshop on techniques for implementing constraint programming systems (TRICS), Singapore, 2000. http://www.choco-constraints.net/; Laburthe F and the OCRE project team. CHOCO: implementing a CP kernel. In: CP-2000 workshop on techniques for implementing constraint programming systems (TRICS), Singapore, 2000. http://www.choco-constraints.net/
[47] Baptiste, P.; Le Pape, C., Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems, Constraints, 5, 1,2, 119-139 (2000) · Zbl 0941.90030
[48] Penron L. Search procedures and parallelism in constraint programming. In: Proceedings of CP-99, Alexandria, Virginia, October 11-14, 1999. p. 346-60.; Penron L. Search procedures and parallelism in constraint programming. In: Proceedings of CP-99, Alexandria, Virginia, October 11-14, 1999. p. 346-60.
[49] Van Hentenryck, P.; Perron, L.; Puget, J.-F., Search and strategies in OPL, ACM Transactions on Computational Logic (TOCL), 1, 2, 285-320 (2000) · Zbl 1365.90281
[50] Van Hentenryck, P.; Michel, L., New trends in constraints, chapter OPL scriptcomposing and controlling models (2000), Springer: Springer Berlin
[51] Schulte C. Programming constraint services. Doctoral dissertation, Universitat des Saarlandes, Saarbrucken, Germany, 2000.; Schulte C. Programming constraint services. Doctoral dissertation, Universitat des Saarlandes, Saarbrucken, Germany, 2000.
[52] IC-Parc. Eclipse 5.7, 2004. http://www-icparc.doc.ic.ac.uk/eclipse/; IC-Parc. Eclipse 5.7, 2004. http://www-icparc.doc.ic.ac.uk/eclipse/
[53] Banzhaf, W.; Nordin, P.; Keller, R. E.; Francone, F. D., Genetic programmingan introduction (1997), Morgan Kaufmann Publishers, Inc: Morgan Kaufmann Publishers, Inc Los Altos, CA
[54] EOLE consortium. EOLE project: on-line optimization framework for telecom. http://www.lcr.thomson-csf.com/projects/www_eole; EOLE consortium. EOLE project: on-line optimization framework for telecom. http://www.lcr.thomson-csf.com/projects/www_eole
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.