Concepts of Combinatorial Optimization, Volume 1

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 xiiiVangelis Th. PASCHOSPART I. COMPLEXITY OF COMBINATORIAL OPTIMIZATION PROBLEMS 1Chapter 1. Basic Concepts in Algorithms and Complexity Theory 3Vangelis Th. PASCHOS1.1. Algorithmic complexity 31.2. Problem complexity 41.3. The classes P, NP and NPO 71.4. Karp and Turing reductions 91.5. NP-completeness 101.6. Two examples of NP-complete problems 131.7. A few words on strong and weak NP-completeness 161.8. A few other well-known complexity classes 171.9. Bibliography 18Chapter 2. Randomized Complexity 21Jérémy BARBAY2.1. Deterministic and probabilistic algorithms 222.2. Lower bound technique 282.3. Elementary intersection problem 352.4. Conclusion 372.5 Bibliography 37PART II. CLASSICAL SOLUTION METHODS 39Chapter 3. Branch-and-Bound Methods 41Irène CHARON and Olivier HUDRY3.1. Introduction 413.2. Branch-and-bound method principles 433.3. A detailed example: the binary knapsack problem 543.4. Conclusion 673.5. Bibliography 68Chapter 4. Dynamic Programming 71Bruno ESCOFFIER and Olivier SPANJAARD4.1. Introduction 714.2. A first example: crossing the bridge 724.3. Formalization 754.4. Some other examples 794.5. Solution 834.6. Solution of the examples 884.7. A few extensions 904.8. Conclusion 984.9. Bibliography 98PART III. ELEMENTS FROM MATHEMATICAL PROGRAMMING 101Chapter 5. Mixed Integer Linear Programming Models for Combinatorial Optimization Problems 103Frédérico DELLA CROCE5.1. Introduction 1035.2. General modeling techniques 1115.3. More advanced MILP models 1175.4. Conclusions 1325.5. Bibliography 133Chapter 6. Simplex Algorithms for Linear Programming 135Frédérico DELLA CROCE and Andrea GROSSO6.1. Introduction 1356.2. Primal and dual programs 1356.3. The primal simplex method 1406.4. Bland’s rule 1456.5. Simplex methods for the dual problem 1476.6. Using reduced costs and pseudo-costs for integer programming 1526.7. Bibliography 155Chapter 7. A Survey of some Linear Programming Methods 157Pierre TOLLA7.1. Introduction 1577.2. Dantzig’s simplex method 1587.3. Duality 1627.4. Khachiyan’s algorithm 1627.5. Interior methods 1657.6. Conclusion 1867.7. Bibliography 187Chapter 8. Quadratic Optimization in 0–1 Variables 189Alain BILLIONNET8.1. Introduction 1898.2. Pseudo-Boolean functions and set functions 1908.3. Formalization using pseudo-Boolean functions 1918.4. Quadratic pseudo-Boolean functions (qpBf) 1928.5. Integer optimum and continuous optimum of qpBfs 1948.6. Derandomization 1958.7. Posiforms and quadratic posiforms 1968.8. Optimizing a qpBf: special cases and polynomial cases 1988.9. Reductions, relaxations, linearizations, bound calculation and persistence 2008.10. Local optimum 2068.11. Exact algorithms and heuristic methods for optimizing qpBfs 2088.12. Approximation algorithms 2118.13. Optimizing a quadratic pseudo-Boolean function with linear constraints 2138.14. Linearization, convexification and Lagrangian relaxation for optimizing a qpBf with linear constraints 2208.15. -Approximation algorithms for optimizing a qpBf with linear constraints 2238.16. Bibliography 224Chapter 9. Column Generation in Integer Linear Programming 235Irène LOISEAU, Alberto CESELLI, Nelson MACULAN and Matteo SALANI9.1. Introduction 2359.2. A column generation method for a bounded variable linear programming problem 2369.3. An inequality to eliminate the generation of a 0–1 column 2389.4. Formulations for an integer linear program 2409.5. Solving an integer linear program using column generation 2439.6. Applications 2479.7. Bibliography 255Chapter 10. Polyhedral Approaches 261Ali Ridha MAHJOUB10.1. Introduction 26110.2. Polyhedra, faces and facets 26510.3. Combinatorial optimization and linear programming 27610.4. Proof techniques 28210.5. Integer polyhedra and min–max relations 29310.6. Cutting-plane method 30110.7. The maximum cut problem 30810.8. The survivable network design problem 31310.9. Conclusion 31910.10. Bibliography 320Chapter 11. Constraint Programming 325Claude LE PAPE11.1. Introduction 32511.2. Problem definition 32711.3. Decision operators 32811.4. Propagation 33011.5. Heuristics 33311.6. Conclusion 33611.7. Bibliography 336List of Authors 339Index 343Summary of Other Volumes in the Series 347