Large Scale Linear and Integer Optimization

by Martin, Richard Kipp

• ISBN13: 9780792382027
• ISBN10: 0792382021
• Format: Hardcover
• Copyright: 1998-12-01
• Publisher: Kluwer Academic Pub

Summary

There is a growing need in major industries such as airline, trucking, financial engineering, etc. to solve very large linear and integer linear optimization problems. Because of the dramatic increase in computing power, it is now possible to solve these problems. Along with the increase in computer power, the mathematical programming community has developed better and more powerful algorithms to solve very large problems. These algorithms are of interest to many researchers in the areas of operations research/management science, computer science, and engineering. In this book, Kipp Martin has systematically provided users with a unified treatment of the algorithms and the implementation of the algorithms that are important in solving large problems. Parts I and II of Large Scale Linear and Integer Programming provide an introduction to linear optimization using two simple but unifying ideas-projection and inverse projection. The ideas of projection and inverse projection are also extended to integer linear optimization. With the projection-inverse projection approach, theoretical results in integer linear optimization become much more analogous to their linear optimization counterparts. Hence, with an understanding of these two concepts, the reader is equipped to understand fundamental theorems in an intuitive way. Part III presents the most important algorithms that are used in commercial software for solving real-world problems. Part IV shows how to take advantage of the special structure in very large scale applications through decomposition. Part V describes how to take advantage of special structureby modifying and enhancing the algorithms developed in Part III. This section contains a discussion of the current research in linear and integer linear programming. The author also shows in Part V how to take different problem formulations and appropriately 'modify' them so that the algorithms from Part III are more efficient. Again, the projection and inverse projection concepts are used in Part V to present the current research in linear and integer linear optimization in a very unified way. While the book is written for a mathematically mature audience, no prior knowledge of linear or integer linear optimization is assumed. The audience is upper-level undergraduate students and graduate students in computer science, applied mathematics, industrial engineering and operations research/management science. Course work in linear algebra and analysis is sufficient background.

Table of Contents

