Applied Integer Programming: Modeling and Solution -- CONTENTS -- PREFACE -- PART I MODELING -- 1 Introduction -- 1.1 Integer Programming -- 1.2 Standard Versus Nonstandard Forms -- 1.3 Combinatorial Optimization Problems -- 1.4 Successful Integer Programming Applications -- 1.5 Text Organization and Chapter Preview -- 1.6 Notes -- 1.7 Exercises -- 2 Modeling and Models -- 2.1 Assumptions on Mixed Integer Programs -- 2.2 Modeling Process -- 2.3 Project Selection Problems -- 2.3.1 Knapsack Problem -- 2.3.2 Capital Budgeting Problem -- 2.4 Production Planning Problems -- 2.4.1 Uncapacitated Lot Sizing -- 2.4.2 Capacitated Lot Sizing -- 2.4.3 Just-in-Time Production Planning -- 2.5 Workforce/Staff Scheduling Problems -- 2.5.1 Scheduling Full-Time Workers -- 2.5.2 Scheduling Full-Time and Part-Time Workers -- 2.6 Fixed-Charge Transportation and Distribution Problems -- 2.6.1 Fixed-Charge Transportation -- 2.6.2 Uncapacitated Facility Location -- 2.6.3 Capacitated Facility Location -- 2.7 Multicommodity Network Flow Problem -- 2.8 Network Optimization Problems with Side Constraints -- 2.9 Supply Chain Planning Problems -- 2.10 Notes -- 2.11 Exercises -- 3 Transformation Using 0-1 Variables -- 3.1 Transform Logical (Boolean) Expressions -- 3.1.1 Truth Table of Boolean Operations -- 3.1.2 Basic Logical (Boolean) Operations on Variables -- 3.1.3 Multiple Boolean Operations on Variables -- 3.2 Transform Nonbinary to 0-1 Variable -- 3.2.1 Transform Integer Variable -- 3.2.2 Transform Discrete Variable -- 3.3 Transform Piecewise Linear Functions -- 3.3.1 Arbitrary Piecewise Linear Functions -- 3.3.2 Concave Piecewise Linear Cost Functions: Economy of Scale -- 3.4 Transform 0-1 Polynomial Functions -- 3.5 Transform Functions with Products of Binary and Continuous Variables: Bundle Pricing Problem -- 3.6 Transform Nonsimultaneous Constraints.

3.6.1 Either/Or Constraints -- 3.6.2 p Out of m Constraints Must Hold -- 3.6.3 Disjunctive Constraint Sets -- 3.6.4 Negation of a Constraint -- 3.6.5 If/Then Constraints -- 3.7 Notes -- 3.8 Exercises -- 4 Better Formulation by Preprocessing -- 4.1 Better Formulation -- 4.2 Automatic Problem Preprocessing -- 4.3 Tightening Bounds on Variables -- 4.3.1 Bounds on Continuous Variables -- 4.3.2 Bounds on General Integer Variables -- 4.3.3 Bounds on 0-1 Variables -- 4.3.4 Variable Fixing Redundant Constraints, and Infeasibility -- 4.4 Preprocessing Pure 0-1 Integer Programs -- 4.4.1 Fixing 0-1 Variables -- 4.4.2 Detecting Redundant Constraints And Infeasibility -- 4.4.3 Tightening Constraints (or Coefficients Reduction) -- 4.4.4 Generating Cutting Planes from Minimum Cover -- 4.4.5 Rounding by Division with GCD -- 4.5 Decomposing a Problem into Independent Subproblems -- 4.6 Scaling the Coefficient Matrix -- 4.7 Notes -- 4.8 Exercises -- 5 Modeling Combinatorial Optimization Problems I -- 5.1 Introduction -- 5.2 Set Covering and Set Partitioning -- 5.2.1 Set Covering Problem -- 5.2.2 Set Partitioning and Set Packing -- 5.2.3 Set Covering in Networks -- 5.2.4 Applications of Set Covering Problem -- 5.3 Matching Problem -- 5.3.1 Matching Problems in Network -- 5.3.2 Integer Programming Formulation -- 5.4 Cutting Stock Problem -- 5.4.1 One-Dimensional Case -- 5.4.2 Two-Dimensional Case -- 5.5 Comparisons for Above Problems -- 5.6 Computational Complexity of COP -- 5.6.1 Problem Versus Problem Instance -- 5.6.2 Computational Complexity of an Algorithm -- 5.6.3 Polynomial Versus Nonpolynomial Function -- 5.7 Notes -- 5.8 Exercises -- 6 Modeling Combinatorial Optimization Problems II -- 6.1 Importance of Traveling Salesman Problem -- 6.2 Transformations to Traveling Salesman Problem -- 6.2.1 Shortest Hamiltonian Paths -- 6.2.2 TSP with Repeated City Visits.

