## Theory of linear and integer programming

Author: Schrijver, Alexander Series: Wiley-Interscience series in discrete mathematics and optimization Publisher: Wiley, 1986.Language: EnglishDescription: xi, 471 p. ; 25 cm.ISBN: 0471982326 ; 0471908541Type of document: BookItem type | Current location | Collection | Call number | Status | Date due |
---|---|---|---|---|---|

Doriot Library Main Collection |
T57.74 .S53 1986
(Browse shelf) 000280127 |
Available |

Digitized

Contents 1 Introduction and preliminaries 1.1 Introduction, 1 1.2 Generalpreliminaries, 3 1.3 Preliminaries from linear algebra, matrix theory, and Euclidean geometry, 4 1.4 Some graph theory, 8 2 Problems, algorithms, and complexity 2.1 2.2 2.3 2.4 2.5 2.6 Letters, words, and sizes, 15 Problems, 15 Algorithms and running time, 16 Polynomial algorithms, 17 The classes P, N P, and co-N P, 18 N P-complete problems, 20 Some historical notes, 21 14 PART I: LINEAR ALGEBRA 3 Linear algebra and complexity 3.1 Some theory, 27 3.2 Sizes and good characterizations, 29 3.3 The Gaussian elimination method, 31 3.4 Iterative methods, 36 Notes on linear algebra Historical notes, 38 Further notes on linear algebra, 40 25 27 38 PART II: LATTICES AND LINEAR DIOPHANTINE EQUATIONS 4 Theory of lattices and linear diophantine equations 4.1 4.2 4.3 4.4 The Hermite normal form, 45 Uniqueness of the Hermite normal form, 48 Unimodular matrices, 48 Further remarks, 50 vii 43 45 Viii, . Contents Algorithms for linear diophantine equations 5.1 The Euclidean algorithm, 52 5.2 Sizes and good characterizations, 54 5.3 Polynomial algorithms for Hermite normal forms and systems of linear diophantine equations, 56 52 5 6 Diophantine approximation and basis reduction 6.1 The continued fraction method, 60 6.2 Basis reduction in lattices, 67 6.3 Applications of the basis reduction method, 71 Notes on lattices and linear diophantine equations Historical notes, 76 Further notes on lattices and linear diophantine equations, 82 60 76 PART III: POLYHEDRA, LINEAR INEQUALITIES, AND LINEAR PROGRAMMING 7 Fundamental concepts and results on polyhedra, linear inequalities, and linear programming 7.1 7.2 1.3 7.4 7.5 7.6 7.7 7.8 7.9 7.10 8 The Fundamental theorem of linear inequalities, 85 Cones, polyhedra, and polytopes, 87 Farkas' lemma and variants, 89 Linear programming, 90 LP-duality geometrically, 92 Affine form of Farkas' lemma, 93 Carathéodory's theorem, 94 Strict inequalities, 94 Complementary slackness, 95 Application: max-flow min-cut, 96 83 85 The structure of polyhedra 8.1 Implicit equalities and redundant constraints, 99 8.2 Characteristic cone, lineality space, afline hull, dimension, 8.3 Faces, 101 8.4 Facets, 101 8.5 Minimal faces and vertices, 104 8.6 The face-lattice, 104 8.7 Edges and extremal 105 , 8.8 Extremal rays cones, 105 8.9 Decomposition of polyhedra, 106 8.10 Application: doubly stochastic matrices, 107 8.11 Application: the matching polytope, 109 100 99 9 Polarity, and blocking and anti-blocking polyhedra 9.1 Polarity, 112 9.2 Blocking polyhedra, 113 9.3 Anti-blocking polyhedra, 116 112 Contents ix 10 Sizes and the theoretical complexity of linear inequalities and linear programming 10.1 Sizes and good characterizations, 120 10.2 Vertex and facet complexity, 121 10.3 Polynomial equivalence of linear inequalities and linear programming, 10.4 Sensitivity analysis, 125 120 124 11 The simplex method 11.1 The simplex method, 129 11.2 The simplex method in tableau form, 132 11.3 Pivot selection. cycling, and complexity, 137 11.4 The worst-case behaviour of the simplex method, 11.5 The average running time of the simplex method, 11.6 The revised simplex method, 147 11.7 The dual simplex method, 148 129 139 142 12 Primal-dual, elimination, and relaxation methods 12.1 The primal-dual method, 151 12.2 The Fourier-Motzkin elimination method, 12.3 The relaxation method, 157 13 155 151 Khachiyan's method for linear programming 13.1 13.2 13.3 13.4 13.5 13.6 Ellipsoids, 163 Khachiyan's method: outline, 165 Two approximation lemmas, 166 Khachiyan's method more precisely, 168 The practical complexity of Khachiyan's method, Further remarks. 171 163 170 14 The ellipsoid method for polyhedra more generally 14.1 Finding a solution with a separation algorithm, 172 14.2 Equivalence of separation and optimization, 177 14.3 Further implications, 183 172 15 Further polynomiality results in linear programming 15.1 Karmarkar's polynomial-time algorithm for linear programming, 190 15.2 Strongly polynomial algorithms, 194 15.3 Megiddo's linear-time LP-algorithm in fixed dimension, 199 15.4 Shallow cuts and rounding of polytopes, 205 Notes on polyhedra, linear inequalities, and linear programming Historical notes, 209 Further notes on polyhedra, linear inequalities, and linear programming, 223 190 209 x Contents PART IV: INTEGER LINEAR PROGRAMMING 16 Introduction to integer linear programming 16.1 Introduction, 229 16.2 The integer hull of a polyhedron, 230 16.3 Integral polyhedra, 231 16.4 Hilbert bases, 232 16.5 A theorem of Bell and Scarf, 234 16.6 The knapsack problem and aggregation, 235 16.7 Mixed integer linear programming, 236 17 Estimates in integer linear programming 17.1 17.2 17.3 17.4 18 Sizes of solutions, 237 Distances of optimum solutions, 239 Finite test sets for integer linear programming, 242 The facets of PI, 243 227 229 1 237 The complexity of integer linear programming 18.1 ILP is NP-complete, 245 18.2 NP-completeness of related problems, 248 18.3 Complexity of facets, vertices, and adjacency on the integer hull, 251 18.4 Lenstra's algorithm for integer linear programming, 256 18.5 Dynamic programming applied to the knapsack problem, 261 18.6 Dynamic programming applied to integer linear programming, 264 245 19 Totally unimodular matrices: fundamental properties and examples 19.1 19.2 19.3 19.4 Total unimodularity and optimization, 266 More characterizations of total unimodularity, 269 The basic examples: network matrices, 272 Decomposition of totally unimodular matrices, 279 266 20 Recognizing total unimodularity 20.1 20.2 20.3 21 Recognizing network matrices, 282 Decomposition test, 287 Total unimodularity test, 290 282 Further theory related to total unimodularity 21.1 21.2 21.3 21.4 21.5 Regular matroids and signing of {O, I}-matrices, 294 Chain groups, 297 An upper bound of Heller 299 Unimodular matrices more generally, 301 Balanced matrices, 303 294 22 Integral polyhedra and total dual integrality 22.1 22.2 22.3 22.4 22.5 Integral polyhedra and total dual integrality, 310 Two combinatorial applications, 312 Hilbert bases and minimal TDI-systems, 315 Box-total dual integrality, 317 Behaviour of total dual integrality under operations, 321 309 Contents xi 22.6 An integer analogue of Carathtodory's theorem, 326 22.7 Another characterization of total dual integrality, 327 22.8 Optimization over integral polyhedra and TDI-systems algorithmically, 330 22.9 Recognizing integral polyhedra and total dual integrality, 332 22.10 Integer rounding and decomposition, 336 23 Cutting planes 23. I 23.2 23.3 23.4 23.5 23.6 23.7 23.8 339 Finding the integer hull with cutting planes, 339 Cutting plane proofs, 343 The number of cutting planes and the length of cutting plane proofs, The Chvatal rank, 347 Two combinatorial illustrations. 348 Cutting planes and NP-theory, 351 Chvatal functions and duality, 353 Gomory's cutting plane method, 354 344 24 Further methods in integer linear progamming 24.1 Branch-and-bound methods for integer linear progamming, 360 24.2 The group problem and corner polyhedra, 363 24.3 Lagrangean relaxation, 367 24.4 Application: the traveling salesman problem, 370 24.5 Benders' decomposition, 371 24.6 Some notes on integer linear programming in practice, Historical and further notes on integer linear programming Historical notes, 375 Further notes on integer linear programming, References Notation index Author index Subject index 378 360 375 381 452 454 465

There are no comments for this item.