Chapter 8
Parallel Combinatorial Optimization
Van-Dat Cung, Bertrand Le Cun,
Catherine Roucairol,
Bertrand Le Cun
PRiSM, University of Versailles, St-Quentin-en-Yvelines, France
Search for more papers by this authorCatherine Roucairol
PRiSM, University of Versailles, St-Quentin-en-Yvelines, France
Search for more papers by this authorVan-Dat Cung, Bertrand Le Cun,
Catherine Roucairol,
Bertrand Le Cun
PRiSM, University of Versailles, St-Quentin-en-Yvelines, France
Search for more papers by this authorCatherine Roucairol
PRiSM, University of Versailles, St-Quentin-en-Yvelines, France
Search for more papers by this authorBook Editor(s):Vangelis Th. Paschos,
Vangelis Th. Paschos
LAMSADE, University of Paris-Dauphine, France
Search for more papers by this authorFirst published: 13 February 2013
Summary
This chapter contains sections titled:
-
Impact of parallelism in combinatorial optimization
-
Parallel metaheuristics
-
Parallelizing tree exploration in exact methods
-
Conclusion
-
Bibliography
Bibliography
- [ANS 01a] ANSTREICHER K.M., BRIXIUS N.W., “A new bound for the quadratic assignment problem based on convex quadratic programming”, Mathematical Programming, vol. 80, p. 341–357, 2001.
- [ANS 01b] ANSTREICHER K.M., BRIXIUS N.W., “Solving quadratic assignment problems using convex quadratic programming relaxations”, Optimization Methods and Software, vol. 16, p. 49–68, 2001.
- [ANS 02] ANSTREICHER K.M., BRIXIUS N.W., GOUX J.-P., LINDEROTH J., “Solving large quadratic assignment problems on computational grids”, Mathematical Programming, vol. 91, num. 3, p. 563–588, 2002.
- [APP 98] APPLEGATE D., BIXBY R., CHVÁTAL V., COOK W., “On the solution of the traveling salesman problems”, Documenta Mathematica, vol. Extra volume ICM, num. III, p. 645–656, 1998.
- [BAT 92] BATTITI R., TECCHIOLLI G., “Parallel biased search for combinatorial optimization: genetic algorithms and Tabu”, Microprocessors and Microsystems, vol. 16, p. 351–367, 1992.
- [BRU 96] BRUENGGER A., CLAUSEN J., MARZETTA A., PERREGAARD M., Joining Forces in Solving Large-Scale Quadratic Assignment Problems in Parallel, Report, DIKU, University of Copenhagen, 1996.
- [BUR 91] BURKARD R.E., ÇELA E., KARISCH S.E., RENDL F., “QAPLIB – A quadratic assignment problem library”, Available at the address www.opt.math.tu-graz.ac.at/qaplib, 1991, First published in European Journal of Operational Research, vol. 55, p. 115–119, 1991.
- [CLA 97] CLAUSEN J., PERREGAARD M., “Solving large quadratic assignment problems in parallel”, Computational Optimization and Applications, vol. 8, p. 111–128, 1997.
- [CON] TSP sites at the Universities of Rice amd Princeton: Concorde Program, www.keck.caam.rice.edu/tsp/ or www.math.princeton.edu/tsp/.
-
[CRA 98] CRAINIC T.G., TOULOUSE M., “Parallel metaheuristics”, CRAINIC T.G., LA-PORTE G., Eds., Fleet Management and Logistics, p. 205–251, Kluwer Academic Publishers, Norwell, 1998.
10.1007/978-1-4615-5755-5_10 Google Scholar
- [CRA 02a] CRAINIC T.G., Adaptive Memory and Eolution: Tabu Search and Scatter Search, Chapter “Parallel computation, co-operation, Tabu search”, Kluwer Academic Publishers, Norwell, 2002.
- [CRA 02b] CRAINIC T.G., TOULOUSE M., State-of-the-Art Handbook in Metaheuristics, Chapter “Parallel strategies for meta-heuristics”, p. 475–514, Kluwer Academic Publishers, Norwell, 2002.
- [CUN 97a] CUNG V.-D., MAUTOR T., MICHELON P., TAVARES A., “Improving the efficiency of scatter search”, Metaheuristics International Conference, MIC'97, INRIA Sophia-Antipolis, INRIA, July 1997.
- [CUN 97b] CUNG V.-D., MAUTOR T., MICHELON P., TAVARES A., “A Scatter search based approach for the quadratic assignment problem”, BAECK T., MICHALEWICZ Z., YAO X., Eds., Proceedings of IEEE-ICEC'97, IEEE International Conference on Evolutionary Computation, IEEE Neural Networks Council and the Evolutionary Programming Society, p. 165–170, April 1997.
- [CUN 98] CUNG V.-D., MAUTOR T., MICHELON P., “Different parallelizations of the scatter search method”, European Conference on Operational Research, Université Libre de Bruxelles, Belgium, July 1998.
- [CUN 99a] CUNG V.-D., MAUTOR T., MICHELON P., “Impacts du parallélisme sur la recherche dispersée”, Congrès Français de Recherche Opérationelle et Aide à la Décision ROADEF, January 1999.
- [CUN 99b] CUNG V.-D., MAUTOR T., ROUCAIROL C., “A parallel branch-and-bound algorithm using a semidefinite programming relaxation for the vertex-cover problem”, ECCO XII meeting of the European Chapter of Combinatorial Optimization, Laboratoire d'Informatique de Marseille, Faculté des Sciences de Luminy, France, 1999.
-
[CUN 00a] CUNG V.-D., HIFI M., LE CUN B., “Constrained two-dimensional cutting stock problems - a best-first branch-and-bound algorithm”, International Transactions in Operational Research (ITOR), vol. 7, num. 3, p. 185–210, 2000.
10.1111/j.1475-3995.2000.tb00194.x Google Scholar
- [CUN 00b] CUNG V.-D., LE CUN B., “Multithreaded branch-and-bound tree searches”, Workshop on Parallel Computing for Irregular Applications, in Conjunction with HPCA-6, IRIT, Toulouse, France, p. 30–34, January 2000.
- [CUN 02] CUNG V.-D., MARTINS S.L., RIBEIRO C.C., ROUCAIROL C., Essays and Surveys in Metaheuristics, Chapter “Strategies for the parallel implementation of metaheuristics”, p. 263-308, Kluwer Academic Publishers, Norwell, 2002.
- [CUN 03] CUNG V.-D., ROUCAIROL C., Résolution de problème de RO par les Métaheuristiques, Chapter “Implémentations parallèles des métaheuristiques”, Traité IC2, Série informatique et Système d'information, Hermès, Paris, 2003.
- [DEN 96] DENNEULIN Y., LE CUN B., MAUTOR T., MÉHAUT J.-F., “Distributed branch and bound algorithms for large quadratic assignment problems”, Computer Science Technical Section on Computer Science and Operations Research, 1996.
- [DOD 90] DODD N., “Slow annealing versus multiple fast annealing runs – an empirical investigation”, Parallel Computing, vol. 16, p. 269–272, 1990.
- [FER 01] FERRIS M.C., PATAKI G., SCHMIETA S., “Solving the Seymour problem”, OPTIMA - Mathematical Programming Society Newsletter, vol. 66, October 2001.
-
[GLO 77] GLOVER F., “Heuristic for integer programming using surrogate constraints”, Decision Sciences, vol. 8, p. 156–166, 1977.
10.1111/j.1540-5915.1977.tb01074.x Google Scholar
- [HAH 98a] HAHN P.M., GRANT T., “Lower bounds for the quadratic assignment problem based upon a dual formulation”, Operations Research, vol. 46, p. 912–942, 1998.
- [HAH 98b] HAHN P.M., GRANT T., HALL N., “A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method”, European Journal of Operational Research, vol. 108, p. 629–640, 1998.
- [HAH 01] HAHN P., HIGHTOWER W.L., JOHNSON T.A., GUIGNARD-SPIELBERG M., ROUCAIROL C., “Tree elaboration strategies in branch and bound algorithms for solving the quadratic assignment problem”, Yugoslavian Journal of Operational Research, vol. 11, num. 1, 2001.
- [KAL 96] KALE L.V., KRISHNAN S., Parallel Programming using C++, Chapter “Charm++: Parallel Programming with Message-Driven Objects”, p. 175-213, MIT Press, 1996, Parallel Programming Laboratory, Department of Computer Science, University of Illinois at Urbana-Champaign.
-
[KAL 99] KALE L., BRUNNER R., PHILLIPS J., VARADARAJAN K., “Application performance of a Linux cluster using converse”, Proceedings of 3rd Workshop on Runtime Systems for Parallel Programming,Rolim et al. (Eds.), Lecture Notes in Computer Science 1586, IPPS/SPDP, Springer, p. 483–495, 1999.
10.1007/BFb0097933 Google Scholar
- [KOO 57] KOOPMANS T.C., BECKMANN M.J., “Assignment problems and the location of economic activities”, Econometrica, vol. 25, p. 53–76, 1957.
- [MAN 95] MANS B., MAUTOR T., ROUCAIROL C., “A parallel depth first search branch and bound algorithm for the quadratic assignment problem”, EJOR European Journal of Operational Research, vol. 81, num. 3, p. 617–628, 1995.
- [MAN 96] MANS B., ROUCAIROL C., “Performances of parallel branch and bound algorithms with best-first search”, Discrete Applied Mathematics, vol. 66, num. 1, p. 57–76, April 1996.
- [NIC 98] NICKLAS L.D., ATKINS R.W., SETIA S.K., WANG P.Y., “The design and implementation of a parallel solution to cutting stock problem”, Concurrency: Practice and Experience, vol. 10, October 1998.
-
[OSB 91] OSBORNE L., GILLETT B., “A comparison of two simulated annealing algorithms applied to the directed Steiner problem on networks”, ORSA Journal on Computing, vol. 3, p. 213–225, 1991.
10.1287/ijoc.3.3.213 Google Scholar
-
[PAR 94] PARDALOS P.M., WOLKOWICZ H., Eds., Quadratic Assignment and Related Problems, vol. 16 of DIMACS Series on Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, 1994.
10.1090/dimacs/016 Google Scholar
-
[PRE 99] PREUX P., TALBI E.-G., “Towards hybrid evolutionary algorithms”, International Transactions in Operational Research, vol. 6, num. 6, p. 557–570, October 1999.
10.1111/j.1475-3995.1999.tb00173.x Google Scholar
- [REI ] REINELT G., “TSPLIB – la librairie officielle du problème du voyageur de commerce”, Available at the address www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ or www.crpc.rice.edu/softlib/tsplib/.
- [SAH 76] SAHNI S., GONZALEZ T., “P-complete approximation problems”, Journal of the ACM, vol. 23, p. 555–565, 1976.
- [TAI 91] TAILLARD E.D., “Robust Taboo search for the quadratic assignment problem”, Parallel Computing, vol. 17, p. 443–455, 1991.
- [TSC 95] TSCHÖKE S., HOLTHÖFER N., “A new parallel approach to the constrained two-dimensional cutting stock problem”, Proceedings of the Second International Workshop on Parallel Algorithms for Irregularly Structured Problems, num. 980LNCS, Spinger-Verlag, p. 768–776, 1995.
-
[VER 95] VERHOVEN M. G.A., AARTS E. H.L., “Parallel local search”, Journal of Heuristics, vol. 1, p. 43–65, 1995.
10.1007/BF02430365 Google Scholar
- [VER 96] VERHOEVEN M., Parallel Local Search, PhD thesis, Eindhoven University of Technology, The Netherlands, 1996.
- [VOS 93] VOSS S., Tabu Search: Applications and Prospects, Chapter “Network optimization problems”, p. 333–353, World Scientific, 1993.