6.2.3 Multiple Traveling Salesmen Problem -- 6.2.4 Clustered TSP -- 6.2.5 Generalized TSP -- 6.2.6 Maximum TSP -- 6.3 Applications of TSP -- 6.3.1 Machine Sequencing Problems in Various Manufacturing Systems -- 6.3.2 Sequencing Problems in Electronic Industry -- 6.3.3 Vehicle Routing for Delivery/Dispatching -- 6.3.4 Genome Sequencing for Genetic Study -- 6.4 Formulating Asymmetric TSP -- 6.4.1 Subtour Elimination by Dantzig-Fulkerson-Johnson Constraints -- 6.4.2 Subtour Elimination by Miller-Tucker-Zemlin (MTZ) Constraints -- 6.5 Formulating Symmetric TSP -- 6.6 Notes -- 6.7 Exercises -- PART II REVIEW OF LINEAR PROGRAMMING AND NETWORK FLOWS -- 7 Linear Programming-Fundamentals -- 7.1 Review of Basic Linear Algebra -- 7.1.1 Euclidean Space -- 7.1.2 Linear and Convex Combinations -- 7.1.3 Linear Independence -- 7.1.4 Rank of a Matrix -- 7.1.5 Basis -- 7.1.6 Matrix Inversion -- 7.1.7 Determinant of a Matrix -- 7.1.8 Upper and Lower Triangular Matrices -- 7.2 Uses of Elementary Row Operations -- 7.2.1 Finding the Rank of a Matrix -- 7.2.2 Calculating the Inverse of a Matrix -- 7.2.3 Converting to a Triangular Matrix -- 7.2.4 Calculating the Determinant of a Matrix -- 7.2.5 Solving a System of Linear Equations -- 7.3 The Dual Linear Program -- 7.3.1 The Linear Program in Standard Form -- 7.3.2 Formulating the Dual Problem -- 7.3.3 Economic Interpretation of the Dual -- 7.3.4 Importance of the Dual -- 7.4 Relationships Between Primal and Dual Solutions -- 7.4.1 Relationships Between All Primal and All Dual Feasible Solutions -- 7.4.2 Relationship Between Primal and Dual Optimum Solutions -- 7.4.3 Relationships Between Each Complementary Pair of Variables at Optimum -- 7.5 Notes -- 7.6 Exercises -- 8 Linear Programming: Geometric Concepts -- 8.1 Geometric Solution -- 8.1.1 Objective Function -- 8.1.2 Solution Space -- 8.1.3 Requirement Space.

