Exact and Heuristic Methods in Combinatorial Optimization: A Study on the Linear Ordering and the Maximum Diversity Problem (Applied Mathematical Sciences, 175)

✍ Scribed by Rafael Martí, Gerhard Reinelt

• Publisher: Springer
• Year: 2022
• Tongue: English
• Leaves: 232
• Edition: 2nd ed. 2022
• Category: Library

✦ Synopsis

In the last decades, algorithmic advances as well as hardware and software improvements have provided an excellent environment to create and develop solving methods to hard optimization problems. Modern exact and heuristic techniques are dramatically enhancing our ability to solve significant practical problems. This monograph sets out state-of-the-art methodologies for solving combinatorial optimization problems, illustrating them with two well-known problems.

This second edition of the book extends the first one by adding to the ‘linear ordering problem’ (LOP), included in the first edition, the ‘maximum diversity problem’ (MDP). In this way, we provide the reader with the background, elements and strategies to tackle a wide range of different combinatorial optimization problems. The exact and heuristic techniques outlined in these pages can be put to use in any number of combinatorial optimization problems. While the authors employ the LOP and the MDP to illustrate cutting-edge optimization technologies, the book is also a tutorial on how to design effective and successful implementations of exact and heuristic procedures alike.

This monograph provides the basic principles and fundamental ideas that will enable students and practitioners to create valuable applications based on both exact and heuristic technologies. Specifically, it is aimed at engineers, scientists, operations researchers, and other applications specialists who are looking for the most appropriate and recent optimization tools to solve particular problems. The book provides a broad spectrum of advances in search strategies with a focus on its algorithmic and computational aspects.

✦ Table of Contents

Preface
Contents
Chapter 1 Introduction
1.1 The Linear Ordering Problem
1.1.1 Applications
1.1.2 The LOLIB Library of Benchmark Instances
1.2 The Maximum Diversity Problem
1.2.1 Diversity measures and models
1.2.2 The MDPLIB Library of Benchmark Instances
Chapter 2 Heuristic Methods
2.1 Introduction
2.1.1 Assessing the Quality of Heuristics
2.2 Construction Heuristics
2.2.1 Early LOP Methods
2.2.2 Reconstruction in the MDP
2.2.3 General Insertions
2.2.4 Numerical Experiments
2.3 Local Search
2.3.1 Insertions in permutation problems
2.3.2 Exchanges in binary problems
2.3.3 LOP methods
2.4 Multi-Start Procedures
2.4.1 Variants of Multi-Start
2.4.2 Numerical Experiments
Chapter 3 Meta-Heuristics
3.1 Introduction
3.2 GRASP
3.2.1 Construction Phase
3.2.2 Improvement Phase
3.3 Strategic Oscillation and Iterated Greedy
3.4 Tabu Search
3.4.1 Short Term Memory
3.4.2 Long Term Memory
3.5 Simulated Annealing
3.6 Variable Neighborhood Search
3.6.1 VNS implementations for the LOP
3.6.2 VNS implementations for the MDP
3.7 Scatter Search
3.7.1 Reference Set Creation
3.7.2 Reference Set Update
3.7.3 Reference Set Rebuild
3.8 Genetic and Memetic Algorithms
3.9 Matheuristics
3.10 Experiments with the LOP
3.11 Experiments with the MDP
Chapter 4 Branch-and-Bound
4.1 Introduction
4.2 Branch-and-Bound with Partial Orderings for the LOP
4.3 Lexicographic Search
4.4 Extension of Lexicographic Search to Branch-and-Bound
4.5 Branch-and-Bound with Lagrangean Relaxation
4.6 Improved MDP formulations
4.7 Branch-and-Bound with Partial Selections for the MDP
Chapter 5 Branch-and-Cut for the LOP
5.1 Integer Programming
5.2 Cutting Plane Algorithms
5.3 Branch-and-Cut with 3-Dicycle Cuts
5.3.1 Solving the 3-Diycle Relaxation
5.3.2 An LP Based Heuristic
5.3.3 Computational Results with 3-Dicycles
5.4 Generation of Further Cuts
5.4.1 Chvátal-Gomory Cuts
5.4.2 Maximally Violated Mod-k Cuts
5.4.3 Mod-2 Cuts
5.5 Implementation of Branch-and-Cut
5.5.1 Initialization
5.5.2 Active Variables
5.5.3 Local Upper Bound
5.5.4 Branching
5.5.5 Fixing and Setting of Variables
5.5.6 Logical Implications
5.5.7 Selection of Nodes
5.5.8 Lower Bounds
5.5.9 Separation
5.5.10 Elimination of Constraints
5.5.11 Constraint Pool
5.5.12 Pricing
5.5.13 Infeasible LPs
5.5.14 Addition of Variables
5.6 Some Computational Results
Chapter 6 The Linear Ordering Polytope
6.1 Polyhedral Combinatorics and Basic Results
6.2 Facets of the Linear Ordering Polytope
6.3 Computation of Complete Descriptions
6.4 Differences between Facets
6.5 Separation of Small Facets
6.6 Computational Experiments with Small Facets
6.6.1 Comparison of Heuristics
6.6.2 Cutting Plane Selection
6.6.3 Number of Classes Taken into Account
6.6.4 Facet Selection
6.7 Local Cuts and Target Cuts
Chapter 7 Further Aspects
7.1 Approximative Algorithms
7.2 Integrality Gaps of LP Relaxations
7.3 Degree of Linearity
7.4 Semidefinite Relaxations
7.5 Context Independent Solvers
7.6 Difficulty of LOP Instances
7.7 Multiple Optimal Rankings
7.8 Sparse Problems
7.9 A Simple Dual Heuristic
7.10 Future Research on the LOP
7.11 Extensions of the MDP
References
Index