Primal heuristics in Integer programming / Timo Berthold, Andrea Lodi, Domenico Salvagnin.

Format:

Book

Author/Creator:

Berthold, Timo, author.

Lodi, Andrea, author.

Salvagnin, Domenico, author.

Language:

English

Subjects (All):

Integer programming.

Physical Description:

1 online resource (ix, 129 pages) : digital, PDF file(s).

Edition:

1st ed.

Place of Publication:

Cambridge : Cambridge University Press, 2025.

Summary:

Primal heuristics guarantee that feasible, high-quality solutions are provided at an early stage of the solving process, and thus are essential to the success of mixed-integer programming (MIP). By helping prove optimality faster, they allow MIP technology to extend to a wide variety of applications in discrete optimization. This first comprehensive guide to the development and use of primal heuristics within MIP technology and solvers is ideal for computational mathematics graduate students and industry practitioners. Through a unified viewpoint, it gives a unique perspective on how state-of-the-art results are integrated within the branch-and-bound approach at the core of the MIP technology. It accomplishes this by highlighting all the required knowledge needed to push the heuristic side of MIP solvers to their limit and pointing out what is left to do to improve them, thus presenting heuristic approaches for MIP as part of the MIP solving process.

Contents:

Cover

Half-title

Endorsements

Title page

Imprints page

Contents

Preface

1 Introduction and Concepts

1.1 Notation

1.2 Algorithms for Mixed-Integer Programming

1.3 Primal Heuristics inside MIP Solvers

1.4 Rounding and Constraint Propagation

1.5 General Heuristic Concepts

1.6 Reference Points, Information and Statistics

1.7 Measuring the Impact of Primal Heuristics

1.8 Quiz

2 Large Neighborhood Search

2.1 Local Branching

2.2 Relaxation Induced Neighborhood Search

2.3 Polishing Heuristic

2.4 Exploiting Alternative Objective Functions

2.5 Structure-Based LNS Heuristics

2.6 Quiz

3 Rounding, Propagation and Diving

3.1 Rounding Heuristics

3.2 Propagation Heuristics

3.3 Diving Heuristics

3.4 Quiz

4 The Feasibility Pump Family

4.1 Basic Algorithm

4.2 Improving the Rounding Step

4.3 Improving the Projection Step

4.4 The Perturbation Step

4.5 Objective Diving

4.6 Quiz

5 Pivoting and Line Search Heuristics

5.1 Pivoting Heuristics

5.2 Line Search Heuristics

5.3 Quiz

6 Computational Study

6.1 The Impact of Primal Heuristics

6.2 Experiments with Additional Configurations

6.3 Quiz

7 Primal Heuristics for Mixed-Integer Nonlinear Programming

7.1 Feasibility Pumps

7.2 LNS-Based Primal Heuristics

7.3 Undercover

7.4 Quiz

8 Machine Learning for Primal Heuristics

8.1 Deploying Heuristics

8.2 Learning Parameters

8.3 Perspectives

8.4 Quiz

Appendix: Quiz Solutions

References

Index.

Notes:

Title from publisher's bibliographic system (viewed on 07 Apr 2025).

Description based on publisher supplied metadata and other sources.

ISBN:

1-009-57482-5

1-009-57479-5

OCLC:

1460256776