#
Linear and Integer Optimization

Theory and Practice, Third Edition

## Preview

## Book Description

Presenting a strong and clear relationship between theory and practice**, Linear and Integer Optimization: Theory and Practice **is divided into two main parts. The first covers the theory of linear and integer optimization, including both basic and advanced topics. Dantzig’s simplex algorithm, duality, sensitivity analysis, integer optimization models, and network models are introduced.

More advanced topics also are presented including interior point algorithms, the branch-and-bound algorithm, cutting planes, complexity, standard combinatorial optimization models, the assignment problem, minimum cost flow, and the maximum flow/minimum cut theorem.

The second part applies theory through real-world case studies. The authors discuss advanced techniques such as column generation, multiobjective optimization, dynamic optimization, machine learning (support vector machines), combinatorial optimization, approximation algorithms, and game theory.

Besides the fresh new layout and completely redesigned figures, this new edition incorporates modern examples and applications of linear optimization. The book now includes computer code in the form of models in the GNU Mathematical Programming Language (GMPL). The models and corresponding data files are available for download and can be readily solved using the provided online solver.

This new edition also contains appendices covering mathematical proofs, linear algebra, graph theory, convexity, and nonlinear optimization. All chapters contain extensive examples and exercises. This textbook is ideal for courses for advanced undergraduate and graduate students in various fields including mathematics, computer science, industrial engineering, operations research, and management science.

## Table of Contents

**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

**Introduction to Computational Complexity**

Computational Complexity

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

**Formulating the Problem**

Minimizing Trimloss When Cutting Cardboard

Minimizing Trimloss When Cutting Cardboard

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)

Appendix B Linear Algebra

Appendix C Graph Theory

Appendix D Convexity

Appendix E Nonlinear Optimization

Appendix F Writing LO-Models in GNU MathProg (GMPL)

## Author(s)

### Biography

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

## Reviews

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)