Preface	xv
Part I MOTIVATION	1	(32)
1 LINEAR AND INTEGER LINEAR OPTIMIZATION	3	(30)
1.1 Introduction	3	(2)
1.2 Linear and Integer Linear Optimization	5	(2)
1.3 A Guided Tour of Applications	7	(14)
1.4 Special Structure	21	(4)
1.5 Linear and Integer Linear Programming Codes	25	(3)
1.6 Other Directions	28	(1)
1.7 Exercises	29	(4)
Part II THEORY	33	(108)
2 LINEAR SYSTEMS AND PROJECTION	35	(46)
2.1 Introduction	35	(1)
2.2 Projection for Equality Systems: Gaussian Elimination	36	(3)
2.3 Projection for Inequality Systems: Fourier-Motzkin Elimination	39	(7)
2.4 Applications of Projection	46	(3)
2.5 Theorems of the Alternative	49	(8)
2.6 Duality Theory	57	(4)
2.7 Complementary Slackness	61	(4)
2.8 Sensitivity Analysis	65	(10)
2.9 Conclusion	75	(1)
2.10 Exercises	75	(6)
3 LINEAR SYSTEMS AND INVERSE PROJECTION	81	(22)
3.1 Introduction	81	(1)
3.2 Deleting Constraints by Adding Variables	81	(10)
3.3 Dual Relationships	91	(2)
3.4 Sensitivity Analysis	93	(6)
3.5 Conclusion	99	(1)
3.6 Homework Exercises	100	(3)
4 INTEGER LINEAR SYSTEMS: PROJECTION AND INVERSE PROJECTION	103	(38)
4.1 Introduction	103	(2)
4.2 Background Material	105	(9)
4.3 Solving A System of Congruence Equations	114	(8)
4.4 Integer Linear Equalities	122	(2)
4.5 Integer Linear Inequalities: Projection	124	(3)
4.6 Integer Linear Inequalities: Inverse Projection	127	(9)
4.7 Conclusion	136	(1)
4.8 Exercises	137	(4)
Part III ALGORITHMS	141	(206)
5 THE SIMPLEX ALGORITHM	143	(40)
5.1 Introduction	143	(1)
5.2 Motivation	143	(4)
5.3 Pivoting	147	(7)
5.4 Revised Simplex	154	(8)
5.5 Product Form of the Inverse	162	(6)
5.6 Degeneracy and Cycling	168	(9)
5.7 Complexity of the Simplex Algorithm	177	(1)
5.8 Conclusion	178	(1)
5.9 Exercises	178	(5)
6 MORE ON SIMPLEX	183	(36)
6.1 Introduction	183	(1)
6.2 Sensitivity Analysis	184	(7)
6.3 The Dual Simplex Algorithm	191	(7)
6.4 Simple Upper Bounds and Special Structure	198	(3)
6.5 Finding a Starting Basis	201	(4)
6.6 Pivot Column Selection	205	(4)
6.7 Other Computational Issues	209	(6)
6.8 Conclusion	215	(1)
6.9 Exercises	216	(3)
7 INTERIOR POINT ALGORITHMS: POLYHEDRAL TRANSFORMATIONS	219	(42)
7.1 Introduction	219	(6)
7.2 Projective Transformations	225	(6)
7.3 Karmarkar's Algorithm	231	(3)
7.4 Polynomial Termination	234	(5)
7.5 Purification, Standard Form and Sliding Objective	239	(4)
7.6 Affine Polyhedral Transformations	243	(11)
7.7 Geometry of the Least Squares Problem	254	(4)
7.8 Conclusion	258	(1)
7.9 Exercises	258	(3)
8 INTERIOR POINT ALGORITHMS: BARRIER METHODS	261	(52)
8.1 Introduction	261	(5)
8.2 Primal Path Following	266	(6)
8.3 Dual Path Following	272	(5)
8.4 Primal-Dual Path Following	277	(6)
8.5 Polynomial Termination of Path Following Algorithms	283	(9)
8.6 Relation to Polyhedral Transformation Algorithms	292	(5)
8.7 Predictor-Corrector Algorithms	297	(3)
8.8 Other Issues	300	(6)
8.9 Conclusion	306	(4)
8.10 Exercises	310	(3)
9 INTEGER PROGRAMMING	313	(34)
9.1 Introduction	313	(1)
9.2 Modeling with Integer Variables	314	(5)
9.3 Branch-and-Bound	319	(5)
9.4 Node and Variable Selection	324	(4)
9.5 More General Branching	328	(13)
9.6 Conclusion	341	(1)
9.7 Exercises	341	(6)
Part IV SOLVING LARGE SCALE PROBLEMS: DECOMPOSITION METHODS	347	(90)
10 PROJECTION: BENDERS' DECOMPOSITION	349	(20)
10.1 Introduction	349	(1)
10.2 The Benders' Algorithm	350	(4)
10.3 A Location Application	354	(6)
10.4 Dual Variable Selection	360	(4)
10.5 Conclusion	364	(1)
10.6 Exercises	365	(4)
11 INVERSE PROJECTION: DANTZIG-WOLFE DECOMPOSITION	369	(24)
11.1 Introduction	369	(1)
11.2 Dantzig-Wolfe Decomposition	370	(5)
11.3 A Location Application	375	(9)
11.4 Taking Advantage of Block Angular Structure	384	(2)
11.5 Computational Issues	386	(4)
11.6 Conclusion	390	(1)
11.7 Exercises	391	(2)
12 LAGRANGIAN METHODS	393	(44)
12.1 Introduction	393	(1)
12.2 The Lagrangian Dual	394	(4)
12.3 Extension to Integer Programming	398	(4)
12.4 Properties of the Lagrangian Dual	402	(6)
12.5 Optimizing the Lagrangian Dual	408	(18)
12.6 Computational Issues	426	(3)
12.7 A Decomposition Algorithm for Integer Programming	429	(5)
12.8 Conclusion	434	(1)
12.9 Exercises	435	(2)
Part V SOLVING LARGE SCALE PROBLEMS: USING SPECIAL STRUCTURE	437	(196)
13 SPARSE METHODS	439	(42)
13.1 Introduction	439	(1)
13.2 LU Decomposition	439	(7)
13.3 Sparse LU Update	446	(16)
13.4 Numeric Cholesky Factorization	462	(4)
13.5 Symbolic Cholesky Factorization	466	(5)
13.6 Storing Sparse Matrices	471	(1)
13.7 Programming Issues	472	(6)
13.8 Computational Results: Barrier versus Simplex	478	(1)
13.9 Conclusion	479	(1)
13.10 Exercises	480	(1)
14 NETWORK FLOW LINEAR PROGRAMS	481	(46)
14.1 Introduction	481	(1)
14.2 Totally Unimodular Linear Programs	482	(11)
14.3 Network Simplex Algorithm	493	(12)
14.4 Important Network Flow Problems	505	(8)
14.5 Almost Network Problems	513	(2)
14.6 Integer Polyhedra	515	(8)
14.7 Conclusion	523	(1)
14.8 Exercises	524	(3)
15 LARGE INTEGER PROGRAMS: PREPROCESSING AND CUTTING PLANES	527	(38)
15.1 Formulation Principles and Techniques	527	(6)
15.2 Preprocessing	533	(9)
15.3 Cutting Planes	542	(13)
15.4 Branch-and-Cut	555	(2)
15.5 Lifting	557	(3)
15.6 Lagrangian Cuts	560	(1)
15.7 Integer Programming Test Problems	561	(1)
15.8 Conclusion	562	(1)
15.9 Exercises	563	(2)
16 LARGE INTEGER PROGRAMS: PROJECTION AND INVERSE PROJECTION	565	(68)
16.1 Introduction	565	(8)
16.2 Auxiliary Variable Methods	573	(28)
16.3 A Projection Theorem	601	(1)
16.4 Branch-and-Price	601	(12)
16.5 Projection of Extended Formulations: Benders' Decomposition Revisited	613	(17)
16.6 Conclusion	630	(1)
16.7 Exercises	630	(3)
Part VI APPENDIX	633	(54)
A POLYHEDRAL THEORY	635	(22)
A.1 Introduction	635	(1)
A.2 Concepts and Definitions	635	(5)
A.3 Faces of Polyhedra	640	(5)
A.4 Finite Basis Theorems	645	(6)
A.5 Inner Products, Subspaces and Orthogonal Subspaces	651	(2)
A.6 Exercises	653	(4)
B COMPLEXITY THEORY	657	(20)
B.1 Introduction	657	(3)
B.2 Solution Sizes	660	(1)
B.3 The Turing Machine	661	(2)
B.4 Complexity Classes	663	(4)
B.5 Satisfiability	667	(2)
B.6 NP-Completeness	669	(1)
B.7 Complexity of Gaussian Elimination	670	(4)
B.8 Exercises	674	(3)
C BASIC GRAPH THEORY	677	(4)
D SOFTWARE AND TEST PROBLEMS	681	(2)
E NOTATION	683	(4)
References	687	(36)
AUTHOR INDEX	723	(8)
TOPIC INDEX	731