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

Applied Integer Programming (eBook, ePUB)

Modeling and Solution

• Format: ePub

Produktbeschreibung

An accessible treatment of the modeling and solution of integer programming problems, featuring modern applications and software In order to fully comprehend the algorithms associated with integer programming, it is important to understand not only how algorithms work, but also why they work. Applied Integer Programming features a unique emphasis on this point, focusing on problem modeling and solution using commercial software. Taking an application-oriented approach, this book addresses the art and science of mathematical modeling related to the mixed integer programming (MIP) framework and discusses the algorithms and associated practices that enable those models to be solved most efficiently. The book begins with coverage of successful applications, systematic modeling procedures, typical model types, transformation of non-MIP models, combinatorial optimization problem models, and automatic preprocessing to obtain a better formulation. Subsequent chapters present algebraic and geometric basic concepts of linear programming theory and network flows needed for understanding integer programming. Finally, the book concludes with classical and modern solution approaches as well as the key components for building an integrated software system capable of solving large-scale integer programming and combinatorial optimization problems. Throughout the book, the authors demonstrate essential concepts through numerous examples and figures. Each new concept or algorithm is accompanied by a numerical example, and, where applicable, graphics are used to draw together diverse problems or approaches into a unified whole. In addition, features of solution approaches found in today's commercial software are identified throughout the book. Thoroughly classroom-tested, Applied Integer Programming is an excellent book for integer programming courses at the upper-undergraduate and graduate levels. It also serves as a well-organized reference for professionals, software developers, and analysts who work in the fields of applied mathematics, computer science, operations research, management science, and engineering and use integer-programming techniques to model and solve real-world optimization problems.

---

Dieser Download kann aus rechtlichen Gründen nur mit Rechnungsadresse in A, B, BG, CY, CZ, D, DK, EW, E, FIN, F, GR, HR, H, IRL, I, LT, L, LR, M, NL, PL, P, R, S, SLO, SK ausgeliefert werden.

Produktdetails

• Verlag: John Wiley & Sons
• Seitenzahl: 488
• Erscheinungstermin: 20. September 2011
• Englisch
• ISBN-13: 9781118210024
• Artikelnr.: 37345971

Autorenporträt

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.

Inhaltsangabe

