Theory of Linear and Integer Programming

by Schrijver, Alexander

• ISBN13: 9780471982326
• ISBN10: 0471982326
• Edition: 1st
• Format: Paperback
• Copyright: 1998-06-11
• Publisher: Wiley

Summary

Theory of Linear and Integer Programming Alexander Schrijver Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands This book describes the theory of linear and integer programming and surveys the algorithms for linear and integer programming problems, focusing on complexity analysis. It aims at complementing the more practically oriented books in this field. A special feature is the author's coverage of important recent developments in linear and integer programming. Applications to combinatorial optimization are given, and the author also includes extensive historical surveys and bibliographies. The book is intended for graduate students and researchers in operations research, mathematics and computer science. It will also be of interest to mathematical historians. Contents 1 Introduction and preliminaries; 2 Problems, algorithms, and complexity; 3 Linear algebra and complexity; 4 Theory of lattices and linear diophantine equations; 5 Algorithms for linear diophantine equations; 6 Diophantine approximation and basis reduction; 7 Fundamental concepts and results on polyhedra, linear inequalities, and linear programming; 8 The structure of polyhedra; 9 Polarity, and blocking and anti-blocking polyhedra; 10 Sizes and the theoretical complexity of linear inequalities and linear programming; 11 The simplex method; 12 Primal-dual, elimination, and relaxation methods; 13 Khachiyan's method for linear programming; 14 The ellipsoid method for polyhedra more generally; 15 Further polynomiality results in linear programming; 16 Introduction to integer linear programming; 17 Estimates in integer linear programming; 18 The complexity of integer linear programming; 19 Totally unimodular matrices: fundamental properties and examples; 20 Recognizing total unimodularity; 21 Further theory related to total unimodularity; 22 Integral polyhedra and total dual integrality; 23 Cutting planes; 24 Further methods in integer linear programming; Historical and further notes on integer linear programming; References; Notation index; Author index; Subject index

Author Biography

About the author Professor Schrijver has held tenured positions with the Mathematisch Centrum in Amsterdam, and the University of Amsterdam. He has spent leaves of absence in Oxford and Szeged (Hungary). In 1983 he was appointed to the post of Professor of Mathematics at Tilburg University, The Netherlands, with a partial engagement at the Centrum voor Wiskunde en Informatica in Amsterdam.

Table of Contents

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