| |
| |
| |
| Modeling | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Integer Programming | |
| |
| |
| |
| Standard vs. Non-Standard Forms | |
| |
| |
| |
| Combinatorial Optimization Problems | |
| |
| |
| |
| Successful Integer Programming Applications | |
| |
| |
| |
| Text Organization and Chapter Preview | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Modeling and Models | |
| |
| |
| |
| Assumptions on Mixed Integer Programs | |
| |
| |
| |
| Modeling Process | |
| |
| |
| |
| Project Selection Problems | |
| |
| |
| |
| Knapsack problem | |
| |
| |
| |
| Capital budgeting problem | |
| |
| |
| |
| Production Planning Problems | |
| |
| |
| |
| Workforce/Staff Scheduling Models | |
| |
| |
| |
| Fixed-Charge Transportation and Distribution Problems | |
| |
| |
| |
| Multi-Commodity Network Flow Problem | |
| |
| |
| |
| Network Optimization Problems with Side Constraints | |
| |
| |
| |
| Supply Chain Planning Problems | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Transformation Using 0-1 Variables | |
| |
| |
| |
| Transform Logical (Boolean) Expressions | |
| |
| |
| |
| Transform Non-Binary to Binary Variables | |
| |
| |
| |
| Transform Piecewise Linear Functions | |
| |
| |
| |
| Transform 0-1 Polynomial Functions | |
| |
| |
| |
| Transform Nonlinear Functions | |
| |
| |
| |
| Transform Non-Simultaneous Constraints | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Better Formulation by Preprocessing | |
| |
| |
| |
| Better Formulation | |
| |
| |
| |
| Automatic Problem Preprocessing | |
| |
| |
| |
| Tightening Bounds on Variables | |
| |
| |
| |
| Preprocessing Pure 0-1 Integer Programs | |
| |
| |
| |
| Decomposing Problem into Independent Sub-Problems | |
| |
| |
| |
| Scaling the Coefficient Matrix | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Combinatorial Optimization I | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Set Covering, Set Partitioning, and Set Packing | |
| |
| |
| |
| Matching Problem | |
| |
| |
| |
| Cutting Stock Problem | |
| |
| |
| |
| Comparisons for Above Problems | |
| |
| |
| |
| Computational Complexity of COP | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Combinatorial Optimization II | |
| |
| |
| |
| Importance of Traveling Salesman Problem | |
| |
| |
| |
| Transformations to Traveling Salesman Problem | |
| |
| |
| |
| Applications of Traveling Salesman Problem | |
| |
| |
| |
| Formulating Asymmetric TSP | |
| |
| |
| |
| Formulating Symmetric TSP | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Review of Linear Programming and Network Flows | |
| |
| |
| |
| Linear Programming--Fundamentals | |
| |
| |
| |
| Review of Basic Linear Algebra | |
| |
| |
| |
| Uses of Elementary Row Operations | |
| |
| |
| |
| The Dual of a Linear Program | |
| |
| |
| |
| Relationships between Primal and Dual Solutions | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Linear Programming--Geometric Concepts | |
| |
| |
| |
| Geometric Solution | |
| |
| |
| |
| Convex Sets | |
| |
| |
| |
| Describing a Bounded Polyhedron | |
| |
| |
| |
| Describing an Unbounded Polyhedron | |
| |
| |
| |
| Faces, Facets, Dimension of a Polyhedron | |
| |
| |
| |
| Describing a Polyhedron by Facets | |
| |
| |
| |
| Correspondence between Algebraic and Geometric Terms | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Linear Programming--Solution Methods | |
| |
| |
| |
| Linear Programs in Canonical Form | |
| |
| |
| |
| Basic Feasible Solutions and Reduced Costs | |
| |
| |
| |
| The Simplex Method | |
| |
| |
| |
| Interpreting the Simplex Tableau | |
| |
| |
| |
| Geometric Interpretation of the Simplex Method | |
| |
| |
| |
| The Simplex Method for Upper-Bounded Variables | |
| |
| |
| |
| The Dual Simplex Method | |
| |
| |
| |
| The Revised Simplex Method | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Network Optimization Problems and Solutions | |
| |
| |
| |
| Network Fundamentals | |
| |
| |
| |
| Class of Easy Network Optimization Problems | |
| |
| |
| |
| Totally Unimodular Matrices | |
| |
| |
| |
| The Network Simplex Method | |
| |
| |
| |
| Solution via LINGO | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Solutions | |
| |
| |
| |
| Classical Solution Approaches | |
| |
| |
| |
| Branch-and-Bound Approach | |
| |
| |
| |
| Cutting Plane Approach | |
| |
| |
| |
| Group Theoretic Approach | |
| |
| |
| |
| Geometric Concepts | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Branch-and-Cut Approach | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Valid Inequalities | |
| |
| |
| |
| Cut Generating Techniques | |
| |
| |
| |
| Rounding | |
| |
| |
| |
| Cuts Generated from Sets Involving Pure Integer Variables | |
| |
| |
| |
| Cuts Generated from Sets Involving Mixed Integer Variables | |
| |
| |
| |
| Cuts Generated from 0-1 Knapsack Sets | |
| |
| |
| |
| Cuts Generated from Sets Involving 0-1 Coefficients and Variables | |
| |
| |
| |
| Cuts Generated from Sets with Special Structures | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Branch-and-Price Approach | |
| |
| |
| |
| Concepts of Branch-and-Price | |
| |
| |
| |
| Dantzig-Wolfe Decomposition | |
| |
| |
| |
| Generalized Assignment Problem (GAP) | |
| |
| |
| |
| GAP Example | |
| |
| |
| |
| Other Application Areas | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Solution via Heuristics and Relaxations | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Overall Solution Strategy | |
| |
| |
| |
| Primal Solution via Heuristics | |
| |
| |
| |
| Dual Solution via Relaxations | |
| |
| |
| |
| Lagrangian Dual | |
| |
| |
| |
| Primal-Dual Solution via Benders? Partitioning | |
| |
| |
| |
| Notes | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Solutions with Commercial Software | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Typical IP Software System Components | |
| |
| |
| |
| AMPL Modeling Language | |
| |
| |
| |
| LINGO Modeling Language | |
| |
| |
| |
| MPL Modeling Language | |
| |
| |
| Appendix--Answers to Selected Exercises | |
| |
| |
| Bibliography | |
| |
| |
| Index | |