Top

previous chapter Particle Swarm Methods

next chapter Random-Key Genetic Algorithms

Hint

Swipe to navigate through the chapters of this book

2018 | OriginalPaper | Chapter

22. POPMUSIC

Read first chapter

Authors: Éric D. Taillard, Stefan Voß

Publisher: Springer International Publishing

Published in: Handbook of Heuristics

» Get access to the full-text

Abstract

This chapter presents POPMUSIC, a general decomposition-based framework within the realm of metaheuristics and matheuristics that has been successfully applied to various combinatorial optimization problems. POPMUSIC is especially useful for designing heuristic methods for large combinatorial problems that can be partially optimized. The basic idea is to optimize subparts of solutions until a local optimum is reached. Implementations of the technique to various problems show its broad applicability and efficiency for tackling especially large-size instances.

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

Adams J, Balas E, Zawack D (1988) The shifting bottleneck procedure for job shop scheduling. Manag Sci 34:391–401 MathSciNetCrossRef

Alvim ACF, Taillard ÉD (2007) An efficient POPMUSIC based approach to the point feature label placement problem. In: Metaheuristic International Conference (MIC’07) Proceedings.

Alvim ACF, Taillard ÉD (2009) POPMUSIC for the point feature label placement problem. Eur J Oper Res 192(2):396–413 CrossRef

Alvim ACF, Taillard ÉD (2013) POPMUSIC for the world location routing problem. EURO J Transp Logist 2:231–254 CrossRef

Angelelli E, Mansini R, Speranza M (2010) Kernel search: a general heuristic for the multi-dimensional knapsack problem. Comput Oper Res 37(11):2017–2026 MathSciNetCrossRef

Angelelli E, Mansini R, Speranza M (2012) Kernel search: a new heuristic framework for portfolio selection. Comput Optim Appl 51(1):345–361. MathSciNetCrossRef

Balas E, Zemel E (1980) An algorithm for large zero-one knapsack problems. Oper Res 28(5):1130–1154 MathSciNetCrossRef

Ball MO (2011) Heuristics based on mathematical programming. Surv Oper Res Manag Sci 16(1):21–38

Concorde (2015) Concorde TSP solver. http://www.math.uwaterloo.ca/tsp/concorde/index.html

10.

Fischetti M, Lodi A (2003) Local branching. Math Program B 98:23–47 MathSciNetCrossRef

11.

Fischetti M, Polo C, Scantamburlo M (2004) A local branching heuristic for mixed-integer programs with 2-level variables, with an application to a telecommunication network design problem. Networks 44(2):61–72 MathSciNetCrossRef

12.

Glover F, Laguna M (1997) Tabu search. Kluwer, Dordrecht CrossRef

13.

Hansen P, Mladenović N, Urosević D (2006) Variable neighborhood search and local branching. Comput Oper Res 33(10):3034–3045 CrossRef

14.

Hill A, Voß S (2015) Generalized local branching heuristics and the capacitated ring tree problem. Working paper, IWI, University of Hamburg MATH

15.

Lalla-Ruiz E, Voß S (2016) POPMUSIC as a matheuristic for the berth allocation problem. Ann Math Artif Intell 76:173–189 MathSciNetCrossRef

16.

Lalla-Ruiz E, Voß S, Exposito-Izquierdo C, Melian-Batista B, Moreno-Vega JM (2015) A POPMUSIC-based approach for the berth allocation problem under time-dependent limitations. Ann Oper Res 1–27. doi:10.1007/s10479-015-2055-6, ISSN:1572-9338. Page online available http://dx.doi.org/10.1007/s10479-015-2055-6

17.

Lalla-Ruiz E, Schwarze S, Voß S (2016) A matheuristic approach for the p-cable trench problem. Working paper, IWI, University of Hamburg CrossRef

18.

Laurent M, Taillard ÉD, Ertz O, Grin F, Rappo D, Roh S (2009) From point feature label placement to map labelling. In: Metaheuristic International Conference (MIC’09) Proceedings.

19.

Maniezzo V, Stützle T, Voß S (eds) (2009) Matheuristics: hybridizing metaheuristics and mathematical programming. Springer, Berlin MATH

20.

Ostertag A, Doerner KF, Hartl RF, Taillard ÉD, Waelti P (2009) POPMUSIC for a real-world large-scale vehicle routing problem with time windows. J Oper Res Soc 60(7):934–943 CrossRef

21.

Pisinger D (1999) Core problems in knapsack algorithms. Oper Res 47(4):570–575 MathSciNetCrossRef

22.

Pisinger D, Ropke S (2007) A general heuristic for vehicle routing problems. Comput Oper Res 34(8):2403–2435 MathSciNetCrossRef

23.

Sniedovich M, Voß S (2006) The corridor method: a dynamic programming inspired metaheuristic. Control Cybern 35:551–578 MathSciNetMATH

24.

Taillard E, Voß S (2002) POPMUSIC—partial optimization metaheuristic under special intensification conditions. In: Ribeiro C, Hansen P (eds) Essays and surveys in metaheuristics. Kluwer, Boston, pp 613–629 CrossRef

25.

Taillard ÉD (1993) Parallel iterative search methods for vehicle routing problems. Networks 23(8):661–673 CrossRef

26.

Taillard ÉD (2003) Heuristic methods for large centroid clustering problems. J Heuristics 9(1):51–73. Old technical report IDSIA-96-96

27.

Woodruff D (1998) Proposals for chunking and tabu search. Eur J Oper Res 106:585–598 CrossRef

28.

Yamamoto M, Camara G, Lorena L (2002) Tabu search heuristic for point-feature cartographic label placement. GeoInformatica 6:77–90 CrossRef

Title

POPMUSIC

Book

Handbook of Heuristics

Print ISBN: 978-3-319-07123-7

Electronic ISBN: 978-3-319-07124-4

https://doi.org/10.1007/978-3-319-07124-4

DOI

https://doi.org/10.1007/978-3-319-07124-4_31

Authors:

Éric D. Taillard
Stefan Voß

Publisher

Springer International Publishing

Sequence number

Chapter number

Premium Partner

Image Credits