Applications of Combinatorial Optimization (eBook)

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

Preface xiii

Chapter 1 Airline Crew Pairing Optimization 1

Laurent Alfandari and Anass Nagih

Chapter 2 The Task Allocation Problem 23

Moaiz Ben Dhaou and Didier Fayard

Chapter 3 A Comparison of Some Valid Inequality Generation
Methods for General 0-1 Problems 49

Pierre Bonami and Michel Minoux

Chapter 4 Production Planning 73

Nadia Brauner, Gerd Finke and Maurice Queyranne

Chapter 5 Operations Research and Goods Transportation 111

Teodor Gabriel Crainic and Frédéric Semet

Chapter 6 Optimization Models for Transportation Systems
Planning 177

Teodor Gabriel Crainic and Michael Florian

Chapter 7 A Model for the Design of a Minimum-cost
Telecomminications Network 209

Marc Demange, Cécile Murat, Vangelis Th. Paschos and Sophie
Toulouse

Chapter 8 Parallel Combinatorial Optimization 225

Van-Dat Cung, Bertrand Le Cun and Catherine Roucairol

Chapter 9 Network Design Problems: Fundamental Methods 253

Alain Quilliot

Chapter 10 Network Design Problems: Models and Applications
291

Alain Quilliot

Chapter 11 Multicriteria Task Allocation to Heterogenous
Processors with Capacity and Mutual Exclusion Constraints 327

Bernard Roy and Roman Slowinski

General Bibliography 365

List of Authors 401

Index 405

Summary of Other Volumes in the Series 409