PREFACE. PART I MODELING. 1 Introduction. 1.1 Integer Programming. 1.2
Standard Versus Nonstandard Forms. 1.3 Combinatorial Optimization Problems.
1.4 Successful Integer Programming Applications. 1.5 Text Organization and
Chapter Preview. 1.6 Notes. 1.7 Exercises. 2 Modeling and Models. 2.1
Assumptions on Mixed Integer Programs. 2.2 Modeling Process. 2.3 Project
Selection Problems. 2.4 Production Planning Problems. 2.5 Workforce/Staff
Scheduling Problems. 2.6 Fixed-Charge Transportation and Distribution
Problems. 2.7 Multicommodity Network Flow Problem. 2.8 Network Optimization
Problems with Side Constraints. 2.9 Supply Chain Planning Problems. 2.10
Notes. 2.11 Exercises. 3 Transformation Using 0-1 Variables. 3.1 Transform
Logical (Boolean) Expressions. 3.2 Transform Nonbinary to 0-1 Variable. 3.3
Transform Piecewise Linear Functions. 3.4 Transform 0-1 Polynomial
Functions. 3.5 Transform Functions with Products of Binary and Continuous
Variables: Bundle Pricing Problem. 3.6 Transform Nonsimultaneous
Constraints. 3.7 Notes. 3.8 Exercises. 4 Better Formulation by
Preprocessing. 4.1 Better Formulation. 4.2 Automatic Problem Preprocessing.
4.3 Tightening Bounds on Variables. 4.4 Preprocessing Pure 0-1 Integer
Programs. 4.5 Decomposing a Problem into Independent Subproblems. 4.6
Scaling the Coefficient Matrix. 4.7 Notes. 4.8 Exercises. 5 Modeling
Combinatorial Optimization Problems I. 5.1 Introduction. 5.2 Set Covering
and Set Partitioning. 5.3 Matching Problem. 5.4 Cutting Stock Problem. 5.5
Comparisons for Above Problems. 5.6 Computational Complexity of COP. 5.7
Notes. 5.8 Exercises. 6 Modeling Combinatorial Optimization Problems II.
6.1 Importance of Traveling Salesman Problem. 6.2 Transformations to
Traveling Salesman Problem. 6.3 Applications of TSP. 6.4 Formulating
Asymmetric TSP. 6.5 Formulating Symmetric TSP. 6.6 Notes. 6.7 Exercises.
PART II REVIEW OF LINEAR PROGRAMMING AND NETWORK FLOWS. 7 Linear
Programming--Fundamentals. 7.1 Review of Basic Linear Algebra. 7.2 Uses of
Elementary Row Operations. 7.3 The Dual Linear Program. 7.4 Relationships
Between Primal and Dual Solutions. 7.5 Notes. 7.6 Exercises. 8 Linear
Programming: Geometric Concepts. 8.1 Geometric Solution. 8.2 Convex Sets.
8.3 Describing a Bounded Polyhedron. 8.4 Describing Unbounded Polyhedron.
8.5 Faces, Facets, and Dimension of a Polyhedron. 8.6 Describing a
Polyhedron by Facets. 8.7 Correspondence Between Algebraic and Geometric
Terms. 8.8 Notes. 8.9 Exercises. 9 Linear Programming: Solution Methods.
9.1 Linear Programs in Canonical Form. 9.2 Basic Feasible Solutions and
Reduced Costs. 9.3 The Simplex Method. 9.4 Interpreting the Simplex
Tableau. 9.5 Geometric Interpretation of the Simplex Method. 9.6 The
Simplex Method for Upper Bounded Variables. 9.7 The Dual Simplex Method.
9.8 The Revised Simplex Method. 9.9 Notes. 9.10 Exercises. 10 Network
Optimization Problems and Solutions. 10.1 Network Fundamentals. 10.2 A
Class of Easy Network Problems. 10.3 Totally Unimodular Matrices. 10.4 The
Network Simplex Method. 10.5 Solution via LINGO. 10.6 Notes. 10.7
Exercises. PART III SOLUTIONS. 11 Classical Solution Approaches. 11.1
Branch-and-Bound Approach. 11.2 Cutting Plane Approach. 11.3 Group
Theoretic Approach. 11.4 Geometric Concepts. 11.5 Notes. 11.6 Exercises. 12
Branch-and-Cut Approach. 12.1 Introduction. 12.2 Valid Inequalities. 12.3
Cut Generating Techniques. 12.4 Cuts Generated from Sets Involving Pure
Integer Variables. 12.5 Cuts Generated from Sets Involving Mixed Integer
Variables. 12.6 Cuts Generated from 0-1 Knapsack Sets. 12.7 Cuts Generated
from Sets Containing 0-1 Coefficients and 0-1 Variables. 12.8 Cuts
Generated from Sets with Special Structures. 12.9 Notes. 12.10 Exercises.
13 Branch-and-Price Approach. 13.1 Concepts of Branch-and-Price. 13.2
Dantzig-Wolfe Decomposition. 13.3 Generalized Assignment Problem. 13.4 GAP
Example. 13.5 Other Application Areas. 13.6 Notes. 13.7 Exercises. 14
Solution via Heuristics, Relaxations, and Partitioning. 14.1 Introduction.
14.2 Overall Solution Strategy. 14.3 Primal Solution via Heuristics. 14.4
Dual Solution via Relaxation. 14.5 Lagrangian Dual. 14.6 Primal-Dual
Solution via Benders' Partitioning. 14.7 Notes. 14.8 Exercises. 15
Solutions with Commercial Software. 15.1 Introduction. 15.2 Typical IP
Software Components. 15.3 The AMPL Modeling Language. 15.4 LINGO Modeling
Language. 15.5 MPL Modeling Language. REFERENCES. APPENDIX: ANSWERS TO
SELECTED EXERCISES. INDEX.