The Linear Ordering Problem (eBook)

The Linear Ordering Problem 3
Preface 7
Contents 9
Chapter 1 Introduction 13
1.1 Basic definitions 13
1.2 Applications of the Linear Ordering Problem 15
1.2.1 Equivalent Graph Problems 15
1.2.2 Related Graph Problems 16
1.2.3 Aggregation of Individual Preferences 16
1.2.4 Binary Choice Probabilities 17
1.2.5 Triangulation of Input-Output Tables 17
1.2.6 Optimal Weighted Ancestry Relationships 18
1.2.7 Ranking in Sports Tournaments 18
1.2.8 Corruption Perception 19
1.2.9 Crossing Minimization 20
1.2.10 Linear Ordering with Quadratic Objective Function 20
1.2.11 Scheduling with Precedences 21
1.2.12 Linear Ordering with Cumulative Costs 21
1.2.13 Coupled Task Problem 21
1.2.14 Target Visitation Problem 22
1.3 Benchmark Problems 22
1.3.1 Data Format 22
1.3.2 Input-Output Matrices 24
1.3.3 Randomly Generated Instances A (Type 1) 25
1.3.4 Randomly Generated Instances A (Type 2) 25
1.3.5 Randomly Generated Instances B 25
1.3.6 SGB Instances 25
1.3.7 Instances of Schiavinotto and Stützle 26
1.3.8 Instances of Mitchell and Borchers 26
1.3.9 Further Special Instances 26
Chapter 2 Heuristic Methods 28
2.1 Introduction 28
2.1.1 Assessing the Quality of Heuristics 30
2.2 Construction Heuristics 32
2.2.1 The Method of Chenery and Watanabe 32
2.2.2 Heuristics of Aujac & Masson
2.2.3 Heuristics of Becker 33
2.2.4 Best Insertion 34
2.3 Local Search 36
2.3.1 Insertion 37
2.3.2 The Heuristic of Chanas & Kobylanski
2.3.3 k-opt 38
2.3.4 Kernighan-Lin Type Improvement 38
2.3.5 Local Enumeration 40
2.4 Multi-Start Procedures 41
2.4.1 Variants of Multi-Start 42
2.4.2 Experiments with the LOP 44
Chapter 3 Meta-Heuristics 52
3.1 Introduction 52
3.2 GRASP 54
3.2.1 Construction Phase 55
3.2.2 Improvement Phase 59
3.3 Tabu Search 61
3.3.1 Short Term Memory 62
3.3.2 Long Term Memory 64
3.4 Simulated Annealing 67
3.5 Variable Neighborhood Search 71
3.5.1 Variable Neighborhood Descent 72
3.5.2 Restricted Variable Neighborhood Search 72
3.5.3 Basic Variable Neighborhood Search 73
3.5.4 Frequency Variable Neighborhood Search 73
3.5.5 Hybrid Variable Neighborhood Search 74
3.6 Scatter Search 77
3.6.1 Reference Set Creation 81
3.6.2 Reference Set Update 82
3.6.3 Reference Set Rebuild 84
3.7 Genetic Algorithms 88
3.8 Empirical Comparison 93
Chapter 4 Branch-and-Bound 96
4.1 Introduction 96
4.2 Branch-and-Bound with Partial Orderings 98
4.3 Lexicographic Search 100
4.4 Extension of Lexicographic Search to Branch-and-Bound 100
4.5 Branch-and-Bound with Lagrangian Relaxation 102
Chapter 5 Branch-and-Cut 106
5.1 Integer Programming 106
5.2 Cutting Plane Algorithms 108
5.3 Branch-and-Cut with 3-Dicycle Cuts 111
5.3.1 Solving the 3-Diycle Relaxation 112
5.3.2 An LP Based Heuristic 113
5.3.3 Computational Results with 3-Dicycles 113
5.4 Generation of Further Cuts 115
5.4.1 Chvátal-Gomory Cuts 115
5.4.2 Maximally Violated Mod-k Cuts 116
5.4.3 Mod-2 Cuts 118
5.5 Implementation of Branch-and-Cut 118
5.5.1 Initialization 119
5.5.2 Active Variables 120
5.5.3 Local Upper Bound 120
5.5.4 Branching 120
5.5.5 Fixing and Setting of Variables 120
5.5.6 Logical Implications 121
5.5.7 Selection of Nodes 121
5.5.8 Lower Bounds 122
5.5.9 Separation 122
5.5.10 Elimination of Constraints 122
5.5.11 Constraint Pool 122
5.5.12 Pricing 122
5.5.13 Infeasible LPs 123
5.5.14 Addition of Variables 123
5.6 Some Computational Results 124
Chapter 6 The Linear Ordering Polytope 128
6.1 Polyhedral Combinatorics and Basic Results 128
6.2 Facets of the Linear Ordering Polytope 131
6.3 Computation of Complete Descriptions 137
6.4 Differences between Facets 141
6.5 Separation of Small Facets 146
6.6 Computational Experiments with Small Facets 150
6.6.1 Comparison of Heuristics 150
6.6.2 Cutting Plane Selection 150
6.6.3 Number of Classes Taken into Account 151
6.6.4 Facet Selection 152
6.7 Local Cuts and Target Cuts 152
Chapter 7 Further Aspects 155
7.1 Approximative Algorithms 155
7.2 Integrality Gaps of LP Relaxations 156
7.3 Degree of Linearity 156
7.4 Semidefinite Relaxations 160
7.5 Context Independent Solvers 161
7.6 Difficulty of LOP Instances 163
7.7 Sparse Problems 165
7.8 A Simple Dual Heuristic 166
7.9 Future Research 168
References 172
Index 178