摘要
Difficult combinatorial optimization problems coming from practice are nowadays often approached by hybrid metaheuristics that combine principles of classical metaheuristic techniques with advanced methods from fields like mathematical programming, dynamic programming, and constraint programming. If designed appropriately, such hybrids frequently outperform simpler "pure" approaches as they are able to exploit the underlying methods' individual advantages and benefit from synergy. This article starts with a general review of design patterns for hybrid approaches that have been successful on many occasions. More complex practical problems frequently have some special structure that might be exploited. In the field of mixed integer linear programming, three decomposition techniques are particularly well known for taking advantage of special structures: Lagrangian decomposition, Dantzig-Wolfe decomposition (column generation), and Benders' decomposition. It has been recognized that these concepts may also provide a very fruitful basis for effective hybrid metaheuristics. We review the basic principles of these decomposition techniques and discuss for each promising possibilities for combinations with metaheuristics. The approaches are illustrated with successful examples from literature.
学科与关键词
- Hybrid metaheuristics in combinatorial optimization: A surveyBlum, Christian*; Puchinger, Jakob; Raidl, Guenther R.; Roli, AndreaAPPLIED SOFT COMPUTING, 2011, 11(6): 4135-4151.被引 534
- Hybrid Metaheuristics in Combinatorial Optimization: A TutorialChristian, BlumTheory and Practice of Natural Computing, Springer Berlin Heidelberg, 1-10, 2012.
- Combining metaheuristics with mathematical programming, constraint programming and machine learningTalbi, El-Ghazali*4OR-A Quarterly Journal of Operations Research, 2013, 11(2): 101-150.被引 20
