LEADER 05886nam 22007933u 450 001 9910816400303321 005 20240405033423.0 010 $a1-118-62686-9 010 $a1-118-62737-7 010 $a1-118-62725-3 035 $a(CKB)2550000001349249 035 $a(EBL)1776322 035 $a(SSID)ssj0001371257 035 $a(PQKBManifestationID)11754302 035 $a(PQKBTitleCode)TC0001371257 035 $a(PQKBWorkID)11301284 035 $a(PQKB)10806385 035 $a(MiAaPQ)EBC1776322 035 $a(EXLCZ)992550000001349249 100 $a20140908d2014|||| u|| | 101 0 $aeng 135 $aur|n|---||||| 181 $ctxt 182 $cc 183 $acr 200 10$aInteger and Combinatorial Optimization$b[electronic resource] 205 $a1st ed. 210 $aHoboken $cWiley$d2014 215 $a1 online resource (783 p.) 225 1 $aWiley Series in Discrete Mathematics and Optimization 300 $aDescription based upon print version of record. 311 $a0-471-35943-2 311 $a1-322-09471-3 327 $aCover ; 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 327 $a4. 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 327 $aDual 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 327 $aAugmenting 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 327 $a6. 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 327 $aSection I.5.3 330 $aRave reviews for INTEGER AND COMBINATORIAL OPTIMIZATION""This book provides an excellent introduction and survey of traditional fields of combinatorial optimization . . . It is indeed one of the best and most complete texts on combinatorial optimization . . . available. [And] with more than 700 entries, [it] has quite an exhaustive reference list.""-Optima""A unifying approach to optimization problems is to formulate them like linear programming problems, while restricting some or all of the variables to the integers. This book is an encyclopedic resource for such formulations, as well as for 410 0$aWiley Series in Discrete Mathematics and Optimization 606 $aCombinatorial optimization 606 $aInteger programming 606 $aMathematical optimization 606 $aMathematical optimization 606 $aInteger programming 606 $aCombinatorial optimization 606 $aCivil & Environmental Engineering$2HILCC 606 $aEngineering & Applied Sciences$2HILCC 606 $aOperations Research$2HILCC 615 4$aCombinatorial optimization. 615 4$aInteger programming. 615 4$aMathematical optimization. 615 0$aMathematical optimization 615 0$aInteger programming 615 0$aCombinatorial optimization 615 7$aCivil & Environmental Engineering 615 7$aEngineering & Applied Sciences 615 7$aOperations Research 676 $a519.7/7 700 $aWolsey$b Laurence A$0104519 701 $aNemhauser$b George L$065489 801 0$bAU-PeEL 801 1$bAU-PeEL 801 2$bAU-PeEL 906 $aBOOK 912 $a9910816400303321 996 $aInteger and combinatorial optimization$91538976 997 $aUNINA