Applications of Combinatorial Optimization, Volume 3

Vangelis Th. Paschos is Exceptional Professor of Computer Science and Combinatorial Optimization at the University Paris-Dauphine and chairman of the LAMSADE (Laboratory for the Modeling and the Analysis of Decision Aiding Systems). His research interests include the complexity theory, the theory of the polynomial approximation of NP-hard problems, the probabilistic combinatorial optimization, the on-line computation and the exact solution of NP-hard problems. He is the author of more than a hundred and fifty research papers. He is also member of the editorial board of several international scientific journals.

• Preface xiiiChapter 1. Airline Crew Pairing Optimization 1Laurent ALFANDARI and Anass NAGIH1.1. Introduction 11.2. Definition of the problem 21.3. Solution approaches 71.4. Solving the subproblem for column generation 111.5. Conclusion 211.6. Bibliography 22Chapter 2. The Task Allocation Problem 23Moaiz BEN DHAOU and Didier FAYARD2.1. Presentation 242.2. Definitions and modeling 242.3. Review of the main works 292.4. A little-studied model 382.5. Conclusion 432.6. Bibliography 43Chapter 3. A Comparison of Some Valid Inequality Generation Methods for General 0–1 Problems 49Pierre BONAMI and Michel MINOUX3.1. Introduction 493.2. Presentation of the various techniques tested 533.3. Computational results 673.4. Bibliography 70Chapter 4. Production Planning 73Nadia BRAUNER, Gerd FINKE and Maurice QUEYRANNE4.1. Introduction 734.2. Hierarchical planning 744.3. Strategic planning and productive system design 754.4. Tactical planning and inventory management 774.5. Operations planning and scheduling 904.6. Conclusion and perspectives 1044.7. Bibliography 105Chapter 5. Operations Research and Goods Transportation 111Teodor Gabriel CRAINIC and Frédéric SEMET5.1. Introduction 1115.2. Goods transport systems 1135.3. Systems design 1155.4. Long-distance transport 1225.5. Vehicle routing problems 1375.6. Exact models and methods for the VRP 1395.7. Heuristic methods for the VRP 1475.8. Conclusion 1605.9. Appendix: metaheuristics 1615.10. Bibliography 164Chapter 6. Optimization Models for Transportation Systems Planning 177Teodor Gabriel CRAINIC and Michael FLORIAN6.1. Introduction 1776.2. Spatial interaction models 1786.3. Traffic assignment models and methods 1816.4. Transit route choice models 1936.5. Strategic planning of multimodal systems 1976.6. Conclusion 2046.7. Bibliography 204Chapter 7. A Model for the Design of a Minimum-cost Telecommunications Network 209Marc DEMANGE, Cécile MURAT, Vangelis Th. PASCHOS and Sophie TOULOUSE7.1. Introduction 2097.2. Minimum cost network construction 2107.3. Mathematical model, general context 2137.4. Proposed algorithm 2167.5. Critical points 2207.6. Conclusion 2237.7. Bibliography 223Chapter 8. Parallel Combinatorial Optimization 225Van-Dat CUNG, Bertrand LE CUN and Catherine ROUCAIROL8.1. Impact of parallelism in combinatorial optimization 2258.2. Parallel metaheuristics 2268.3. Parallelizing tree exploration in exact methods 2358.4. Conclusion 2478.5. Bibliography 248Chapter 9. Network Design Problems: Fundamental Methods 253Alain Quilliot9.1. Introduction 2539.2. The main mathematical and algorithmic tools for network design 2589.3. Models and problems 2759.4. The STEINER-EXTENDED problem 2809.5. Conclusion 2819.6 Bibliography 281Chapter 10. Network Design Problems: Models and Applications 291Alain Quilliot10.1. Introduction 29110.2. Models and location problems 29310.3. Routing models for telecommunications 29810.4. The design or dimensioning problem in telecommunications 30110.5. Coupled flows and multiflows for transport and production 30610.6. A mixed network pricing model 31410.7. Conclusion 31910.8. Bibliography 319Chapter 11. Multicriteria Task Allocation to Heterogenous Processors with Capacity and Mutual Exclusion Constraints 327Bernard ROY and Roman SLOWINSKI11.1. Introduction and formulation of the problem 32811.2. Modeling the set of feasible assignments 33111.3. The concept of a blocking configuration and analysis of the unblocking means 33411.4. The multicriteria assignment problem 34611.5. Exploring a set of feasible non-dominated assignments in the plane g2 × g3 34811.6. Numerical example 35711.7. Conclusion 36311.8. Bibliography 364List of Authors 365Index 369Summary of Other Volumes in the Series 373