Merkzettel Warenkorb
Produktbild: Combinatorial Optimization / Concepts of Combinatorial Optimization

Combinatorial Optimization / Concepts of Combinatorial Optimization

227,99 €

inkl. gesetzl. MwSt., Versandkostenfrei

Lieferung nach Hause

Beschreibung

Produktdetails

Einband

Gebundene Ausgabe

Erscheinungsdatum

23.08.2010

Herausgeber

Vangelis Th. Paschos

Verlag

John Wiley & Sons Inc

Seitenzahl

380

Maße (L/B/H)

24/16/2,8 cm

Gewicht

700 g

Auflage

1. Auflage

Sprache

Englisch

ISBN

978-1-84821-147-6

Beschreibung

Produktdetails

Einband

Gebundene Ausgabe

Erscheinungsdatum

23.08.2010

Herausgeber

Vangelis Th. Paschos

Verlag

John Wiley & Sons Inc

Seitenzahl

380

Maße (L/B/H)

24/16/2,8 cm

Gewicht

700 g

Auflage

1. Auflage

Sprache

Englisch

ISBN

978-1-84821-147-6

Herstelleradresse

Libri GmbH
Europaallee 1
36244 Bad Hersfeld
DE

Email: gpsr@libri.de

Kundinnen und Kunden meinen

0 Bewertungen

Informationen zu Bewertungen

Zur Abgabe einer Bewertung ist eine Anmeldung im Konto notwendig. Die Authentizität der Bewertungen wird von uns nicht überprüft. Wir behalten uns vor, Bewertungstexte, die unseren Richtlinien widersprechen, entsprechend zu kürzen oder zu löschen.

Die Bewertungen sind nach Format, Anzahl Sterne und Datum sortiert.

Verfassen Sie die erste Bewertung zu diesem Artikel

Helfen Sie anderen Kund*innen durch Ihre Meinung

Kundinnen und Kunden meinen

0 Bewertungen filtern
Die Leseprobe wird geladen.
  • Produktbild: Combinatorial Optimization / Concepts of Combinatorial Optimization

  • 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. NP-completeness 10

    1.6. Two examples of NP-complete problems 13

    1.7. A few words on strong and weak NP-completeness 16

    1.8. A few other well-known 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. Branch-and-Bound Methods 41
    Irène CHARON and Olivier HUDRY

    3.1. Introduction 41

    3.2. Branch-and-bound 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 pseudo-costs 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. Pseudo-Boolean functions and set functions 190

    8.3. Formalization using pseudo-Boolean functions 191

    8.4. Quadratic pseudo-Boolean 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 pseudo-Boolean 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. Cutting-plane 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