Concepts of Combinatorial Optimization
2nd Edition
Published on 29. July 2014
Book
Hardback
408 pages
978-1-84821-656-3 (ISBN)
Description
Combinatorial optimization is a multidisciplinary scientific area, lying in the interface of three major scientific domains: mathematics, theoretical computer science and management. The three volumes of the Combinatorial Optimization series aim 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, presenting basics about worst-case and randomized complexity;
- Classical solution methods, presenting the two most-known methods for solving hard combinatorial optimization problems, that are Branch-and-Bound and Dynamic Programming;
- Elements from mathematical programming, presenting fundamentals from mathematical programming based methods that are in the heart of Operations Research since the origins of this field.
Concepts of Combinatorial Optimization, is divided into three parts:
- On the complexity of combinatorial optimization problems, presenting basics about worst-case and randomized complexity;
- Classical solution methods, presenting the two most-known methods for solving hard combinatorial optimization problems, that are Branch-and-Bound and Dynamic Programming;
- Elements from mathematical programming, presenting fundamentals from mathematical programming based methods that are in the heart of Operations Research since the origins of this field.
More details
Edition
2nd edition
Language
English
Place of publication
London
United Kingdom
Target group
College/higher education
Professional and scholarly
Product notice
sewn/stitched
Cloth over boards
Dimensions
Height: 240 mm
Width: 161 mm
Thickness: 26 mm
Weight
762 gr
ISBN-13
978-1-84821-656-3 (9781848216563)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Other editions
Additional editions
Vangelis Th. Paschos
Concepts of Combinatorial Optimization
E-Book
08/2014
2nd Edition
Wiley-ISTE
€149.99
Available for download
Vangelis Th. Paschos
Concepts of Combinatorial Optimization
E-Book
08/2014
2nd Edition
Wiley-ISTE
€149.99
Available for download
Person
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.
Content
Preface xiii Vangelis Th. Paschos
Part I Complexity of Combinatioral Optimization Problems 1
Chapter 1 Basic Concepts in Algorithms and Complexity Theory 3
Vangelis Th. Paschos
Chapter 2 Randomized Complexity 21
Jeremy Barbay
Part II Classic Solution Methods 39
Chapter 3 Branch-and-Bound Methods 41
Irene 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 for Combinatorial Optimization Problems 103
Frederico Della Croce
Chapter 6 Simplex Algorithms for Linear Programming 135
Frederico 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 Programming 235
Irene Loiseau, Alberto Ceselli, Nelson Maculan and Matteo Salani
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
Part I Complexity of Combinatioral Optimization Problems 1
Chapter 1 Basic Concepts in Algorithms and Complexity Theory 3
Vangelis Th. Paschos
Chapter 2 Randomized Complexity 21
Jeremy Barbay
Part II Classic Solution Methods 39
Chapter 3 Branch-and-Bound Methods 41
Irene 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 for Combinatorial Optimization Problems 103
Frederico Della Croce
Chapter 6 Simplex Algorithms for Linear Programming 135
Frederico 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 Programming 235
Irene Loiseau, Alberto Ceselli, Nelson Maculan and Matteo Salani
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