Linear and Integer Optimization

Basic Concepts of Linear Optimization The Company Dovetail Definition of an LO-Model Alternatives of the Standard LO-Model Solving LO-Models Using a Computer Package Linearizing Nonlinear Functions Examples of Linear Optimization Models Building and Implementing Mathematical Models Exercises LINEAR OPTIMIZATION THEORY: BASIC TECHNIQUES Geometry and Algebra of Feasible Regions The Geometry of Feasible Regions Algebra of Feasible Regions; Feasible Basic Solutions Exercises Dantzig's Simplex Algorithm From Vertex to Vertex to an Optimal Solution LO-Model Reformulation The Simplex Algorithm Simplex Tableaus Discussion of the Simplex Algorithm Initialization Uniqueness and Multiple Optimal Solutions Models with Equality Constraints The Revised Simplex Algorithm Exercises Duality, Feasibility, and Optimality The Companies Dovetail and Salmonnose Duality and Optimality Complementary Slackness Relations Infeasibility and Unboundedness; Farkas' Lemma Primal and Dual Feasible Basic Solutions Duality and the Simplex Algorithm The Dual Simplex Algorithm Exercises Sensitivity Analysis Sensitivity of Model Parameters Perturbing Objective Coefficients Perturbing Right Hand Side Values (Nondegenerate Case) Piecewise Linearity of Perturbation Functions Perturbation of the Technology Matrix Sensitivity Analysis for the Degenerate Case Shadow Prices and Redundancy of Equality Constraints Exercises Large-Scale Linear Optimization The Interior Path Formulation of the Interior Path Algorithm Convergence to the Interior Path; Maintaining Feasibility Termination and Initialization Exercises Integer Linear Optimization Introduction The Branch-and-Bound Algorithm Linearizing Logical Forms with Binary Variables Gomory's Cutting-Plane Algorithm Exercises Linear Network Models LO-Models with Integer Solutions; Total Unimodularity ILO-Models with Totally Unimodular Matrices The Network Simplex Algorithm Exercises Computational Complexity Introduction to Computational Complexity Computational Aspects of Dantzig's Simplex Algorithm The Interior Path Algorithm Has Polynomial Running Time Computational Aspects of the Branch-and-Bound Algorithm Exercises LINEAR OPTIMIZATION PRACTICE: ADVANCED TECHNIQUES Designing a Reservoir for Irrigation The Parameters and the Input Data Maximizing the Irrigation Area Changing the Input Parameters of the Model GMPL Model Code Exercises Classifying Documents by Language Machine Learning Classifying Documents Using Separating Hyperplanes LO-Model for Finding Separating Hyperplane Validation of a Classifier Robustness of Separating Hyperplanes; Separation Width Models that Maximize the Separation Width GMPL Model Code Exercises Production Planning; A Single Product Case Model Description Regular Working Hours Overtime Allowing Overtime and Idle Time Sensitivity Analysis GMPL Model Code Exercises Production of Coffee Machines Problem Setting An LO-Model that Minimizes Backlogs Old and Recent Backlogs Full Week Productions Sensitivity Analysis GMPL Model Code Exercises Conflicting Objectives: Producing Versus Importing Problem Description and Input Data Modeling Two Conflicting Objectives; Pareto Optimal Point Goal Optimization for Conflicting Objective Soft and Hard Constraints Sensitivity Analysis Alternative Solution Techniques A Comparison of the Solutions GMPL Model Code Exercises Coalition Formation and Profit Distribution The Farmers Cooperation Problem Game Theory; Linear Production Games How to Distribute the Total Profit Among the Farmers? Profit Distribution for Arbitrary Numbers of Farmers Sensitivity Analysis Exercises Minimizing Trimloss When Cutting Cardboard Formulating the Problem Gilmore-Gomory's Solution Algorithm Calculating an Optimal Solution Exercises Off-Shore Helicopter Routing Problem Description Vehicle Routing Problems Problem Formulation ILO Formulation Column Generation Dual Values as Price Indicators for Crew Exchanges A Round-Off Procedure for Determining an Integer Solution Computational Experiments Sensitivity Analysis Exercises The Catering Service Problem Formulation of the Problem The Transshipment Problem Formulation Applying the Network Simplex Algorithm Sensitivity Analysis GMPL Model Code Exercises Appendix A Mathematical Proofs Appendix B Linear Algebra Appendix C Graph Theory Appendix D Convexity Appendix E Nonlinear Optimization Appendix F Writing LO-Models in GNU MathProg (GMPL)