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

Front Cover
Springer Science & Business Media, 1999 - Business & Economics - 740 pages
0 Reviews
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

Other editions - View all

Common terms and phrases

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.

References to this book

All Book Search results »

About the author (1999)

Martin, Graduate School of Business, University of Chicago, IL, USA.

Bibliographic information