The linear ordering problem : exact and heuristic methods in combinatorial optimization / Rafael Martí, Gerhard Reinelt.

Format:

Book

Author/Creator:

Martí, Rafael (Rafael Cunquero)

Contributor:

Reinelt, G. (Gerhard)

Series:

Applied mathematical sciences (Springer-Verlag New York Inc.) ; v. 175.

Applied mathematical sciences (Springer-Verlag New York Inc.)

Language:

English

Subjects (All):

Combinatorial optimization.

Mathematical optimization.

Sequences (Mathematics).

Physical Description:

xii, 171 pages : illustrations (some color) ; 24 cm.

Place of Publication:

Berlin ; New York : Springer, [2011]

Summary:

Complex optimization problems abound in the real world. In the face of these challenges, established methods often fall short of providing solutions. However, 'exact' and 'heuristic' techniques are dramatically enhancing our ability to solve significant practical problems in the world of optimization. They are changing the landscape in the field, broadening the frontiers of the possible, and allowing us to engage effectively with a whole new range of challenges. This monograph sets out state-of-the-art optimization methods for tackling the 'linear ordering problem'(LOP).Whereas important applications in business, engineering and economics lie beyond the reach of methodologies that have been the focus of academic research for three decades, the fresh approaches set out in this volume provide practical solutions to the LOP.

The focus on the LOP does not limit the monograph's scope and applicability, however. 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 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. The information in these pages provides readers with a toolkit that can be employed in a variety of settings. As a result, the book will be of great interest to researchers and practitioners in a number of fields, including computer science, mathematics, operations research, management science, industrial engineering and economics. It is also suitable for use as a textbook on issues of practical optimization in a masters course, or as a reference book for engineering optimization algorithms. The authors have sought to make the book accessible to as wide an audience as possible by providing the reader with basic definitions and concepts in optimization. In addition, the numerous tutorials aid speedy assimilation, while the coverage given to the next generation of Flash software prepares readers for future developments. Book jacket.

Contents:

1 Introduction 1

1.l Basic definitions 1

1.2 Applications of the Linear Ordering Problem 3

1.2.1 Equivalent Graph Problems 3

1.2.2 Related Graph Problems 4

1.2.3 Aggregation of Individual Preferences 4

1.2.4 Binary Choice Probabilities 5

1.2.5 Ttiangulation of Input-Output Tables 5

1.2.6 Optimal Weighted Ancestry Relationships 6

1.2.7 Ranking in Sports Tournaments 6

1.2.8 Corruption Perception 7

1.2.9 Crossing Minimization 8

1.2.10 Linear Ordering with Quadratic Objective Function 8

1.2.11 Scheduling with Precedences 9

1.2.12 Linear Ordering with Cumulative Costs 9

1.2.13 Coupled Task Problem 9

1.2.14 Target Visitation Problem 10

1.3 Benchmark Problems 10

1.3.1 Data Format 10

1.3.2 Input-Output Matrices 12

1.3.3 Randomly Generated Instances A (Type 1) 13

1.3.4 Randomly Generated Instances A (Type 2) 13

1.3.5 Randomly Generated Instances B 13

1.3.6 SGB Instances 13

1.3.7 Instances of Schiavinotto and Stiltzle 14

1.3.8 Instances of Mitchell and Borchers 14

1.3.9 Further Special Instances 14

2 Heuristic Methods 17

2.1 Introduction 17

2.1.1 Assessing the Quality of Heuristics 19

2.2 ConstlUction Heuristics 21

2.2.1 The Method of Chenery and Watanabe 21

2.2.2 Heuristics of Aujac & Masson 22

2.2.3 Heuristics of Becker 22

2.2.4 Best Insertion 23

2.3 Local Search 25

2.3.1 Insertion 26

2.3.2 The Heuristic of Chan as & Kobylanski 27

2.3.3 k-opt 27

2.3.4 Kernighan-Lin Type Improvement 27

2.3.5 Local Enumeration 29

2.4 Multi-Start Procedures 30

2.4.1 Variants of Multi-Start 31

2.4.2 Experiments with the LOP 33

3 Meta-Heuristics 41

3.1 Introduction 41

3.2 GRASP 43

3.2.1 Construction Phase 44

3.2.2 Improvement Phase 48

3.3 Tabu Search 50

3.3.1 Short Term Memory 51

3.3.2 Long Term Memory 53

3.4 Simulated Annealing 56

3.5 Variable Neighborhood Search 60

3.5.1 Variable Neighborhood Descent 61

3.5.2 Restricted Variable Neighborhood Search 61

3.5.3 Basic Variable Neighborhood Search 62

3.5.4 Frequency Variable Neighborhood Search 62

3.5.5 Hybrid Variable Neighborhood Search 63

3.6 Scatter Search 66

3.6.1 Reference Set Creation 70

3.6.2 Reference Set Update 71

3.6.3 Reference Set Rebuild 73

3.7 Genetic Algorithms 77

3.8 Empilical Comparison 82

4 Branch-and-Bound 85

4.1 Introduction 85

4.2 Branch-and-Bound with Partial Orderings 87

4.3 Lexicographic Search 89

4.4 Extension of Lexicographic Search to Branch-and-Bound 89

4.5 Branch-and-Bound with Lagrangian Relaxation 91

5 Branch-and-Cut 95

5.1 Integer Programming 95

5.2 Cutting Plane Algorithms 97

5.3 Branch-and-Cut with 3-Dicycle Cuts 100

5.3.1 Solving the 3-Diycle Relaxation 101

5.3.2 An LP Based Henristic 102

5.3.3 Computational Results witl1 3-Dicycles 102

5.4 Generation of Further Cuts 104

5.4.1 Chvatal-Gomory Cuts 104

5.4.2 Maximally Violated Mod-k Cuts 105

5.4.3 Mod-2 Cuts 107

5.5 Implementation of Branch-and-Cut 107

5.5.1 Initialization 108

5.5.2 Active Variables 109

5.5.3 Local Upper Bound 109

5.5.4 Branching 109

5.5.5 Fixing and Setting of Variables 109

5.5.6 Logical Implications 110

5.5.7 Selection of Nodes 110

5.5.8 Lower Bounds 111

5.5.9 Separation 111

5.5.10 Elimination of Constraints 111

5.5.11 Constraint Pool 111

5.5.12 Pricing 111

5.5.13 Infeasible LPs 112

5.5.14 Addition of Variables 112

5.6 Some Computational Results 113

6 The Linear Ordering Polytope 117

6.1 Polyhedral Combinatorics and Basic Results 117

6.2 Facets of the Linear Ordering Polytope 120

6.3 Computation of Complete Descriptions 126

6.4 Differences between Facets 130

6.5 Separation of Small Facets 135

6.6 Computational Experiments with Small Facets 139

6.6.1 Comparison of Henristics 139

6.6.2 Cutting Plane Selection 139

6.6.3 Number of Classes Taken into Account 140

6.6.4 Facet Selection 141

6.7 Local Cuts and Target Cuts 141

7 Further Aspects 145

7.1 Approximative Algorithms 145

7.2 Integrality Gaps of LP Relaxations 146

7.3 Degree of Linearity 146

7.4 Semidefinite Relaxations 150

7.5 Context Independent Solvers 151

7.6 Difficulty of LOP Instances 153

7.7 Sparse Problems 155

7.8 A Simple Dual Heuristic 156

7.9 Future Research 158.

Notes:

Includes bibliographical references (pages 163-168) and index.

ISBN:

3642167284

9783642167287

OCLC:

668941895

Online:

Inhaltstext