3rd Edition

Linear and Integer Optimization Theory and Practice, Third Edition

By Gerard Sierksma, Yori Zwols Copyright 2015
    686 Pages 175 B/W Illustrations
    by Chapman & Hall

    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.

    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


    Geometry and Algebra of Feasible Regions
    The Geometry of Feasible Regions
    Algebra of Feasible Regions; Feasible Basic Solutions

    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
    Uniqueness and Multiple Optimal Solutions
    Models with Equality Constraints
    The Revised Simplex Algorithm

    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

    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

    Large-Scale Linear Optimization
    The Interior Path
    Formulation of the Interior Path Algorithm
    Convergence to the Interior Path; Maintaining Feasibility
    Termination and Initialization

    Integer Linear Optimization
    The Branch-and-Bound Algorithm
    Linearizing Logical Forms with Binary Variables
    Gomory’s Cutting-Plane Algorithm

    Linear Network Models
    LO-Models with Integer Solutions; Total Unimodularity
    ILO-Models with Totally Unimodular Matrices
    The Network Simplex Algorithm

    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


    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

    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

    Production Planning; A Single Product Case
    Model Description
    Regular Working Hours
    Allowing Overtime and Idle Time
    Sensitivity Analysis
    GMPL Model Code

    Production of Coffee Machines
    Problem Setting
    An LO-Model that Minimizes Backlogs
    Old and Recent Backlogs
    Full Week Productions
    Sensitivity Analysis
    GMPL Model Code

    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

    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

    Minimizing Trimloss When Cutting Cardboard
    Formulating the Problem
    Gilmore-Gomory’s Solution Algorithm
    Calculating an Optimal Solution

    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

    The Catering Service Problem
    Formulation of the Problem
    The Transshipment Problem Formulation
    Applying the Network Simplex Algorithm
    Sensitivity Analysis
    GMPL Model Code

    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)


    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)