Preface
References
Contents
Acronyms
List of Algorithms
Part I Contextual Issues
1 The Generalized Assignment Problem
1.1 Introduction
1.1.1 NP-hardness
1.1.2 Special Cases and Extensions
1.2 Lower Bounds
1.2.1 Linear Relaxation
1.2.2 Lagrangian Relaxation
1.2.3 Lagrangian Decomposition
1.2.4 Surrogate Relaxation
1.2.5 Benders Decomposition
1.2.6 Column Generation
1.3 Upper Bounds
1.3.1 Constructive Heuristics
1.3.2 Local Search Heuristics
1.4 Fixing Heuristics
1.5 Exact Algorithms
1.6 Related Literature
References
2 Automatic Design for Matheuristics
2.1 Introduction
2.2 Parameter Configuration
2.2.1 Parameters
2.2.2 Parameter Configuration Problem
2.2.3 Automatic Algorithm Configuration
2.2.4 ParamILS
2.2.5 SMAC
2.2.6 irace
2.3 Design of Algorithms
2.3.1 Automated Configuration of Existing Algorithms
2.3.2 Integration into an Algorithm(Re-)engineering Process
2.3.3 Advanced Uses of Configurators
2.4 An Example: irace
2.5 Related Literature
References
Part II Metaheuristic Hybrids
3 Single Solution Metaheuristics
3.1 Introduction
3.2 Simulated Annealing
3.2.1 SA for the GAP, An Example
3.3 Tabu Search
3.3.1 TS for the GAP, An Example
3.4 Iterated Local Search
3.4.1 ILS for the GAP, An Example
3.5 Variable Neighborhood Search
3.5.1 VNS for the GAP, An Example
3.6 GRASP
3.6.1 GRASP for the GAP, An Example
3.7 Ejection Chains
3.7.1 Solution Fixing
3.7.2 Ejection Chain for the GAP, An Example
3.8 Related Literature
References
4 Population-Based Metaheuristics
4.1 Introduction
4.2 Evolutionary Algorithms
4.2.1 Genetic Algorithms
4.2.2 Evolution Strategies
4.2.3 Matheuristic Evolutionary Algorithms
4.2.4 Genetic Algorithm for the GAP, an Example
4.3 Ant Colony Optimization
4.3.1 ACO Metaheuristics
4.3.2 Matheuristic ACO
4.3.3 ANTS
4.3.4 ANTS for the GAP
4.4 Scatter Search
4.4.1 Path Relinking
4.4.2 Matheuristic Scatter Search
4.4.3 Scatter Search for the GAP, an Example
4.5 Related Literature
References
Part III Original Matheuristics
5 Diving Heuristics
5.1 Introduction
5.2 Relaxation Induced Neighborhood Search
5.2.1 RINS for the GAP
5.3 Local Branching
5.3.1 Local Branching for the GAP
5.4 Feasibility Pump
5.5 Related Literature
References
6 Very Large-Scale Neighborhood Search
6.1 Introduction
6.2 Variable-Depth Methods
6.3 Network-Flow-Based Improvement Algorithms
6.3.1 Neighborhoods Defined by Cycles
6.3.2 Neighborhoods Defined by Paths
6.3.3 Neighborhoods Defined by Assignmentsand Matching
6.4 Efficiently Solvable Restrictions
6.5 VLNS for the GAP
6.6 Related Literature
References
7 Decomposition-Based Heuristics
7.1 Introduction
7.2 Linear Decompositions
7.2.1 Dantzig–Wolfe Decomposition
7.2.2 Lagrangian Relaxation and Decomposition
7.2.3 Benders Decomposition
7.3 Matheuristics Derived from Decompositions
7.3.1 Lagrangian Metaheuristic
7.3.2 Lagrangian Matheuristics
7.4 A Lagrangian Matheuristic for the GAP
7.4.1 The Fixing Heuristic
7.4.2 LagrHeuristic: Computational Trace
7.5 Related Literature
References
8 Corridor Method
8.1 Introduction
8.2 Corridor Method for the GAP
8.3 Related Literature
References
9 Kernel Search
9.1 Introduction
9.2 Kernel Search for the GAP
9.3 Related literature
References
10 Fore-and-Back
10.1 Introduction
10.2 Fore-and-Back
10.2.1 Search Trees
10.2.2 Fore-and-Back Pseudocode
10.3 Fore-and-Back for the GAP
10.4 Related Literature
References
Index