Linear and Integer Optimization: Theory and Practice, Third Edition, 3rd Edition (Hardback) book cover

Linear and Integer Optimization

Theory and Practice, Third Edition, 3rd Edition

By Gerard Sierksma, Gerard Sierksma, Yori Zwols

Chapman and Hall/CRC

686 pages | 175 B/W Illus.

Purchasing Options:$ = USD
Hardback: 9781498710169
pub: 2015-05-01
SAVE ~$27.00
$135.00
$108.00
x
eBook (VitalSource) : 9780429159961
pub: 2015-05-01
from $67.50


FREE Standard Shipping!

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.

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)

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

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)

About the Authors

Gerard Sierksma, PhD, University of Groningen, The Netherlands

Yori Zwols, PhD, Google UK, London

About the Series

Advances in Applied Mathematics

Learn more…

Subject Categories

BISAC Subject Codes/Headings:
BUS049000
BUSINESS & ECONOMICS / Operations Research
MAT000000
MATHEMATICS / General
TEC029000
TECHNOLOGY & ENGINEERING / Operations Research