Combinatorial optimization is a multidisciplinary scientific area,lying 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 problems,presenting 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.
Auflage
Sprache
Verlagsort
Verlagsgruppe
Dateigröße
ISBN-13
978-1-119-01518-5 (9781119015185)
Schweitzer Klassifikation
Preface xiii
Vangelis Th. Paschos
Part I Complexity of Combinatioral Optimization Problems1
Chapter 1 Basic Concepts in Algorithms and Complexity Theory3
Vangelis Th. Paschos
Chapter 2 Randomized Complexity 21
Jérémy Barbay
Part II Classic Solution Methods 39
Chapter 3 Branch-and-Bound Methods 41
Irène Charon and Olivier Hudry
Chapter 4 Dynamic Programming 71
Bruno Escoffier and Olivier Spanjaard
Part III Elements from Mathematical Programming 101
Chapter 5 Mixed Integer Linear Programming Models forCombinatorial Optimization Problems 103
Frédérico Della Croce
Chapter 6 Simplex Algorithms for Linear Programming 135
Frédérico Della Croce and Andrea Grosso
Chapter 7 A Survey of Some Linear Programming Methods 157
Pierre Tolla
Chapter 8 Quadratic Optimization in 0-1 Variables 189
Alain Billionnet
Chapter 9 Column Generation in Integar Linear Programming235
Irène Loiseau, Alberto Ceselli, Nelson Maculan and MatteoSalani
Chapter 10 Polyhedral Approaches 261
Ali Ridha Mahjoub
Chapter 11 Constaint Programming 325
Claude Le Pape
General Bibliography 339
List of Authors 363
Index 367
Summary of Other Volumes in the Series 371
