Applied Integer Programming Modeling and Solution

by Chen, Der-San; Batson, Robert G.; Dang, Yu

• ISBN13: 9780470373064
• ISBN10: 0470373067
• Edition: 1st
• Format: Hardcover
• Copyright: 2010-01-12
• Publisher: Wiley

Summary

The application-oriented approach of this book addresses the art and science of mathematical modeling for the collection of problems that fit the MIP framework and also discusses the algorithms and associated practices that enable those models to be solved most efficiently. Throughout the book, reasoning and interpretation are exercised more often than rigorous mathematical proofs of theorems, which may be located in referenced articles. The authors have been very thorough in searching out and synthesizing various modeling and solution approaches that have appeared in disparate publications over the past 40 years. This book is a well-organized and comprehensive reference that eases the learning hurdles in integer programming and provides suggestions/guidelines for practice on the job. This book is organized in three parts: modeling, review of linear programming (LP) and network flows, and solutions. The first part (Chapters 1-6) includes areas of successful MIP applications, systematic modeling procedures, typical types of models, transformation of non-MIP models, automatic preprocessing for getting better formulation, and modeling of combinatorial optimization problems. The second part (Chapters 7-10) presents algebraic and geometric basic concepts of LP theory and network flows needed for understanding integer programming. The final part (Chapters 11-17) addresses classical and modern solution approaches as well as the key components that build an integrated software system capable of solving large-scale integer programming and combinatorial optimization problems. Three commercial modeling languages for large-scale IP problems are introduced in appendices.

Author Biography

Der-San Chen, PhD, is Professor Emeritus in the Department of Industrial Engineering at The University of Alabama. He has over thirty years of academic and consulting experience on the applications of linear programming, integer programming, optimization, and decision support systems. Dr. Chen currently focuses his research on modeling optimization problems arising in production, transportation, distribution, supply chain management, and the application of optimization and statistical software for problem solving.

Robert G. Batson, PhD, PE, is Professor of Construction Engineering at The University of Alabama, where he is also Director of Industrial Engineering Programs. A Fellow of the American Society for Quality Control, Dr. Batson has written numerous journal articles in his areas of research interest, which include operations research, applied statistics, and supply chain management.

Yu Dang, PhD, is Qualitative Manufacturing Analyst at Quickparts.com, a manufacturing services company that provides customers with an online e-commerce system to procure custom manufactured parts. She received her PhD in operations management from The University of Alabama in 2004.

Table of Contents

Modeling

Introduction

Integer Programming

Standard vs. Non-Standard Forms

Combinatorial Optimization Problems

Successful Integer Programming Applications

Text Organization and Chapter Preview

Notes

Exercises

Modeling and Models

Assumptions on Mixed Integer Programs

Modeling Process

Project Selection Problems

Knapsack problem

Capital budgeting problem

Production Planning Problems

Workforce/Staff Scheduling Models

Fixed-Charge Transportation and Distribution Problems

Multi-Commodity Network Flow Problem

Network Optimization Problems with Side Constraints

Supply Chain Planning Problems

Notes

Exercises

Transformation Using 0-1 Variables

Transform Logical (Boolean) Expressions

Transform Non-Binary to Binary Variables

Transform Piecewise Linear Functions

Transform 0-1 Polynomial Functions

Transform Nonlinear Functions

Transform Non-Simultaneous Constraints

Notes

Exercises

Better Formulation by Preprocessing

Better Formulation

Automatic Problem Preprocessing

Tightening Bounds on Variables

Preprocessing Pure 0-1 Integer Programs

Decomposing Problem into Independent Sub-Problems

Scaling the Coefficient Matrix

Notes

Exercises

Combinatorial Optimization I

Introduction

Set Covering, Set Partitioning, and Set Packing

Matching Problem

Cutting Stock Problem

Comparisons for Above Problems

Computational Complexity of COP

Notes

Exercises

Combinatorial Optimization II

Importance of Traveling Salesman Problem

Transformations to Traveling Salesman Problem

Applications of Traveling Salesman Problem

Formulating Asymmetric TSP

Formulating Symmetric TSP

Notes

Exercises

Review of Linear Programming and Network Flows

Linear Programming--Fundamentals

Review of Basic Linear Algebra

Uses of Elementary Row Operations

The Dual of a Linear Program

Relationships between Primal and Dual Solutions

Notes

Exercises

Linear Programming--Geometric Concepts

Geometric Solution

Convex Sets

Describing a Bounded Polyhedron

Describing an Unbounded Polyhedron

Faces, Facets, Dimension of a Polyhedron

Describing a Polyhedron by Facets

Correspondence between Algebraic and Geometric Terms

Notes

Exercises

Linear Programming--Solution Methods

Linear Programs in Canonical Form

Basic Feasible Solutions and Reduced Costs

The Simplex Method

Interpreting the Simplex Tableau

Geometric Interpretation of the Simplex Method

The Simplex Method for Upper-Bounded Variables

The Dual Simplex Method

The Revised Simplex Method

Notes

Exercises

Network Optimization Problems and Solutions

Network Fundamentals

Class of Easy Network Optimization Problems

Totally Unimodular Matrices

The Network Simplex Method

Solution via LINGO

Notes

Exercises

Solutions

Classical Solution Approaches

Branch-and-Bound Approach

Cutting Plane Approach

Group Theoretic Approach

Geometric Concepts

Notes

Exercises

Branch-and-Cut Approach

Introduction

Valid Inequalities

Cut Generating Techniques

Rounding

Cuts Generated from Sets Involving Pure Integer Variables

Cuts Generated from Sets Involving Mixed Integer Variables

Cuts Generated from 0-1 Knapsack Sets

Cuts Generated from Sets Involving 0-1 Coefficients and Variables

Cuts Generated from Sets with Special Structures

Notes

Exercises

Branch-and-Price Approach

Concepts of Branch-and-Price

Dantzig-Wolfe Decomposition

Generalized Assignment Problem (GAP)

GAP Example

Other Application Areas

Notes

Exercises

Solution via Heuristics and Relaxations

Introduction

Overall Solution Strategy

Primal Solution via Heuristics

Dual Solution via Relaxations

Lagrangian Dual

Primal-Dual Solution via Benders? Partitioning

Notes

Exercises

Solutions with Commercial Software

Introduction

Typical IP Software System Components

AMPL Modeling Language

LINGO Modeling Language

MPL Modeling Language

Appendix--Answers to Selected Exercises

Bibliography

Index

Table of Contents provided by Publisher. All Rights Reserved.