## Large Scale Linear and Integer Optimization: A Unified Approach: A Unified ApproachThere 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

LINEAR AND INTEGER LINEAR OPTIMIZATION | 3 |

12 LINEAR AND INTEGER LINEAR OPTIMIZATION | 5 |

13 A GUIDED TOUR OF APPLICATIONS | 7 |

14 SPECIAL STRUCTURE | 21 |

15 LINEAR AND INTEGER LINEAR PROGRAMMING CODES | 25 |

16 OTHER DIRECTIONS | 28 |

17 EXERCISES | 29 |

THEORY | 33 |

103 A LOCATION APPLICATION | 354 |

104 DUAL VARIABLE SELECTION | 360 |

105 CONCLUSION | 364 |

106 EXERCISES | 365 |

INVERSE PROJECTION DANTZIGWOLFE DECOMPOSITION | 369 |

112 DANTZIGWOLFE DECOMPOSITION | 370 |

113 A LOCATION APPLICATION | 375 |

114 TAKING ADVANTAGE OF BLOCK ANGULAR STRUCTURE | 384 |

LINEAR SYSTEMS AND PROJECTION | 35 |

GAUSSIAN ELIMINATION | 36 |

FOURIERMOTZKIN ELIMINATION | 39 |

24 APPLICATIONS OF PROJECTION | 46 |

25 THEOREMS OF THE ALTERNATIVE | 49 |

26 DUALITY THEORY | 57 |

27 COMPLEMENTARY SLACKNESS | 61 |

28 SENSITIVITY ANALYSIS | 65 |

29 CONCLUSION | 75 |

LINEAR SYSTEMS AND INVERSE PROJECTION | 81 |

33 DUAL RELATIONSHIPS | 91 |

34 SENSITIVITY ANALYSIS | 93 |

35 CONCLUSION | 99 |

36 HOMEWORK EXERCISES | 100 |

INTEGER LINEAR SYSTEMS PROJECTION AND INVERSE PROJECTION | 103 |

42 BACKGROUND MATERIAL | 105 |

43 SOLVING A SYSTEM OF CONGRUENCE EQUATIONS | 114 |

44 INTEGER LINEAR EQUALITIES | 122 |

45 INTEGER LINEAR INEQUALITIES PROJECTION | 124 |

46 INTEGER LINEAR INEQUALITIES INVERSE PROJECTION | 127 |

47 CONCLUSION | 136 |

48 EXERCISES | 137 |

ALGORITHMS | 141 |

THE SIMPLEX ALGORITHM | 143 |

53 PIVOTING | 147 |

54 REVISED SIMPLEX | 154 |

55 PRODUCT FORM OF THE INVERSE | 162 |

56 DEGENERACY AND CYCLING | 168 |

57 COMPLEXITY OF THE SIMPLEX ALGORITHM | 177 |

58 CONCLUSION | 178 |

MORE ON SIMPLEX | 183 |

62 SENSITIVITY ANALYSIS | 184 |

63 THE DUAL SIMPLEX ALGORITHM | 191 |

64 SIMPLE UPPER BOUNDS AND SPECIAL STRUCTURE | 198 |

65 FINDING A STARTING BASIS | 201 |

66 PIVOT COLUMN SELECTION | 205 |

67 OTHER COMPUTATIONAL ISSUES | 209 |

68 CONCLUSION | 215 |

69 EXERCISES | 216 |

INTERIOR POINT ALGORITHMS POLYHEDRAL TRANSFORMATIONS | 219 |

72 PROJECTIVE TRANSFORMATIONS | 225 |

73 KARMARKARS ALGORITHM | 231 |

74 POLYNOMIAL TERMINATION | 234 |

75 PURIFICATION STANDARD FORM AND SLIDING OBJECTIVE | 239 |

76 AFFINE POLYHEDRAL TRANSFORMATIONS | 243 |

77 GEOMETRY OF THE LEAST SQUARES PROBLEM | 254 |

78 CONCLUSION | 258 |

INTERIOR POINT ALGORITHMS BARRIER METHODS | 261 |

82 PRIMAL PATH FOLLOWING | 266 |

83 DUAL PATH FOLLOWING | 272 |

84 PRIMALDUAL PATH FOLLOWING | 277 |

85 POLYNOMIAL TERMINATION OF PATH FOLLOWING ALGORITHMS | 283 |

86 RELATION TO POLYHEDRAL TRANSFORMATION ALGORITHMS | 292 |

87 PREDICTORCORRECTOR ALGORITHMS | 297 |

88 OTHER ISSUES | 300 |

89 CONCLUSION | 306 |

810 EXERCISES | 310 |

INTEGER PROGRAMMING | 313 |

92 MODELING WITH INTEGER VARIABLES | 314 |

93 BRANCHANDBOUND | 319 |

94 NODE AND VARIABLE SELECTION | 324 |

95 MORE GENERAL BRANCHING | 328 |

96 CONCLUSION | 341 |

SOLVING LARGE SCALE PROBLEMS DECOMPOSITION METHODS | 347 |

PROJECTION BENDERS DECOMPOSITION | 349 |

102 THE BENDERS ALGORITHM | 350 |

115 COMPUTATIONAL ISSUES | 386 |

116 CONCLUSION | 390 |

117 EXERCISES | 391 |

LAGRANGIAN METHODS | 393 |

122 THE LAGRANGIAN DUAL | 394 |

