ISBN: 354021398-8 TITLE: Muticriteria Optimization AUTHOR: Ehrgott TOC: Preface v Notation ix 1 Introduction 1 1.1 Optimization with Multiple Criteria 1 1.2 Decision Space and Objective (Criterion) Space 4 1.3 Notions of Optimality 7 1.4 Orders and Cones 8 1.5 Classification of Multicriteria Optimization Problems 16 1.6 Notes 19 Exercises 20 2 Efficiency and Nondominance 23 2.1 Efficient Solutions and Nondominated Points 23 2.2 Bounds an the Nondominated Set 33 2.3 Weakly and Strictly Efficient Solutions 38 2.4 Proper Efficiency and Proper Nondominance 50 2.5 Notes 59 Exercises 62 3 The Weighted Sum Method and Related Topics 65 3.1 Weighted Sum Scalarization and (Weak) Efficiency 68 3.2 Weighted Sum Scalarization and Proper Efficiency 71 3.3 Optimality Conditions 80 3.4 Connectedness of Efficient and Nondominated Sets 86 3.5 Notes 91 Exercises 93 4 Scalarization Techniques 97 4.1 The ?-Constraint Method 98 4.2 The Hybrid Method 101 4.3 The Elastic Constraint Method 102 4.4 Benson's Method 106 4.5 Compromise Solutions - Approximation of the Ideal Point 111 4.6 The Achievement Function Method 121 4.7 Notes 122 Exercises 124 5 Other Definitions of Optimality - Nonscalarizing Methods. 127 5.1 Lexicographic Optimality 128 5.2 Max-Ordering Optimality 132 5.3 Lexicographic Max-Ordering Optimization 135 5.4 Notes 146 Exercises 148 6 Introduction to Multicriteria Linear Programming 151 6.1 Notation and Definitions 152 6.2 The Simplex Method and Biobjective Linear Programs 160 Exercises 170 7 A Multiobjective Simplex Method 171 7.1 Algebra of Multiobjective Linear Programming 171 7.2 The Geometry of Multiobjective Linear Programming 184 7.3 Notes 193 Exercises 195 8 Multiobjective Combinatorial Optimization 197 8.1 Basics 198 8.2 Problems with Explicitely Given Feasible Set 209 8.3 Scalarization of Multiobjective Integer Programs 214 8.4 Notes 218 Exercises 220 9 Multiobjective Versions of Polynomially Solvable Problems 221 9.1 Algorithms for the Shortest Path Problem 221 9.2 The Minimum Spanning Tree Problem 236 9.3 Matroids 247 9.4 The Assignment Problem and the Two Phase Method 253 9.5 Notes 267 Exercises 269 10 Multiobjective Versions of Some NP-Hard Problems 271 10.1 The Knapsack Problem and Branch and Bound 271 10.2 The Travelling Salesperson Problem and Heuristics 279 10.3 Notes 288 Exercises 290 Bibliography 291 Author Index 313 Subject Index 319 END