Linear and Integer Optimization Theory and Practice, Third Edition

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)

Biography

Gerard Sierksma, PhD, University of Groningen, The Netherlands
Yori Zwols, PhD, Google UK, London

Praise for the first edition:

"...very recommendable as a textbook and to anybody wishing to learn the topic."
—Optimization (1997)

"...the book is a nice balance between theory and applications...and gives a sound background for the techniques used and for investigating real problems."
—Zentralblatt für Mathematik (1998)