05482nam 2200661Ia 450 991058307030332120200520144314.01-280-63811-797866106381160-08-045921-897804445150709780444515070(CKB)1000000000358089(EBL)270186(OCoLC)476002192(SSID)ssj0000139830(PQKBManifestationID)12000908(PQKBTitleCode)TC0000139830(PQKBWorkID)10029006(PQKB)10374837(MiAaPQ)EBC270186(EXLCZ)99100000000035808920040713d2005 uy 0engurcn|---|||||txtccrDiscrete optimization /edited by K. Aardal, G.L. Nemhauser and R. Weismantel1st ed.Amsterdam ;Boston Elsevier20051 online resource (621 p.)Handbooks in operations research and management science ;v. 12Description based upon print version of record.Includes bibliographical references and index.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 Introduction2 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; ReferencesChapter 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 theorem15 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 programming4 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 algorithms3 Decomposition algorithms for two-stage SMIP: stagewise decompositionThe 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 chapteHandbooks in operations research and management science ;v. 12.Mathematical optimizationInteger programmingMathematical optimization.Integer programming.519.6Aardal K(Karen)911025Nemhauser George L65489Weismantel Robert770664MiAaPQMiAaPQMiAaPQttps://www.sciencedirect.com/science/handbooks/09270507/129910583070303321Discrete optimization2039931UNINA