Info
- Utilizzare la checkbox di selezione a fianco di ciascun documento per attivare le funzionalità di stampa, invio email, download nei formati disponibili del (i) record.
Discrete optimization / / edited by K. Aardal, G.L. Nemhauser and R. Weismantel
| Discrete optimization / / edited by K. Aardal, G.L. Nemhauser and R. Weismantel |
| Edizione | [1st ed.] |
| Pubbl/distr/stampa | Amsterdam ; ; Boston, : Elsevier, 2005 |
| Descrizione fisica | 1 online resource (621 p.) |
| Disciplina | 519.6 |
| Altri autori (Persone) |
AardalK (Karen)
NemhauserGeorge L WeismantelRobert |
| Collana | Handbooks in operations research and management science |
| Soggetto topico |
Mathematical optimization
Integer programming |
| ISBN |
1-280-63811-7
9786610638116 0-08-045921-8 9780444515070 |
| Formato | Materiale a stampa  |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Handbooks in Operations Research and Management Science; Contents; Preface; Chapter 1 On the History of Combinatorial Optimization (Till 1960); 1 Introduction; 2 The assignment problem; 3 The transportation problem; 4 Menger's theorem and maximum flow; 5 Shortest spanning tree; 6 Shortest path; 7 The traveling salesman problem; References; Chapter 2 Computational Integer Programming and Cutting Planes; 1 Introduction; 2 Formulations and structure analysis; 3 Relaxations; 4 Branch-and-bound strategies; 5 Final remarks; References; Chapter 3 The Structure of Group Relaxations; 1 Introduction
2 Group relaxations3 Associated sets; 4 Arithmetic degree; 5 The Chain theorem; 6 Gomory integer programs; 7 Gomory families and Hilbert bases; 8 Algebraic notes; References; Chapter 4 Integer Programming, Lattices, and Results in Fixed Dimension; 1 Introduction; 2 Notation and basic definitions; 3 Lattice basis reduction; 4 Algorithms for the integer feasibility problem in fixed dimension; 5 Algorithms for the integer optimization problem in fixed dimension; 6 Using lattices to reformulate the problem; 7 Integer hulls and cutting plane closures in fixed dimension; References Chapter 5 Primal Integer Programming1 Introduction; 2 Efficient primal algorithms; 3 Irreducibility and integral generating sets; 4 General integer programming algorithms; 5 Combinatorial optimization; References; Chapter 6 Balanced Matrices; 1 Introduction; 2 Integral polytopes; 3 Bicoloring; 4 Total dual integrality; 5 k-Balanced matrices; 6 Perfection and idealness; 7 Propositional logic; 8 Nonlinear 0, 1 optimization; 9 Balanced hypergraphs; 10 Bipartite representation; 11 Totally balanced 0,1 matrices; 12 Signing 0, 1 matrices; 13 Truemper's theorem; 14 Decomposition theorem 15 Recognition algorithm16 More decomposition theorems; 17 Some conjectures and open questions; References; Chapter 7 Submodular Function Minimization; 1 Introduction; 2 Building blocks for SFM algorithms; 3 The SFM algorithms; 4 Comparing and contrasting the algorithms; 5 Solvable extensions of SFM; 6 Future directions for SFM algorithms; References; Chapter 8 Semide.nite Programming and Integer Programming; 1 Introduction; 2 Semidefinite programming: duality, algorithms, complexity, and geometry; 3 Semidefinite programming and integer 0/1 programming 4 Semidefinite relaxation for the maximum stable set problem5 Semidefinite relaxation for the max-cut problem; 6 Applications of semidefinite programming and the rounding hyperplane technique to other combinatorial optimization problems; 7 Further Topics; 8 Semidefinite programming and the quadratic assignment problem; 9 Epilogue: semidefinite programming and algebraic connectivity; 10 Appendix: surveys, books and software; References; Chapter 9 Algorithms for Stochastic Mixed-Integer Programming Models; 1 Introduction; 2 Preliminaries for decomposition algorithms 3 Decomposition algorithms for two-stage SMIP: stagewise decomposition |
| Record Nr. | UNINA-9910583070303321 |
| Amsterdam ; ; Boston, : Elsevier, 2005 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Integer and Combinatorial Optimization [[electronic resource]]
| Integer and Combinatorial Optimization [[electronic resource]] |
| Autore | Wolsey Laurence A |
| Pubbl/distr/stampa | Hoboken, : Wiley, 2014 |
| Descrizione fisica | 1 online resource (783 p.) |
| Disciplina | 519.7/7 |
| Altri autori (Persone) | NemhauserGeorge L |
| Collana | Wiley Series in Discrete Mathematics and Optimization |
| Soggetto topico |
Combinatorial optimization
Integer programming Mathematical optimization Civil & Environmental Engineering Engineering & Applied Sciences Operations Research |
| ISBN |
1-118-62686-9
1-118-62737-7 1-118-62725-3 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Cover ; Title Page ; Copyright ; Preface ; Contents ; Part I: Foundations ; I.1 The Scope of Integer and Combinatorial Optimization ; 1. Introduction ; 2. Modeling with Binary Variables I: Knapsack, Assignmentand Matching, Covering, Packing and Partitioning ; The 0-1 Knapsack Problem ; The Assignment and Matching Problems ; Set-covering, Set-packing, and Set-partitioning Problems ; 3. Modeling with Binary Variables II: Facility Location, Fixed-charge Network Flow, and Traveling Salesman ; Facility Location Problems ; The Fixed-charge Network Flow Problem ; The Traveling Salesman Problem
4. Modeling with Binary Variables III: Nonlinear Functions and Disjunctive ConstraintsPiecewise Linear Functions ; Disjunctive Constraints ; A Scheduling Problem ; 5. Choices in Model Formulation ; 6. Preprocessing ; Tightening Bounds ; Adding Logical Inequalities, Fixing Variables, and Removing Redundant Constraints ; 7. Notes ; Section I.1.1 ; Sections I.1.2-I.1.4 ; Section I.1.5 ; Section I.1.6 ; 8. Exercises ; I.2: Linear Programming ; 1. Introduction ; 2. Duality ; 3. The Primal and Dual Simplex Algorithms ; Bases and Basic Solutions ; Changing the Basis ; Primal Simplex Algorithm Dual Simplex Algorithm Dual Simplex Algorithm (phase 2) ; The Simplex Algorithm with Simple Upper Bounds ; Addition of Constraints or Variables ; 4. Subgradient Optimization ; The Subgradient Algorithm for (4.1) ; 5. Notes ; Sections I.2.1-i.2.3. ; Section I.2.4 ; I.3: Graphs and Networks ; 1. Introduction ; 2. The Minimum-weight or Shortest-path Problem ; Dijkstra''s Minimum-weight Path Algorithm ; Bellman-ford Minimum-weight Path Algorithm ; 3. The Minimum-weight Spanning Tree Problem ; Algorithm for Constructing a Spanning Tree ; 4. The Maximum-flow and Minimum-cut Problems Augmenting Path Algorithm 5. The Transportation Problem: A Primal-dual Algorithm ; Primal-dual Algorithm for the Transportation Problem ; Minimum-cost Path Augmentation Algorithm ; 6. A Primal Simplex Algorithm for Network Flow Problems ; 7. Notes ; Section I.3.1 ; Section I.3.2 ; Section I.3.3 ; Section I.3.4 ; Section I.3.5 ; Section I.3.6 ; I.4: Polyhedral Theory ; 1. Introduction and Elementary Linear Algebra ; 2. Definitions of Polyhedra and Dimension ; 3. Describing Polyhedra by Facets ; 4. Describing Polyhedra by Extreme Points and Extreme Rays ; 5. Polarity 6. Polyhedral Ties Between Linear and Integer Programs 7. Notes ; Sections I.4.1-I.4.4 ; Section I.4.5 ; Section I.4.6 ; 8. Exercises ; 1.5: Computational Complexity ; 1. Introduction ; 2. Measuring Algorithm Efficiency and Problem Complexity ; 3. Some Problems Solvable in Polynomial Time ; 4. Remarks on 0-1 and Pure-integer Programming ; 5. Nondeterministic Polynomial-time Algorithms and Np Problems ; Certificates of Feasibility, the Class Np, and Nondeterministic Algorithms ; 6. The Most Difficult Np Problems: the Class Np ; 7. Complexity and Polyhedra ; 8. Notes ; Sections I.5.1 and I.5.2 Section I.5.3 |
| Record Nr. | UNINA-9910791157203321 |
Wolsey Laurence A
|
||
| Hoboken, : Wiley, 2014 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Integer and Combinatorial Optimization [[electronic resource]]
| Integer and Combinatorial Optimization [[electronic resource]] |
| Autore | Wolsey Laurence A |
| Edizione | [1st ed.] |
| Pubbl/distr/stampa | Hoboken, : Wiley, 2014 |
| Descrizione fisica | 1 online resource (783 p.) |
| Disciplina | 519.7/7 |
| Altri autori (Persone) | NemhauserGeorge L |
| Collana | Wiley Series in Discrete Mathematics and Optimization |
| Soggetto topico |
Combinatorial optimization
Integer programming Mathematical optimization Civil & Environmental Engineering Engineering & Applied Sciences Operations Research |
| ISBN |
1-118-62686-9
1-118-62737-7 1-118-62725-3 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Cover ; Title Page ; Copyright ; Preface ; Contents ; Part I: Foundations ; I.1 The Scope of Integer and Combinatorial Optimization ; 1. Introduction ; 2. Modeling with Binary Variables I: Knapsack, Assignmentand Matching, Covering, Packing and Partitioning ; The 0-1 Knapsack Problem ; The Assignment and Matching Problems ; Set-covering, Set-packing, and Set-partitioning Problems ; 3. Modeling with Binary Variables II: Facility Location, Fixed-charge Network Flow, and Traveling Salesman ; Facility Location Problems ; The Fixed-charge Network Flow Problem ; The Traveling Salesman Problem
4. Modeling with Binary Variables III: Nonlinear Functions and Disjunctive ConstraintsPiecewise Linear Functions ; Disjunctive Constraints ; A Scheduling Problem ; 5. Choices in Model Formulation ; 6. Preprocessing ; Tightening Bounds ; Adding Logical Inequalities, Fixing Variables, and Removing Redundant Constraints ; 7. Notes ; Section I.1.1 ; Sections I.1.2-I.1.4 ; Section I.1.5 ; Section I.1.6 ; 8. Exercises ; I.2: Linear Programming ; 1. Introduction ; 2. Duality ; 3. The Primal and Dual Simplex Algorithms ; Bases and Basic Solutions ; Changing the Basis ; Primal Simplex Algorithm Dual Simplex Algorithm Dual Simplex Algorithm (phase 2) ; The Simplex Algorithm with Simple Upper Bounds ; Addition of Constraints or Variables ; 4. Subgradient Optimization ; The Subgradient Algorithm for (4.1) ; 5. Notes ; Sections I.2.1-i.2.3. ; Section I.2.4 ; I.3: Graphs and Networks ; 1. Introduction ; 2. The Minimum-weight or Shortest-path Problem ; Dijkstra''s Minimum-weight Path Algorithm ; Bellman-ford Minimum-weight Path Algorithm ; 3. The Minimum-weight Spanning Tree Problem ; Algorithm for Constructing a Spanning Tree ; 4. The Maximum-flow and Minimum-cut Problems Augmenting Path Algorithm 5. The Transportation Problem: A Primal-dual Algorithm ; Primal-dual Algorithm for the Transportation Problem ; Minimum-cost Path Augmentation Algorithm ; 6. A Primal Simplex Algorithm for Network Flow Problems ; 7. Notes ; Section I.3.1 ; Section I.3.2 ; Section I.3.3 ; Section I.3.4 ; Section I.3.5 ; Section I.3.6 ; I.4: Polyhedral Theory ; 1. Introduction and Elementary Linear Algebra ; 2. Definitions of Polyhedra and Dimension ; 3. Describing Polyhedra by Facets ; 4. Describing Polyhedra by Extreme Points and Extreme Rays ; 5. Polarity 6. Polyhedral Ties Between Linear and Integer Programs 7. Notes ; Sections I.4.1-I.4.4 ; Section I.4.5 ; Section I.4.6 ; 8. Exercises ; 1.5: Computational Complexity ; 1. Introduction ; 2. Measuring Algorithm Efficiency and Problem Complexity ; 3. Some Problems Solvable in Polynomial Time ; 4. Remarks on 0-1 and Pure-integer Programming ; 5. Nondeterministic Polynomial-time Algorithms and Np Problems ; Certificates of Feasibility, the Class Np, and Nondeterministic Algorithms ; 6. The Most Difficult Np Problems: the Class Np ; 7. Complexity and Polyhedra ; 8. Notes ; Sections I.5.1 and I.5.2 Section I.5.3 |
| Record Nr. | UNINA-9910816400303321 |
|
Wolsey Laurence A
|
||
| Hoboken, : Wiley, 2014 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||