Book contents
- Frontmatter
- Contents
- Preface
- 1 Introduction and Concepts
- 2 Large Neighborhood Search
- 3 Rounding, Propagation and Diving
- 4 The Feasibility Pump Family
- 5 Pivoting and Line Search Heuristics
- 6 Computational Study
- 7 Primal Heuristics for Mixed-Integer Nonlinear Programming
- 8 Machine Learning for Primal Heuristics
- Appendix Quiz Solutions
- References
- Index
2 - Large Neighborhood Search
Published online by Cambridge University Press: 04 April 2025
- Frontmatter
- Contents
- Preface
- 1 Introduction and Concepts
- 2 Large Neighborhood Search
- 3 Rounding, Propagation and Diving
- 4 The Feasibility Pump Family
- 5 Pivoting and Line Search Heuristics
- 6 Computational Study
- 7 Primal Heuristics for Mixed-Integer Nonlinear Programming
- 8 Machine Learning for Primal Heuristics
- Appendix Quiz Solutions
- References
- Index
Summary
This chapter concerns the vast family of large neighborhood search primal heuristics. These are local search heuristics that generally assume the knowledge of one or more feasible MIP solutions and explore "large" neighborhoods in the attempt to improve the incumbent, i.e., the best feasible solution computed so far by the MIP algorithm. A neighborhood is large if, in general, it cannot be explored by complete enumeration, so the various techniques developed for defining those neighborhoods and exploring them are discussed.
- Type
- Chapter
- Information
- Primal Heuristics in Integer Programming , pp. 30 - 46Publisher: Cambridge University PressPrint publication year: 2025