Hugendubel.info - Die B2B Online-Buchhandlung 

Merkliste
Die Merkliste ist leer.
Bitte warten - die Druckansicht der Seite wird vorbereitet.
Der Druckdialog öffnet sich, sobald die Seite vollständig geladen wurde.
Sollte die Druckvorschau unvollständig sein, bitte schliessen und "Erneut drucken" wählen.

The Linear Ordering Problem

E-BookPDF1 - PDF WatermarkE-Book
172 Seiten
Englisch
Springer Berlin Heidelbergerschienen am03.01.20112011
Faced with the challenge of solving the hard optimization problems that abound in the real world, existing methods often encounter great difficulties. Important applications in business, engineering or economics cannot be tackled by the techniques that have formed the predominant focus of academic research throughout the past three decades. Exact and heuristic approaches are dramatically changing our ability to solve problems of practical significance and are extending the frontier of problems that can be handled effectively. This monograph details state-of-the-art optimization methods, both exact and heuristic, for the LOP. The authors employ the LOP to illustrate contemporary optimization technologies as well as how to design successful implementations of exact and heuristic procedures. Therefore, they do not limit the scope of this book to the LOP, but on the contrary, provide the reader with the background and practical strategies in optimization to tackle different combinatorial problems.mehr
Verfügbare Formate
BuchKartoniert, Paperback
EUR90,94
E-BookPDF1 - PDF WatermarkE-Book
EUR90,94

Produkt

KlappentextFaced with the challenge of solving the hard optimization problems that abound in the real world, existing methods often encounter great difficulties. Important applications in business, engineering or economics cannot be tackled by the techniques that have formed the predominant focus of academic research throughout the past three decades. Exact and heuristic approaches are dramatically changing our ability to solve problems of practical significance and are extending the frontier of problems that can be handled effectively. This monograph details state-of-the-art optimization methods, both exact and heuristic, for the LOP. The authors employ the LOP to illustrate contemporary optimization technologies as well as how to design successful implementations of exact and heuristic procedures. Therefore, they do not limit the scope of this book to the LOP, but on the contrary, provide the reader with the background and practical strategies in optimization to tackle different combinatorial problems.
Details
Weitere ISBN/GTIN9783642167294
ProduktartE-Book
EinbandartE-Book
FormatPDF
Format Hinweis1 - PDF Watermark
FormatE107
Erscheinungsjahr2011
Erscheinungsdatum03.01.2011
Auflage2011
ReiheApplied Mathematical Sciences
Reihen-Nr.175
Seiten172 Seiten
SpracheEnglisch
IllustrationenXII, 172 p.
Artikel-Nr.1038500
Rubriken
Genre9200

Inhalt/Kritik

