Concepts of Combinatorial Optimization, Volume 1ISBN: 9781848211476
368 pages
August 2010, WileyISTE

Description
The three volumes of the Combinatorial Optimization series aims 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, that presents basics about worstcase and randomized complexity;
 Classical solution methods, that presents the two mostknown methods for solving hard combinatorial optimization problems, that are BranchandBound and Dynamic Programming;
 Elements from mathematical programming, that presents fundamentals from mathematical programming based methods that are in the heart of Operations Research since the origins of this field.
Table of Contents
Preface xiii
Vangelis Th. PASCHOS
PART I. COMPLEXITY OF COMBINATORIAL OPTIMIZATION PROBLEMS 1
Chapter 1. Basic Concepts in Algorithms and Complexity Theory
3
Vangelis Th. PASCHOS
1.1. Algorithmic complexity 3
1.2. Problem complexity 4
1.3. The classes P, NP and NPO 7
1.4. Karp and Turing reductions 9
1.5. NPcompleteness 10
1.6. Two examples of NPcomplete problems 13
1.7. A few words on strong and weak NPcompleteness 16
1.8. A few other wellknown complexity classes 17
1.9. Bibliography 18
Chapter 2. Randomized Complexity 21
Jérémy BARBAY
2.1. Deterministic and probabilistic algorithms 22
2.2. Lower bound technique 28
2.3. Elementary intersection problem 35
2.4. Conclusion 37
2.5 Bibliography 37
PART II. CLASSICAL SOLUTION METHODS 39
Chapter 3. BranchandBound Methods 41
Irène CHARON and Olivier HUDRY
3.1. Introduction 41
3.2. Branchandbound method principles 43
3.3. A detailed example: the binary knapsack problem 54
3.4. Conclusion 67
3.5. Bibliography 68
Chapter 4. Dynamic Programming 71
Bruno ESCOFFIER and Olivier SPANJAARD
4.1. Introduction 71
4.2. A first example: crossing the bridge 72
4.3. Formalization 75
4.4. Some other examples 79
4.5. Solution 83
4.6. Solution of the examples 88
4.7. A few extensions 90
4.8. Conclusion 98
4.9. Bibliography 98
PART III. ELEMENTS FROM MATHEMATICAL PROGRAMMING 101
Chapter 5. Mixed Integer Linear Programming Models for
Combinatorial Optimization Problems 103
Frédérico DELLA CROCE
5.1. Introduction 103
5.2. General modeling techniques 111
5.3. More advanced MILP models 117
5.4. Conclusions 132
5.5. Bibliography 133
Chapter 6. Simplex Algorithms for Linear Programming
135
Frédérico DELLA CROCE and Andrea GROSSO
6.1. Introduction 135
6.2. Primal and dual programs 135
6.3. The primal simplex method 140
6.4. Bland’s rule 145
6.5. Simplex methods for the dual problem 147
6.6. Using reduced costs and pseudocosts for integer programming 152
6.7. Bibliography 155
Chapter 7. A Survey of some Linear Programming Methods
157
Pierre TOLLA
7.1. Introduction 157
7.2. Dantzig’s simplex method 158
7.3. Duality 162
7.4. Khachiyan’s algorithm 162
7.5. Interior methods 165
7.6. Conclusion 186
7.7. Bibliography 187
Chapter 8. Quadratic Optimization in 0–1 Variables
189
Alain BILLIONNET
8.1. Introduction 189
8.2. PseudoBoolean functions and set functions 190
8.3. Formalization using pseudoBoolean functions 191
8.4. Quadratic pseudoBoolean functions (qpBf) 192
8.5. Integer optimum and continuous optimum of qpBfs 194
8.6. Derandomization 195
8.7. Posiforms and quadratic posiforms 196
8.8. Optimizing a qpBf: special cases and polynomial cases 198
8.9. Reductions, relaxations, linearizations, bound calculation and persistence 200
8.10. Local optimum 206
8.11. Exact algorithms and heuristic methods for optimizing qpBfs 208
8.12. Approximation algorithms 211
8.13. Optimizing a quadratic pseudoBoolean function with linear constraints 213
8.14. Linearization, convexification and Lagrangian relaxation for optimizing a qpBf with linear constraints 220
8.15. Approximation algorithms for optimizing a qpBf with linear constraints 223
8.16. Bibliography 224
Chapter 9. Column Generation in Integer Linear Programming
235
Irène LOISEAU, Alberto CESELLI, Nelson MACULAN and Matteo
SALANI
9.1. Introduction 235
9.2. A column generation method for a bounded variable linear programming problem 236
9.3. An inequality to eliminate the generation of a 0–1 column 238
9.4. Formulations for an integer linear program 240
9.5. Solving an integer linear program using column generation 243
9.6. Applications 247
9.7. Bibliography 255
Chapter 10. Polyhedral Approaches 261
Ali Ridha MAHJOUB
10.1. Introduction 261
10.2. Polyhedra, faces and facets 265
10.3. Combinatorial optimization and linear programming 276
10.4. Proof techniques 282
10.5. Integer polyhedra and min–max relations 293
10.6. Cuttingplane method 301
10.7. The maximum cut problem 308
10.8. The survivable network design problem 313
10.9. Conclusion 319
10.10. Bibliography 320
Chapter 11. Constraint Programming 325
Claude LE PAPE
11.1. Introduction 325
11.2. Problem definition 327
11.3. Decision operators 328
11.4. Propagation 330
11.5. Heuristics 333
11.6. Conclusion 336
11.7. Bibliography 336
List of Authors 339
Index 343
Summary of Other Volumes in the Series 347