zbMATH — the first resource for mathematics

Parallel and distributed local search in COMET. (English) Zbl 1179.90288
Summary: The availability of commodity multiprocessors and high-speed networks of workstations offer significant opportunities for addressing the increasing computational requirements of optimization applications. To leverage these potential benefits, it is important, however, to make parallel and distributed processing easily accessible to a wide audience of optimization programmers. This paper addresses this challenge by proposing parallel and distributed programming abstractions that keep the distance from sequential local search algorithms as small as possible. The abstractions, including parallel loops, interruptions, thread pools, and shared objects, are compositional and cleanly separate the optimization program and the parallel instructions. They have been evaluated experimentally on a variety of applications, including warehouse location and coloring, for which they provide significant speedups.

90C27 Combinatorial optimization
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68W10 Parallel algorithms in computer science
90B40 Search theory
Full Text: DOI
[1] Moore, G.E., Cramming more components onto integrated circuits, Electronics, 38, 8, 114-117, (1965)
[2] Luby, M.; Sinclair, A.; Zuckerman, D., Optimal speedup of Las Vegas algorithms, Information processing letters, 47, 4, 173-180, (1993) · Zbl 0797.68139
[3] Gomes, C.; Selman, B.; Crato, N.; Kautz, H., Heavy-tailed phenomena in satisfiability and constraint satisfaction problems, Journal of automated reasoning, 24, 1/2, 67-100, (2000) · Zbl 0967.68145
[4] Mauricio, G.; Resende, C.; Werneck, R.F., A hybrid multistart heuristic for the uncapacitated facility location problem, European journal of operational research, 174, 1, 54-68, (2006) · Zbl 1116.90074
[5] Harm G, Van Hentenryck P. A multistart variable neighborhood search for uncapacitated warehouse location. In: Proceedings of the 6th metaheuristics international conference (MIC-2005), Vienna, Austria, August 2005.
[6] Laguna, M., Scatter search, (), 183-193
[7] Perron L. Search procedures and parallelism in constraint programming. In: Proceedings of the fifth international conference on the principles and practice of constraint programming, Alexandria, Virginia, October 1999. p. 346-60.
[8] Van Hentenryck P, Michel L. Control abstractions for local search. In: Proceedings of the ninth international conference on principles and practice of constraint programming, Cork, Ireland, 2003. p. 65-80.
[9] Michel L, Van Hentenryck P. A constraint-based architecture for local search. In: Conference on object-oriented programming systems, languages, and applications, Seattle, November 2002. p. 101-10.
[10] Van Hentenryck, P.; Michel, L., Constraint-based local search, (2005), MIT Press Cambridge, MA
[11] Nowicki, E.; Smutnicki, C., A fast taboo search algorithm for the job shop problem, Management science, 42, 6, 797-813, (1996) · Zbl 0880.90079
[12] Gnu lightning \(\langle\)http://www.gnu.org/software/lightning⟩.
[13] Minton, S.; Johnston, M.; Philips, A.; Laird, P., Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems, Artificial intelligence, 58, 1-3, 161-205, (1992) · Zbl 0782.90054
[14] Hentenryck P, Michel L. Synthesis of constraint-based local search algorithms from high-level models. In: Proceedings of the AAAI-2007, August 2007.
[15] Xu Y, Ralphs T, Ladányi L, Saltzman M. Alps: a framework for implementing parallel tree search algorithms. The next wave in computing, optimization, and decision technologies, 2005. p. 319-34.
[16] Michel, L.; Van Hentenryck, P., A simple tabu search for warehouse location, European journal of operational research, 157, 3, 576-591, (2004) · Zbl 1067.90054
[17] Dell’Amico, M.; Trubian, M., Applying tabu search to the job-shop scheduling problem, Annals of operations research, 41, 231-252, (1993) · Zbl 0771.90056
[18] Ilog Solver 6.2. Documentation. Ilog SA, Gentilly, France, 2006.
[19] Van Hentenryck P, Michel L, Liu L. Constraint-based combinators for local search. In: Proceedings of the tenth international conference on principles and practice of constraint programming, Toronto, Canada, October 2004. p. 47-61. · Zbl 1152.68589
[20] Dorne, R.; Hao, J.K., Tabu search for graph coloring, T-colorings and set T-colorings, chapter meta-heuristics: advances and trends in local search paradigms for optimization, (1998), Kluwer Academic Publishers Dordrecht, p. 77-92
[21] Dotu, I.; Van Hentenryck, P., A simple hybrid evolutionary algorithm for finding golomb rulers, (), 2018-2023
[22] Walser, J., Integer optimization by local search, (1998), Springer Berlin
[23] Schulte C. Parallel search made simple. In: Proceedings of TRICS, a post-conference workshop of CP 2000, Singapore, September 2000.
[24] Dagum, L.; Menon, R., Openmp: an industry-standard API for shared-memory programming, IEEE computational science and engineering, 5, 46-55, (1998)
[25] Chandra, R.; Dagum, L.; Kohr, D.; Maydan, D.; McDonald, J.; Menon, R., Parallel programming in openmp, (2000), Morgan Kaufmann Los Altos, CA, ISBN:1558606718
[26] Van Hentenryck P, Michel L. Nondeterministic control for hybrid search. 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, May 2005.
[27] Chamberlain B, Choi S-E, Deitz S, Snyder L. The high-level parallel language ZPL improves productivity and performance. In: Proceedings of the IEEE international workshop on productivity and performance in high-end computing, 2004.
[28] Allen, Chase, Luchangco, Maessen, Ryu, Steele, Tobin-Hochstadt. The fortress language specification, V0.866. Sun microsystems, February 2006.
[29] Deitz S. Renewed hope for data parallelism: unintegrated support for task parallelism in zpl. Technical Report UW-CSE-2003-12-04; December 2003.
[30] Blumofe, R.; Joerg, C.; Kuszmaul, B.; Leiserson, C.; Randall, K.; Zhou, Y., Cilk: an efficient multithreaded runtime system, Journal of parallel and distributed computing, 37, 1, 55-69, (1996)
[31] Supercomputing Technologies Group MIT Laboratory for Computer Science, Cambridge, MA. Cilk Reference Manual v5.4.2.3 (rev 2867), April 2006.
[32] Ralphs, T.; Ládanyi, L.; Saltzman, M., A library hierarchy for implementing scalable parallel search algorithms, Journal of supercomputing, 28, 2, 215-234, (2004) · Zbl 1062.90039
[33] Michel L, See A, Hentenryck P. Parallelizing constraint programs transparently. In: Principles and practice of constraint programming, September 2007.
[34] Goodale T, Allen G, Lanfermann G, Masso J, Radke T, Seidel E, et al. The cactus framework and toolkit: design and applications. In: High performance computing for computational science—VECPAR 2002: 5th international conference, Porto, Portugal, June 2002. p. 15-36. · Zbl 1027.65524
[35] Philippsen, M.; Zenger, M., Javaparty—transparent remote objects in Java, Concurrency: practice & experience, 6, 109-133, (1995)
[36] Yokoo, M.; Durfee, E.H.; Ishida, T.; Kuwabara, K., The distributed constraint satisfaction problem: formalization and algorithms, Knowledge and data engineering, 10, 5, 673-685, (1998)
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.