Inhaltsverzeichnis
1;The Linear Ordering Problem;3
1.1;Preface;7
1.2;Contents;9
1.3;Chapter 1 Introduction;13
1.3.1;1.1 Basic definitions;13
1.3.2;1.2 Applications of the Linear Ordering Problem;15
1.3.2.1;1.2.1 Equivalent Graph Problems;15
1.3.2.2;1.2.2 Related Graph Problems;16
1.3.2.3;1.2.3 Aggregation of Individual Preferences;16
1.3.2.4;1.2.4 Binary Choice Probabilities;17
1.3.2.5;1.2.5 Triangulation of Input-Output Tables;17
1.3.2.6;1.2.6 Optimal Weighted Ancestry Relationships;18
1.3.2.7;1.2.7 Ranking in Sports Tournaments;18
1.3.2.8;1.2.8 Corruption Perception;19
1.3.2.9;1.2.9 Crossing Minimization;20
1.3.2.10;1.2.10 Linear Ordering with Quadratic Objective Function;20
1.3.2.11;1.2.11 Scheduling with Precedences;21
1.3.2.12;1.2.12 Linear Ordering with Cumulative Costs;21
1.3.2.13;1.2.13 Coupled Task Problem;21
1.3.2.14;1.2.14 Target Visitation Problem;22
1.3.3;1.3 Benchmark Problems;22
1.3.3.1;1.3.1 Data Format;22
1.3.3.2;1.3.2 Input-Output Matrices;24
1.3.3.3;1.3.3 Randomly Generated Instances A (Type 1);25
1.3.3.4;1.3.4 Randomly Generated Instances A (Type 2);25
1.3.3.5;1.3.5 Randomly Generated Instances B;25
1.3.3.6;1.3.6 SGB Instances;25
1.3.3.7;1.3.7 Instances of Schiavinotto and Stützle;26
1.3.3.8;1.3.8 Instances of Mitchell and Borchers;26
1.3.3.9;1.3.9 Further Special Instances;26
1.4;Chapter 2 Heuristic Methods;28
1.4.1;2.1 Introduction;28
1.4.1.1;2.1.1 Assessing the Quality of Heuristics;30
1.4.2;2.2 Construction Heuristics;32
1.4.2.1;2.2.1 The Method of Chenery and Watanabe;32
1.4.2.2;2.2.2 Heuristics of Aujac & Masson;33
1.4.2.3;2.2.3 Heuristics of Becker;33
1.4.2.4;2.2.4 Best Insertion;34
1.4.3;2.3 Local Search;36
1.4.3.1;2.3.1 Insertion;37
1.4.3.2;2.3.2 The Heuristic of Chanas & Kobylanski;38
1.4.3.3;2.3.3 k-opt;38
1.4.3.4;2.3.4 Kernighan-Lin Type Improvement;38
1.4.3.5;2.3.5 Local Enumeration;40
1.4.4;2.4 Multi-Start Procedures;41
1.4.4.1;2.4.1 Variants of Multi-Start;42
1.4.4.2;2.4.2 Experiments with the LOP;44
1.5;Chapter 3 Meta-Heuristics;52
1.5.1;3.1 Introduction;52
1.5.2;3.2 GRASP;54
1.5.2.1;3.2.1 Construction Phase;55
1.5.2.2;3.2.2 Improvement Phase;59
1.5.3;3.3 Tabu Search;61
1.5.3.1;3.3.1 Short Term Memory;62
1.5.3.2;3.3.2 Long Term Memory;64
1.5.4;3.4 Simulated Annealing;67
1.5.5;3.5 Variable Neighborhood Search;71
1.5.5.1;3.5.1 Variable Neighborhood Descent;72
1.5.5.2;3.5.2 Restricted Variable Neighborhood Search;72
1.5.5.3;3.5.3 Basic Variable Neighborhood Search;73
1.5.5.4;3.5.4 Frequency Variable Neighborhood Search;73
1.5.5.5;3.5.5 Hybrid Variable Neighborhood Search;74
1.5.6;3.6 Scatter Search;77
1.5.6.1;3.6.1 Reference Set Creation;81
1.5.6.2;3.6.2 Reference Set Update;82
1.5.6.3;3.6.3 Reference Set Rebuild;84
1.5.7;3.7 Genetic Algorithms;88
1.5.8;3.8 Empirical Comparison;93
1.6;Chapter 4 Branch-and-Bound;96
1.6.1;4.1 Introduction;96
1.6.2;4.2 Branch-and-Bound with Partial Orderings;98
1.6.3;4.3 Lexicographic Search;100
1.6.4;4.4 Extension of Lexicographic Search to Branch-and-Bound;100
1.6.5;4.5 Branch-and-Bound with Lagrangian Relaxation;102
1.7;Chapter 5 Branch-and-Cut;106
1.7.1;5.1 Integer Programming;106
1.7.2;5.2 Cutting Plane Algorithms;108
1.7.3;5.3 Branch-and-Cut with 3-Dicycle Cuts;111
1.7.3.1;5.3.1 Solving the 3-Diycle Relaxation;112
1.7.3.2;5.3.2 An LP Based Heuristic;113
1.7.3.3;5.3.3 Computational Results with 3-Dicycles;113
1.7.4;5.4 Generation of Further Cuts;115
1.7.4.1;5.4.1 Chvátal-Gomory Cuts;115
1.7.4.2;5.4.2 Maximally Violated Mod-k Cuts;116
1.7.4.3;5.4.3 Mod-2 Cuts;118
1.7.5;5.5 Implementation of Branch-and-Cut;118
1.7.5.1;5.5.1 Initialization;119
1.7.5.2;5.5.2 Active Variables;120
1.7.5.3;5.5.3 Local Upper Bound;120
1.7.5.4;5.5.4 Branching;120
1.7.5.5;5.5.5 Fixing and Setting of Variables;120
1.7.5.6;5.5.6 Logical Implications;121
1.7.5.7;5.5.7 Selection of Nodes;121
1.7.5.8;5.5.8 Lower Bounds;122
1.7.5.9;5.5.9 Separation;122
1.7.5.10;5.5.10 Elimination of Constraints;122
1.7.5.11;5.5.11 Constraint Pool;122
1.7.5.12;5.5.12 Pricing;122
1.7.5.13;5.5.13 Infeasible LPs;123
1.7.5.14;5.5.14 Addition of Variables;123
1.7.6;5.6 Some Computational Results;124
1.8;Chapter 6 The Linear Ordering Polytope;128
1.8.1;6.1 Polyhedral Combinatorics and Basic Results;128
1.8.2;6.2 Facets of the Linear Ordering Polytope;131
1.8.3;6.3 Computation of Complete Descriptions;137
1.8.4;6.4 Differences between Facets;141
1.8.5;6.5 Separation of Small Facets;146
1.8.6;6.6 Computational Experiments with Small Facets;150
1.8.6.1;6.6.1 Comparison of Heuristics;150
1.8.6.2;6.6.2 Cutting Plane Selection;150
1.8.6.3;6.6.3 Number of Classes Taken into Account;151
1.8.6.4;6.6.4 Facet Selection;152
1.8.7;6.7 Local Cuts and Target Cuts;152
1.9;Chapter 7 Further Aspects;155
1.9.1;7.1 Approximative Algorithms;155
1.9.2;7.2 Integrality Gaps of LP Relaxations;156
1.9.3;7.3 Degree of Linearity;156
1.9.4;7.4 Semidefinite Relaxations;160
1.9.5;7.5 Context Independent Solvers;161
1.9.6;7.6 Difficulty of LOP Instances;163
1.9.7;7.7 Sparse Problems;165
1.9.8;7.8 A Simple Dual Heuristic;166
1.9.9;7.9 Future Research;168
1.10;References;172
1.11;Index;178mehr

Autor