123 EXTENSION TO INTEGER PROGRAMMING | 398 |

124 PROPERTIES OF THE LAGRANGIAN DUAL | 402 |

125 OPTIMIZING THE LAGRANGIAN DUAL | 408 |

126 COMPUTATIONAL ISSUES | 426 |

127 A DECOMPOSITION ALGORITHM FOR INTEGER PROGRAMMING | 429 |

128 CONCLUSION | 434 |

129 EXERCISES | 435 |

SOLVING LARGE SCALE PROBLEMS USING SPECIAL STRUCTURE | 437 |

SPARSE METHODS | 439 |

133 SPARSE LU UPDATE | 446 |

134 NUMERIC CHOLESKY FACTORIZATION | 462 |

135 SYMBOLIC CHOLESKY FACTORIZATION | 466 |

136 STORING SPARSE MATRICES | 471 |

137 PROGRAMMING ISSUES | 472 |

BARRIER VERSUS SIMPLEX | 478 |

139 CONCLUSION | 479 |

1310 EXERCISES | 480 |

NETWORK FLOW LINEAR PROGRAMS | 481 |

142 TOTALLY UNIMODULAR LINEAR PROGRAMS | 482 |

143 NETWORK SIMPLEX ALGORITHM | 493 |

144 IMPORTANT NETWORK FLOW PROBLEMS | 505 |

145 ALMOST NETWORK PROBLEMS | 513 |

146 INTEGER POLYHEDRA | 515 |

147 CONCLUSION | 523 |

148 EXERCISES | 524 |

LARGE INTEGER PROGRAMS PREPROCESSING AND CUTTING PLANES | 527 |

152 PREPROCESSING | 533 |

153 CUTTING PLANES | 542 |

154 BRANCHANDCUT | 555 |

155 LIFTING | 557 |

156 LAGRANGIAN CUTS | 560 |

157 INTEGER PROGRAMMING TEST PROBLEMS | 561 |

158 CONCLUSION | 562 |

159 EXERCISES | 563 |

LARGE INTEGER PROGRAMS PROJECTION AND INVERSE PROJECTION | 565 |

162 AUXILIARY VARIABLE METHODS | 573 |

163 A PROJECTION THEOREM | 601 |

BENDERS DECOMPOSITION REVISITED | 613 |

166 CONCLUSION | 630 |

APPENDIX | 633 |

POLYHEDRAL THEORY | 635 |

A3 FACES OF POLYHEDRA | 640 |

A4 FINITE BASIS THEOREMS | 645 |

A5 INNER PRODUCTS SUBSPACES AND ORTHOGONAL SUBSPACES | 651 |

A6 EXERCISES | 653 |

COMPLEXITY THEORY | 657 |

B2 SOLUTION SIZES | 660 |

B3 THE TURING MACHINE | 661 |

B4 COMPLEXITY CLASSES | 663 |

B5 SATISFIABILITY | 667 |

B6 ATCOMPLETENESS | 669 |

B7 COMPLEXITY OF GAUSSIAN ELIMINATION | 670 |

B8 EXERCISES | 674 |

BASIC GRAPH THEORY | 677 |

SOFTWARE AND TEST PROBLEMS | 681 |

NOTATION | 683 |

687 | |

723 | |

731 | |

### Other editions - View all

Large Scale Linear and Integer Optimization: A Unified Approach Richard Kipp Martin Limited preview - 2012 |

Large Scale Linear and Integer Optimization: A Unified Approach Richard Kipp Martin No preview available - 2012 |

Large Scale Linear and Integer Optimization: A Unified Approach Richard Kipp Martin No preview available - 1998 |

### Common terms and phrases

Assume auxiliary variables basic feasible solution basic variable Benders binary branch-and-bound calculate candidate problem Chapter column cone conv(r convex convex hull corresponding decomposition defined dual variables equation Euclidean algorithm Example extreme point extreme ray formulation Gaussian elimination given graph Hermite normal form implies inequalities infeasible integer linear program integer polyhedron integer programming integer solution integer variables integer vector inverse projection iteration Karmarkar's algorithm knapsack knapsack problem Lagrangian dual Lemma linear programming relaxation lower bound LU decomposition method min{cTx minimal mixed integer network flow network flow problem nonbasic variables nonnegative nonzero elements objective function value optimal solution value path following algorithm pivot polyhedral polynomial polytope primal solution Proof Proposition restricted master result revised simplex right hand side Section simplex algorithm slack solving Step subproblem subset system Ax update upper bound variable xi vertex zero

### Popular passages

Page 714 - An Integer Programming Approach to Scheduling. In A. Wren, editor, Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling, pages 269-280, North-Holland, Amsterdam.

Page 693 - Desrochers, M., and Soumis, F., "A column generation approach to the urban transit crew scheduling problem", Transportation Science 23 (1989) 1-13.

Page 714 - IE Grossmann, Reformulation of the multiperiod MILP model for capacity expansion of chemical processes, Operations Research 40 (SI) (1992) S127-S144.

Page 693 - JH Dreze and D. de la Vallee Poussin, "A Tatonnement Process for Guiding and Financing an Efficient Production of Public Goods," Discussion Paper 6922, CORE, Univ.

Page 717 - Global convergence of the affine scaling methods for degenerate linear programming problems.

Page 712 - CJ Piper and AA Zoltners, Some easy postoptimality analysis for zero-one programming, Management Sci.