Matheuristics

Metaheuristics support managers in decision-making with robust tools that provide high-quality solutions to important applications in business, engineering, economics, and science in reasonable time frames, but finding exact solutions in these applications still poses a real challenge. However, because of advances in the fields of mathematical optimization and metaheuristics, major efforts have been made on their interface regarding efficient hybridization.This edited book will provide a survey of the state of the art in this field by providing some invited reviews by well-known specialists as well as refereed papers from the second Matheuristics workshop to be held in Bertinoro, Italy, June 2008. Papers will explore mathematical programming techniques in metaheuristics frameworks, and especially focus on the latest developments in Mixed Integer Programming in solving real-world problems.Topics to be covered will also include dual information and metaheuristics; metaheuristics for stochastic problems; MIP solvers as search components; decompositions and lower/upper bounds in metaheuristics/MIP codes (MH codes); and real-world case histories of successful MH applications.

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 C^A	p. 215
Constraint Graph Based Construction Heuristic C^B	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.

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.