8.2 Convex Sets -- 8.2.1 Convex Sets and Polyhedra -- 8.2.2 Directions of Unbounded Convex Sets -- 8.2.3 Convex and Polyhedral Cones -- 8.2.4 Convex and Concave Functions -- 8.3 Describing a Bounded Polyhedron -- 8.3.1 Representation by Extreme Points -- 8.3.2 Example Application of Representation Theorem -- 8.4 Describing Unbounded Polyhedron -- 8.4.1 Finding Extreme Direction Algebraically -- 8.4.2 Representing by Extreme Points and Extreme Directions -- 8.4.3 Example of Representation Theorem -- 8.5 Faces Facets and Dimension of a Polyhedron -- 8.6 Describing a Polyhedron by Facets -- 8.7 Correspondence Between Algebraic and Geometric Terms -- 8.8 Notes -- 8.9 Exercises -- 9 Linear Programming: Solution Methods -- 9.1 Linear Programs in Canonical Form -- 9.2 Basic Feasible Solutions and Reduced Costs -- 9.2.1 Basic Feasible Solution -- 9.2.2 Adjacent Basic Feasible Solution -- 9.2.3 Reduced Costs -- 9.3 The Simplex Method -- 9.3.1 Better and Feasible Solution -- 9.3.2 Updating Simplex Tableau by Pivoting -- 9.3.3 Optimality Test -- 9.3.4 Initial Basic Feasible Solution -- 9.4 Interpreting the Simplex Tableau -- 9.4.1 Entire Simplex Tableau -- 9.4.2 Rows of Simplex Tableau -- 9.4.3 Columns of Simplex Tableau -- 9.4.4 Pivot Column and Pivot Row -- 9.4.5 Predicting the New Objective Value Before Updating -- 9.5 Geometric Interpretation of the Simplex Method -- 9.5.1 Basic Feasible Solution Versus Extreme Point -- 9.5.2 Explanation of "Simplex Method" Nomenclature -- 9.5.3 Identifying an Extreme Ray in a Simplex Tableau -- 9.6 The Simplex Method for Upper Bounded Variables -- 9.7 The Dual Simplex Method -- 9.8 The Revised Simplex Method -- 9.9 Notes -- 9.10 Exercises -- 10 Network Optimization Problems and Solutions -- 10.1 Network Fundamentals -- 10.2 A Class of Easy Network Problems -- 10.2.1 The Minimum Cost Network Flow Problem.

10.2.2 Formulating the Transportation-Assignment Problem as an MCNF Problem -- 10.2.3 Formulating the Transshipment Problem as an MCNF Problem -- 10.2.4 Formulating the Maximum Flow Problem as an MCNF Problem -- 10.2.5 Formulating the Shortest Path Problem as an MCNF Problem -- 10.3 Totally Unimodular Matrices -- 10.3.1 Definition -- 10.3.2 Sufficient Condition for a Totally Unimodular Matrix -- 10.3.3 Some Properties of Totally Unimodular Matrices -- 10.3.4 Matrix Structure of the MCNF Problem -- 10.3.5 Lower Triangular Matrix and Forward Substitution -- 10.3.6 Naturally Integer Solution for the MCNF Problem -- 10.4 The Network Simplex Method -- 10.4.1 Feasible Spanning Trees Versus Basic Feasible Solutions -- 10.4.2 The Network Algorithm -- 10.4.3 Numerical Example -- 10.5 Solution via LINGO -- 10.6 Notes -- 10.7 Exercises -- PART III SOLUTIONS -- 11 Classical Solution Approaches -- 11.1 Branch-and-Bound Approach -- 11.1.1 Basic Concepts -- 11.1.2 Branch-and-Bound Algorithm -- 11.2 Cutting Plane Approach -- 11.2.1 Dual Cutting Plane Approach -- 11.2.2 Fractional Cutting Plane Method -- 11.2.3 Mixed Integer Cutting Plane Method -- 11.3 Group Theoretic Approach -- 11.3.1 Group Theory Terminology -- 11.3.2 Deriving the Group (Minimization) Problem -- 11.3.3 Formulating a Group Problem -- 11.3.4 Solving Group Problem as a Shortest Route Problem -- 11.3.5 Solving the Original Integer Program -- 11.4 Geometric Concepts -- 11.4.1 Various Polyhedrons in Original Space -- 11.4.2 Corner Polyhedron in Solution Space of Nonbasic Variables -- 11.5 Notes -- 11.6 Exercises -- 12 Branch-and-Cut Approach -- 12.1 Introduction -- 12.1.1 Basic Concept -- 12.1.2 Branch-and-Cut Algorithm -- 12.1.3 Generating Valid Cuts and Preprocessing -- 12.2 Valid Inequalities -- 12.2.1 Valid Inequalities for Linear Programs -- 12.2.2 Valid Inequalities for Integer Programs.

12.2.3 Types of Valid Inequalities.