Theory of linear and integer programming

Cover......Page 1
Title Page......Page 4
Copyright Page......Page 5
Preface......Page 6
Contents\0......Page 8
1.1 Introduction,\0......Page 14
1.2 General preliminaries,\0......Page 16
1.3 Preliminaries from linear algebra, matrix theory, and Euclidean geometry,\0......Page 17
1.4 Some graph theory,\0......Page 21
2 Problems, algorithms, and complexity\0......Page 27
2.2 Problems,\0......Page 28
2.3 Algorithms and running time,\0......Page 29
2.4 Polynomial algorithms,\0......Page 30
2.5 The classes 9, .K9, and co-.N\'9,\0......Page 31
2.6 .K9-complete problems,\0......Page 33
Some historical notes,\0......Page 34
PART I: LINEAR ALGEBRA\0......Page 38
3.1 Some theory,\0......Page 40
3.2 Sizes and good characterizations,\0......Page 42
3.3 The Gaussian elimination method,\0......Page 44
3.4 Iterative methods,\0......Page 49
Historical notes,\0......Page 51
Further notes on linear algebra,\0......Page 53
PART II: LATTICES AND LINEAR DIOPHANTINE EQUATIONS\0......Page 56
4.1 The Hermite normal form,\0......Page 58
4.3 Unimodular matrices,\0......Page 61
4.4 Further remarks,\0......Page 63
5.1 The Euclidean algorithm,\0......Page 65
5.2 Sizes and good characterizations,\0......Page 67
5.3 Polynomial algorithms for Hermite normal forms and systems of linear diophantine equations,\0......Page 69
6.1 The continued fraction method,\0......Page 73
6.2 Basis reduction in lattices,\0......Page 80
6.3 Applications of the basis reduction method,\0......Page 84
Historical notes,\0......Page 89
Further notes on lattices and linear diophantine equations,\0......Page 95
PART III: POLYHEDRA, LINEAR INEQUALITIES, AND LINEAR PROGRAMMING\0......Page 96
7.1 The Fundamental theorem of linear inequalities,\0......Page 98
7.2 Cones, polyhedra, and polytopes,\0......Page 100
7.3 Farkas\' lemma and variants,\0......Page 102
7.4 Linear programming,\0......Page 103
7.5 LP-duality geometrically,\0......Page 105
7.6 Affine form of Farkas\' lemma,\0......Page 106
7.8 Strict inequalities,\0......Page 107
7.9 Complementary slackness,\0......Page 108
7.10 Application: max-flow min-cut,\0......Page 109
8.1 Implicit equalities and redundant constraints,\0......Page 112
8.2 Characteristic cone, lineality space, affine hull, dimension,\0......Page 113
8.4 Facets,\0......Page 114
8.6 The face-lattice,\0......Page 117
8.8 Extremal rays of cones,\0......Page 118
8.9 Decomposition of polyhedra,\0......Page 119
8.10 Application: doubly stochastic matrices,\0......Page 120
8.11 Application: the matching polytope,\0......Page 122
9.1 Polarity,\0......Page 125
9.2 Blocking polyhedra,\0......Page 126
9.3 Anti-blocking polyhedra,\0......Page 129
10.1 Sizes and good characterizations,\0......Page 133
10.2 Vertex and facet complexity,\0......Page 134
10.3 Polynomial equivalence of linear inequalities and linear programming,\0......Page 137
10.4 Sensitivity analysis,\0......Page 138
11.1 The simplex method,\0......Page 142
11.2 The simplex method in tableau form,\0......Page 145
11.3 Pivot selection, cycling, and complexity,\0......Page 150
11.4 The worst-case behaviour of the simplex method,\0......Page 152
11.5 The average running time of the simplex method,\0......Page 155
11.6 The revised simplex method,\0......Page 160
11.7 The dual simplex method,\0......Page 161
12.1 The primal-dual method,\0......Page 164
12.2 The Fourier-Motzkin elimination method,\0......Page 168
12.3 The relaxation method,\0......Page 170
13.1 Ellipsoids,\0......Page 176
13.2 Khachiyan\'s method: outline,\0......Page 178
13.3 Two approximation lemmas,\0......Page 179
13.4 Khachiyan\'s method more precisely,\0......Page 181
13.5 The practical complexity of Khachiyan\'s method,\0......Page 183
13.6 Further remarks,\0......Page 184
14.1 Finding a solution with a separation algorithm,\0......Page 185
14.2 Equivalence of separation and optimization,\0......Page 190
14.3 Further implications,\0......Page 196
15.1 Karmarkar\'s polynomial-time algorithm for linear programming,\0......Page 203
15.2 Strongly polynomial algorithms,\0......Page 207
15.3 Megiddo\'s linear-time LP-algorithm in fixed dimension,\0......Page 212
15.4 Shallow cuts and rounding of polytopes,\0......Page 218
Historical notes,\0......Page 222
Further notes on polyhedra, linear inequalities, and linear programming,\0......Page 236
PART IV: INTEGER LINEAR PROGRAMMING\0......Page 240
16.1 Introduction,\0......Page 242
16.2 The integer hull of a polyhedron,\0......Page 243
16.3 Integral polyhedra,\0......Page 244
16.4 Hilbert bases,\0......Page 245
16.5 A theorem of Bell and Scarf,\0......Page 247
16.6 The knapsack problem and aggregation,\0......Page 248
16.7 Mixed integer linear programming,\0......Page 249
17.1 Sizes of solutions,\0......Page 250
17.2 Distances of optimum solutions,\0......Page 252
17.3 Finite test sets for integer linear programming,\0......Page 255
17.4 The facets of P,,\0......Page 256
18.1 ILP is .N\'9-complete,\0......Page 258
18.2 X61-completeness of related problems,\0......Page 261
18.3 Complexity of facets, vertices, and adjacency on the integer hull,\0......Page 264
18.4 Lenstra\'s algorithm for integer linear programming,\0......Page 269
18.5 Dynamic programming applied to the knapsack problem,\0......Page 274
18.6 Dynamic programming applied to integer linear programming,\0......Page 277
19.1 Total unimodularity and optimization,\0......Page 279
19.2 More characterizations of total unimodularity,\0......Page 282
19.3 The basic examples: network matrices,\0......Page 285
19.4 Decomposition of totally unimodular matrices,\0......Page 292
20.1 Recognizing network matrices,\0......Page 295
20.2 Decomposition test,\0......Page 300
20.3 Total unimodularity test,\0......Page 303
21.1 Regular matroids and signing of {0,1}-matrices,\0......Page 307
21.2 Chain groups,\0......Page 310
21.3 An upper bound of Heller,\0......Page 312
21.4 Unimodular matrices more generally,\0......Page 314
21.5 Balanced matrices,\0......Page 316
22 Integral polyhedra and total dual integrality\0......Page 322
22.1 Integral polyhedra and total dual integrality,\0......Page 323
22.2 Two combinatorial applications,\0......Page 325
22.3 Hilbert bases and minimal TDI-systems,\0......Page 328
22.4 Box-total dual integrality,\0......Page 330
22.5 Behaviour of total dual integrality under operations,\0......Page 334
22.6 An integer analogue of Caratheodory\'s theorem,\0......Page 339
22.7 Another characterization of total dual integrality,\0......Page 340
22.8 Optimization over integral polyhedra and TDI-systems algorithmically,\0......Page 343
22.9 Recognizing integral polyhedra and total dual integrality,\0......Page 345
22.10 Integer rounding and decomposition,\0......Page 349
23.1 Finding the integer hull with cutting planes,\0......Page 352
23.2 Cutting plane proofs,\0......Page 356
23.3 The number of cutting planes and the length of cutting plane proofs,\0......Page 357
23.4 The Chvatal rank,\0......Page 360
23.5 Two combinatorial illustrations,\0......Page 361
23.6 Cutting planes and .N\'9-theory,\0......Page 364
23.7 Chvatal functions and duality,\0......Page 366
23.8 Gomory\'s cutting plane method,\0......Page 367
24.1 Branch-and-bound methods for integer linear progamming,\0......Page 373
24.2 The group problem and corner polyhedra,\0......Page 376
24.3 Lagrangean relaxation,\0......Page 380
24.4 Application: the traveling salesman problem,\0......Page 383
24.5 Benders\' decomposition,\0......Page 384
24.6 Some notes on integer linear programming in practice,\0......Page 385
Historical notes,\0......Page 388
Further notes on integer linear programming,\0......Page 391
References\0......Page 394
Notation index\0......Page 465
Author index\0......Page 467
Subject index\0......Page 478