Discrete optimization / / edited by K. Aardal, G.L. Nemhauser and R. Weismantel

• Pubblicazione: Amsterdam ; ; Boston, : Elsevier, 2005
• Edizione: 1st ed.
• Descrizione fisica: 1 online resource (621 p.)
• Disciplina: 519.6
• Soggetto topico: Mathematical optimization; Integer programming
• Altri autori: AardalK (Karen) NemhauserGeorge L WeismantelRobert
• Note generali: Description based upon print version of record.
• Nota di bibliografia: Includes bibliographical references and index.
• 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
• Sommario/riassunto: The chapters of this Handbook volume covers nine main topics that are representative of recenttheoretical and algorithmic developments in the field. In addition to the nine papers that present the state of the art, there is an article onthe early history of the field. The handbook will be a useful reference to experts in the field as well as students and others who want to learn about discrete optimization. All of the chapters in this handbook are written by authors who have made significant original contributions to their topics. Herewith a brief introduction to the chapte
• Titolo autorizzato: Discrete optimization
• ISBN: 1-280-63811-7; 9786610638116; 0-08-045921-8; 9780444515070
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910583070303321
• Lo trovi qui: Univ. Federico II
• Serie: Handbooks in operations research and management science ; ; v. 12.