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

This is a textbook about linear and integer linear optimization. There is a growing need in industries such as airline, trucking, and financial engineering to solve very large linear and integer linear optimization problems. Building these models requires uniquely trained individuals. Not only must they have a thorough understanding of the theory behind mathematical programming, they must have substantial knowledge of how to solve very large models in today's computing environment. The major goal of the book is to develop the theory of linear and integer linear optimization in a unified manner and then demonstrate how to use this theory in a modern computing environment to solve very large real world problems. After presenting introductory material in Part I, Part II of this book is de­ voted to the theory of linear and integer linear optimization. This theory is developed using two simple, but unifying ideas: projection and inverse projec­ tion. Through projection we take a system of linear inequalities and replace some of the variables with additional linear inequalities. Inverse projection, the dual of this process, involves replacing linear inequalities with additional variables. Fundamental results such as weak and strong duality, theorems of the alternative, complementary slackness, sensitivity analysis, finite basis the­ orems, etc. are all explained using projection or inverse projection. Indeed, a unique feature of this book is that these fundamental results are developed and explained before the simplex and interior point algorithms are presented.

---

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.

---

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.
Content:
Front Matter....Pages i-xvii
Front Matter....Pages 1-1
Linear and Integer Linear Optimization....Pages 3-32
Front Matter....Pages 33-33
Linear Systems and Projection....Pages 35-80
Linear Systems and Inverse Projection....Pages 81-101
Integer Linear Systems: Projection and Inverse Projection....Pages 103-139
Front Matter....Pages 141-141
The Simplex Algorithm....Pages 143-181
More on Simplex....Pages 183-217
Interior Point Algorithms: Polyhedral Transformations....Pages 219-260
Interior Point Algorithms: Barrier Methods....Pages 261-311
Integer Programming....Pages 313-346
Front Matter....Pages 347-347
Projection: Benders’ Decomposition....Pages 349-367
Inverse Projection: Dantzig-Wolfe Decomposition....Pages 369-392
Lagrangian Methods....Pages 393-436
Front Matter....Pages 437-437
Sparse Methods....Pages 439-480
Network Flow Linear Programs....Pages 481-525
Large Integer Programs: Preprocessing and Cutting Planes....Pages 527-564
Large Integer Programs: Projection and Inverse Projection....Pages 565-632
Back Matter....Pages 633-740

---

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.
Content:
Front Matter....Pages i-xvii
Front Matter....Pages 1-1
Linear and Integer Linear Optimization....Pages 3-32
Front Matter....Pages 33-33
Linear Systems and Projection....Pages 35-80
Linear Systems and Inverse Projection....Pages 81-101
Integer Linear Systems: Projection and Inverse Projection....Pages 103-139
Front Matter....Pages 141-141
The Simplex Algorithm....Pages 143-181
More on Simplex....Pages 183-217
Interior Point Algorithms: Polyhedral Transformations....Pages 219-260
Interior Point Algorithms: Barrier Methods....Pages 261-311
Integer Programming....Pages 313-346
Front Matter....Pages 347-347
Projection: Benders’ Decomposition....Pages 349-367
Inverse Projection: Dantzig-Wolfe Decomposition....Pages 369-392
Lagrangian Methods....Pages 393-436
Front Matter....Pages 437-437
Sparse Methods....Pages 439-480
Network Flow Linear Programs....Pages 481-525
Large Integer Programs: Preprocessing and Cutting Planes....Pages 527-564
Large Integer Programs: Projection and Inverse Projection....Pages 565-632
Back Matter....Pages 633-740
....