Vangelis T. 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 Vangelis Th. PaschosPart I Complexity of Combinatioral Optimization Problems 1Chapter 1 Basic Concepts in Algorithms and Complexity Theory 3Vangelis Th. PaschosChapter 2 Randomized Complexity 21Jérémy BarbayPart II Classic Solution Methods 39Chapter 3 Branch-and-Bound Methods 41Irène Charon and Olivier HudryChapter 4 Dynamic Programming 71Bruno Escoffier and Olivier SpanjaardPart III Elements from Mathematical Programming 101Chapter 5 Mixed Integer Linear Programming Models for Combinatorial Optimization Problems 103Frédérico Della CroceChapter 6 Simplex Algorithms for Linear Programming 135Frédérico Della Croce and Andrea GrossoChapter 7 A Survey of Some Linear Programming Methods 157Pierre TollaChapter 8 Quadratic Optimization in 0-1 Variables 189Alain BillionnetChapter 9 Column Generation in Integar Linear Programming 235Irène Loiseau, Alberto Ceselli, Nelson Maculan and Matteo SalaniChapter 10 Polyhedral Approaches 261Ali Ridha MahjoubChapter 11 Constaint Programming 325Claude Le PapeGeneral Bibliography 339List of Authors 363Index 367Summary of Other Volumes in the Series 371