# Large Scale Linear and Integer Optimization: A Unified Approach: A Unified Approach

Springer Science & Business Media, 1999 - Business & Economics - 740 pages
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.

### 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 REFERENCES 687 AUTHOR INDEX 723 TOPIC INDEX 731 Copyright

### 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.