| Metaheuristics: Intelligent Problem Solving | p. 1 |
| Introduction | p. 1 |
| Basic Concepts and Discussion | p. 5 |
| Local Search | p. 5 |
| Metaheuristics | p. 7 |
| Miscellaneous | p. 14 |
| A Taxonomy | p. 15 |
| Hybrids with Exact Methods | p. 19 |
| General Frames: A Pool-Template | p. 22 |
| Fine Tuning and Evaluation of Algorithms | p. 24 |
| Fine Tuning of Metaheuristics | p. 24 |
| Empirical Evaluation of Metaheuristics | p. 26 |
| Optimization Software Libraries | p. 30 |
| Conclusions | p. 30 |
| References | p. 32 |
| Just MIP it! | p. 39 |
| Introduction | p. 40 |
| MIPping Cut Separation | p. 41 |
| Pure Integer Cuts | p. 43 |
| Mixed Integer Cuts | p. 44 |
| A Computational Overview | p. 47 |
| MIPping Heuristics | p. 50 |
| Local Branching and Feasibility Pump | p. 51 |
| LB with Infeasible Reference Solutions | p. 54 |
| Computational Results | p. 55 |
| MIPping the Dominance Test | p. 61 |
| Borrowing Nogoods from Constraint Programming | p. 63 |
| Improving the Auxiliary Problem | p. 64 |
| Computational Results | p. 65 |
| References | p. 68 |
| MetaBoosting: Enhancing Integer Programming Techniques by Metaheuristics | p. 71 |
| Introduction | p. 71 |
| Integer Programming Techniques | p. 73 |
| Relaxations and Duality | p. 73 |
| LP-Based Branch-and-Bound | p. 75 |
| Cutting Plane Algorithm and Branch-and-Cut | p. 76 |
| Column Generation and Branch-and-Price | p. 77 |
| Metaheuristics for Finding Primal Bound | p. 75 |
| Initial Solutions | p. 78 |
| B&B Acting as Local Search Based Metaheuristic | p. 80 |
| Solution Merging | p. 81 |
| Metaheuristics and Lagrangian Relaxation | p. 83 |
| Collaborative Hybrids | p. 84 |
| Metaheuristics for Cut and Column Generation | p. 85 |
| Cut Separation | p. 85 |
| Column Generation | p. 86 |
| Case Study: A Lagrangian Decomposition/EA Hybrid | p. 87 |
| The Knapsack Constrained Maximum Spanning Tree Problem | p. 87 |
| Lagrangian Decomposition of the KCMST Problem | p. 88 |
| Lagrangian Heuristic | p. 89 |
| Evolutionary Algorithm for the KCMST | p. 89 |
| LD/EA Hybrid | p. 90 |
| Experimental Results | p. 91 |
| Case Study: Metaheuristic Column Generation | p. 92 |
| The Periodic Vehicle Routing Problem with Time Windows | p. 92 |
| Set Covering Formulation for the PVRPTW | p. 94 |
| Column Generation for Solving the LP Relaxation | p. 95 |
| Exact and Metaheuristic Pricing Procedures | p. 96 |
| Experimental Results | p. 97 |
| Conclusions | p. 99 |
| References | p. 100 |
| Usage of Exact Algorithms to Enhance Stochastic Local Search Algorithms | p. 103 |
| Introduction | p. 103 |
| Exploring large neighborhoods | p. 106 |
| NSP Example: Cyclic and Path Exchange Neighborhoods | p. 108 |
| NSP Example: Dynasearch | p. 111 |
| PNSP Example: Hyperopt Neighborhoods | p. 112 |
| Other Approaches | p. 113 |
| Discussion | p. 114 |
| Enhancing Metaheuristics | p. 115 |
| Example: Perturbation in Iterated Local Search | p. 115 |
| Other Approaches | p. 117 |
| Discussion | p. 118 |
| Using Branch-and-Bound Techniques in Constructive Search Heuristics | p. 118 |
| Example: Approximate Nondeterministic Tree Search (ANTS) | p. 119 |
| Other Approaches | p. 121 |
| Exploiting the Structure of Good Solutions | p. 121 |
| Example: Heuristic Concentration | p. 122 |
| Example: Tour Merging | p. 123 |
| Discussion | p. 124 |
| Exploiting Information from Relaxations in Metaheuristics | p. 125 |
| Example: Simplex and Tabu Search Hybrid | p. 125 |
| Discussion | p. 127 |
| Conclusions | p. 128 |
| References | p. 129 |
| Decomposition Techniques as Metaheuristic Frameworks | p. 135 |
| Introduction | p. 135 |
| Decomposition Methods | p. 137 |
| Lagrangean Relaxation | p. 137 |
| Dantzig-Wolfe Decomposition | p. 138 |
| Benders Decomposition | p. 139 |
| Metaheuristics Derived from Decompositions | p. 141 |
| A Lagrangean Metaheuristic | p. 142 |
| A Dantzig-Wolfe Metaheuristic | p. 142 |
| A Benders Metaheuristic | p. 143 |
| Single Source Capacitated Facility Location | p. 144 |
| Solving the SCFLP with a Lagrangean Metaheuristic | p. 146 |
| Solving the SCFLP with a Dantzig-Wolfe Metaheuristic | p. 147 |
| Solving the SCFLP with a Benders Metaheuristic | p. 149 |
| Computational Results | p. 150 |
| Lagrangean Metaheuristic | p. 151 |
| Dantzig-Wolfe Metaheuristic | p. 153 |
| Benders Metaheuristic | p. 153 |
| Conclusions | p. 155 |
| References | p. 156 |
| Convergence Analysis of Metaheuristics | p. 159 |
| Introduction | p. 159 |
| A Generic Metaheuristic Algorithm | p. 161 |
| Convergence | p. 164 |
| Convergence Notions | p. 164 |
| Best-So-Far Convergence | p. 165 |
| Model Convergence | p. 167 |
| Proving Convergence | p. 169 |
| Proving Best-So-Far Convergence | p. 169 |
| Proving Model Convergence | p. 169 |
| Convergence for Problems with Noise | p. 175 |
| Convergence Speed | p. 178 |
| Conclusions | p. 183 |
| References | p. 184 |
| MIP-based GRASP and Genetic Algorithm for Balancing Transfer Lines | p. 189 |
| Introduction | p. 189 |
| Problem Statement | p. 191 |
| Greedy Randomized Adaptive Search Procedure | p. 195 |
| Construction Phase | p. 195 |
| Improvement Phase | p. 197 |
| Genetic Algorithm | p. 198 |
| Experimental Results | p. 200 |
| Problem Instances | p. 200 |
| Experimental Settings | p. 201 |
| Results | p. 202 |
| Conclusions | p. 206 |
| References | p. 207 |
| (Meta-) Heuristic Separation of Jump Cuts in a Branch&Cut Approach for the Bounded Diameter Minimum Spanning Tree Problem | p. 209 |
| Introduction | p. 209 |
| Previous Work | p. 210 |
| The Jump Model | p. 211 |
| Jump Cut Separation | p. 213 |
| Exact Separation Model | p. 214 |
| Simple Construction Heuristic CA | p. 215 |
| Constraint Graph Based Construction Heuristic CB | p. 216 |
| Local Search and Tabu Search | p. 219 |
| Primal Heuristics | p. 220 |
| Computational Results | p. 222 |
| Conclusions and Future Work | p. 228 |
| References | p. 228 |
| A Good Recipe for Solving MINLPs | p. 231 |
| Introduction | p. 231 |
| The Basic Ingredients | p. 233 |
| Variable Neighbourhood Search | p. 233 |
| Local Branching | p. 234 |
| Branch-and-Bound for cMINLPs | p. 234 |
| Sequential Quadratic Programming | p. 235 |
| The RECIPE Algorithm | p. 236 |
| Hyperrectangular Neighbourhood Structure | p. 236 |
| Computational Results | p. 238 |
| MINLPLib | p. 239 |
| Conclusion | p. 242 |
| References | p. 243 |
| Variable Intensity Local Search | p. 245 |
| Introduction | p. 245 |
| The General VILS Framework | p. 246 |
| Experimental Studies | p. 249 |
| Conclusion | p. 250 |
| References | p. 251 |
| A Hybrid Tabu Search for the m-Peripatetic Vehicle Routing Problem | p. 253 |
| Introduction | p. 253 |
| Tabu Search | p. 255 |
| Initial Solution Heuristic and Neighborhood Structure | p. 255 |
| Penalization and Tabu List Management | p. 257 |
| Hybridization with b-Matching and Diversification | p. 257 |
| b-Matching | p. 257 |
| Hybridization | p. 258 |
| Diversification Procedure | p. 259 |
| Computational Analysis | p. 259 |
| VRP and m-PSP | p. 261 |
| m-PVRP with 2 ≤ m ≤ 7 | p. 262 |
| Conclusion | p. 263 |
| References | p. 264 |
| Index | p. 267 |
| Table of Contents provided by Ingram. All Rights Reserved. |
