×

Contraint-based combinators for local search. (English) Zbl 1102.68460

Summary: One of the most appealing features of constraint programming is its rich constraint language for expressing combinatorial optimization problems. This paper demonstrates that traditional combinators from constraint programming have natural counterparts for local search, although their underlying computational model is radically different. In particular, the paper shows that constraint combinators, such as logical and cardinality operators, reification, and first-class expressions can all be viewed as differentiable objects. These combinators naturally support elegant and efficient modelings, generic search procedures, and partial constraint satisfaction techniques for local search. Experimental results on a variety of applications demonstrate the expressiveness and the practicability of the combinators.

MSC:

68P10 Searching and sorting
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Codognet, C., & Diaz, D. (2001). Yet another local search method for constraint solving. In Proceedings of the International Symposium on Stochastic Algorithms: Foundations and Applications (SAGA 2001), pages 73–90. Berlin, Germany (December). · Zbl 1054.68646
[2] Dell’Amico, M., & Trubian, M. (1993). Applying tabu search to the job-shop scheduling problem. Ann. Oper. Res. 41: 231–252. · Zbl 0771.90056
[3] Di Gaspero, L., & Schaerf, A. (2002). Writing local search algorithms using EASYLOCAL ++. In VOß, S. & Woodrubb, D.L., eds., Optimization Software Class Libraries, Kluwer, Boston, MA.
[4] Dotú, I., Van Hentenryck, P., & Michel, L. (2005). Scheduling social golfers locally. In Proceedings of the Second International Conference on the Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR’05). Prague. · Zbl 1133.90336
[5] Freuder, E. (1992). Partial constraint satisfaction. Artif. Intell. 58: 21–70. · Zbl 05472872
[6] Galinier, P., & Hao, J.-K. (2000). A general approach for constraint solving by local search. In Proceedings of the Second International Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR’00), pages 57–69. Paderborn, Germany (March).
[7] Harvey, W., & Stuckey, P. (2003). Improving linear constraint propagation by changing constraint representation. Constraints, 8(2): 173–207. · Zbl 1039.68119
[8] Ilog Solver 4.4. (1998). Reference Manual. Ilog SA, Gentilly, France.
[9] Johnson, D., Aragon, C., McGeoch, L., & Schevon, C. (1989). Optimization by simulated annealing: An experimental evaluation; part I, graph partitioning. Oper. Res. 37(6): 865–893. · Zbl 0698.90065
[10] Laburthe, F., & Caseau, Y. (1998). SALSA: A language for search algorithms. In Fourth International Conference on the Principles and Practice of Constraint Programming (CP’98). Pisa (October). · Zbl 1020.68028
[11] Michel, L., & Van Hentenryck, P. (2000). Localizer. Constraints. 5: 41–82. · Zbl 0988.90015
[12] Michel, L., & Van Hentenryck, P. (2002). A constraint-based architecture for local search. In Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 101–110. Seattle (November).
[13] Michel, L., & Van Hentenryck, P. (2004). A simple Tabu search for warehouse location. Eur. J. Oper. Res. 157(3): 576–591. · Zbl 1067.90054
[14] Minton, S., Johnston, M. D., & Philips, A. B. (1990). Solving large-scale constraint satisfaction and scheduling problems using a heuristic repair method. In Proceedings of the Eighth National Conference on Artificial Intelligence (AAAI-90), pages 17–24. Boston (August).
[15] Nareyek, A. (1998). Constraint-Based Agents. Springer Verlag, Berlin. · Zbl 0968.68559
[16] Nareyek, A. (2004). Dragonbreath. www.ai-center.com/projects/dragonbreath/..
[17] Petit, T., Regin, J.-C., & Bessiere, C. (2001). Specific filtering Algorithms for over–constrained problems. In Proceedings of 7th International Conference on the Principles and Practice of Constraint Programming (CP’01), pages 451–463. Paphos, Cyprus (November).
[18] Prestwich, S. D. (2002). Super symmetric modeling for local search. In Second International Workshop on Symmetry in Constraint Satisfaction Problems. · Zbl 1013.90104
[19] Prestwich, S. D. (2003). Negative effects of modeling techniques on search performance. Ann. Oper. Res. 118: 137–150. · Zbl 1026.90109
[20] Ramalingam, G. (1993). Bounded Incremental Computation. Ph.D. thesis. University of Wisconsin-Madison. · Zbl 0921.68050
[21] Selman, B., Kautz, H., & Cohen, B. (1994). Noise strategies for improving local search. In Proceedings of the Eleventh National Conference on Artificial Intelligence (AAAI-94), pages 337–343. Seattle (July).
[22] Shaw, P., De Backer, B., & Furnon, V. (2002). Improved local Search for CP toolkits. Ann. Oper. Res. 115: 31–50. · Zbl 1011.90036
[23] Van Hentenryck, P. (2002). Constraint and integer programming in OPL. INFORMS J. Comput. 14(4): 345–372. · Zbl 1238.90102
[24] Van Hentenryck, P., & Deville, Y. (1991). The cardinality operator: A new logical connective and its application to constraint logic programming. In The 8th International Conference on Logic Programming (ICLP-91), pages 745–759. Paris, France (June).
[25] Van Hentenryck, P., & Michel, L. (2003). Control abstractions for local search. In Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming, pages 65–80. Cork, Ireland. · Zbl 1084.68033
[26] Van Hoeve, W. J., Pesant, G., & Rousseau, L.-M. (2004). On global warming (Softening global constraints). In Proceedings of 6th International Workshop on Preferences and Soft Constraints, Toronto, Canada (September). · Zbl 1100.68623
[27] Voss, S., & Woodruff, D. (2002). Optimization Software Class Libraries. Kluwer Academic Publishers. · Zbl 1055.68044
[28] Voudouris, C., & Tsang, E. (1996). Partial constraint satisfaction problems and guided local search. In Proceedings of the International Conference on Practical Applications of Constraint Technology (PACT-96), pages 337–356. London (April).
[29] Walser, J. (1998). Integer Optimization by Local Search. Springer Verlag.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.