Combinatorial optimization is a multidisciplinary scientific area, lying in the interface of three major scientific domains: mathematics, theoretical computer science and management. The three volumes of the Combinatorial Optimization series aim to cover a wide range of topics in this area. These topics also deal with fundamental notions and approaches as with several classical applications of combinatorial optimization. Concepts of Combinatorial Optimization, is divided into three parts: - On the complexity of combinatorial optimization problems, presenting basics about worst-case and randomized complexity; - Classical solution methods, presenting the two most-known methods for solving hard combinatorial optimization problems, that are Branch-and-Bound and Dynamic Programming; - Elements from mathematical programming, presenting fundamentals from mathematical programming based methods that are in the heart of Operations Research since the origins of this field.

Combinatorial optimization is a multidisciplinary scientific arealying in the interface of three major scientific domains:mathematics, theoretical computer science and management. Thethree volumes of the Combinatorial Optimization series aim to covera wide range of topics in this area. These topics also dealwith fundamental notions and approaches as with several classicalapplications of combinatorial optimization.Concepts of Combinatorial Optimization, is divided intothree parts: On the complexity of combinatorial optimization problemspresenting basics about worst-case and randomized complexity; Classical solution methods, presenting the two most-known methodsfor solving hard combinatorial optimization problems, that areBranch-and-Bound and Dynamic Programming; Elements from mathematical programming, presenting fundamentalsfrom mathematical programming based methods that are in the heartof Operations Research since the origins of this field.

Preface xiiiChapter 1 Airline Crew Pairing Optimization 1Laurent Alfandari and Anass NagihChapter 2 The Task Allocation Problem 23Moaiz Ben Dhaou and Didier FayardChapter 3 A Comparison of Some Valid Inequality GenerationMethods for General 0-1 Problems 49Pierre Bonami and Michel MinouxChapter 4 Production Planning 73Nadia Brauner, Gerd Finke and Maurice QueyranneChapter 5 Operations Research and Goods Transportation 111Teodor Gabriel Crainic and Frédéric SemetChapter 6 Optimization Models for Transportation SystemsPlanning 177Teodor Gabriel Crainic and Michael FlorianChapter 7 A Model for the Design of a Minimum-costTelecomminications Network 209Marc Demange, Cécile Murat, Vangelis Th. Paschos and SophieToulouseChapter 8 Parallel Combinatorial Optimization 225Van-Dat Cung, Bertrand Le Cun and Catherine RoucairolChapter 9 Network Design Problems: Fundamental Methods 253Alain QuilliotChapter 10 Network Design Problems: Models and Applications291Alain QuilliotChapter 11 Multicriteria Task Allocation to HeterogenousProcessors with Capacity and Mutual Exclusion Constraints 327Bernard Roy and Roman SlowinskiGeneral Bibliography 365List of Authors 401Index 405Summary of Other Volumes in the Series 409