Applied Integer Programming: Modeling and Solution / Edition 1

Hardcover (Print)
Buy New
Buy New from BN.com
$114.41
Used and New from Other Sellers
Used and New from Other Sellers
from $96.76
Usually ships in 1-2 business days
(Save 30%)
Other sellers (Hardcover)
  • All (6) from $96.76   
  • New (4) from $116.11   
  • Used (2) from $96.76   

Overview

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.

Read More Show Less

Editorial Reviews

From the Publisher
"Thoroughly classroom-tested, Applied integer programming is an excellent book for integer programming courses at the upper-undergraduate and graduate levels." (Mathematical Reviews, 2011)

"The book is intended as a textbook for an application oriented course for senior undergraduate or postgraduate students, mainly with an engineering, business school, or applied mathematics background. Each chapter comes with several exercises, solutions of which are provided in an appendix. Many figures illustrate the flow of algorithms and other concepts." (Zentralblatt MATH, 2010)

Read More Show Less

Product Details

  • ISBN-13: 9780470373064
  • Publisher: Wiley
  • Publication date: 1/12/2010
  • Edition number: 1
  • Pages: 488
  • Product dimensions: 9.30 (w) x 6.30 (h) x 1.20 (d)

Meet the Author

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.

Read More Show Less

Table of Contents

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.

Read More Show Less

Customer Reviews

Be the first to write a review
( 0 )
Rating Distribution

5 Star

(0)

4 Star

(0)

3 Star

(0)

2 Star

(0)

1 Star

(0)

Your Rating:

Your Name: Create a Pen Name or

Barnes & Noble.com Review Rules

Our reader reviews allow you to share your comments on titles you liked, or didn't, with others. By submitting an online review, you are representing to Barnes & Noble.com that all information contained in your review is original and accurate in all respects, and that the submission of such content by you and the posting of such content by Barnes & Noble.com does not and will not violate the rights of any third party. Please follow the rules below to help ensure that your review can be posted.

Reviews by Our Customers Under the Age of 13

We highly value and respect everyone's opinion concerning the titles we offer. However, we cannot allow persons under the age of 13 to have accounts at BN.com or to post customer reviews. Please see our Terms of Use for more details.

What to exclude from your review:

Please do not write about reviews, commentary, or information posted on the product page. If you see any errors in the information on the product page, please send us an email.

Reviews should not contain any of the following:

  • - HTML tags, profanity, obscenities, vulgarities, or comments that defame anyone
  • - Time-sensitive information such as tour dates, signings, lectures, etc.
  • - Single-word reviews. Other people will read your review to discover why you liked or didn't like the title. Be descriptive.
  • - Comments focusing on the author or that may ruin the ending for others
  • - Phone numbers, addresses, URLs
  • - Pricing and availability information or alternative ordering information
  • - Advertisements or commercial solicitation

Reminder:

  • - By submitting a review, you grant to Barnes & Noble.com and its sublicensees the royalty-free, perpetual, irrevocable right and license to use the review in accordance with the Barnes & Noble.com Terms of Use.
  • - Barnes & Noble.com reserves the right not to post any review -- particularly those that do not follow the terms and conditions of these Rules. Barnes & Noble.com also reserves the right to remove any review at any time without notice.
  • - See Terms of Use for other conditions and disclaimers.
Search for Products You'd Like to Recommend

Recommend other products that relate to your review. Just search for them below and share!

Create a Pen Name

Your Pen Name is your unique identity on BN.com. It will appear on the reviews you write and other website activities. Your Pen Name cannot be edited, changed or deleted once submitted.

 
Your Pen Name can be any combination of alphanumeric characters (plus - and _), and must be at least two characters long.

Continue Anonymously
Sort by: Showing 1 Customer Reviews
  • Anonymous

    Posted February 11, 2010

    An Excellent Application Text

    A timely, comprehensive, easy-to-read, and self-contained application textbook for integer programming - the first readable text this 30 year veteran has seen in a decade - a must-have for every practitioner. The book is formatted as a traditional textbook, with problems at the end of each chapter, and solutions in the back of the book for many of the more difficult problems. This text is a natural extension of the well-known introductory texts: e.g. Winston. An extensive reference list bridges the practical solutions to the underlying theory. The references are linked from the historical notes at the end of each chapter. The text covers integer programming in 3 major sections: modeling, linear programming theory, and classical and modern solutions.

    The modeling section covers all the classical problems: knapsack, production planning, and scheduling - followed by the network models: assignment, transshipment, maxflow, and shortest path.

    Since linear programming based branch and bound solutions are state-of-the-art, the second section reviews linear programming fundamentals as both a traditional linear algebra formulation and, in preparation for branch and bound cuts, a geometrical formulation where the columns are the basis vectors spanning the feasible solution space. Figures are extensively used to crystallize the geometric concepts.

    In the final, integer programming methods are covered in general: branch and bound, cutting plane, and group theoretic - focusing on using the methods in combinations, especially, branch and bound with cutting plane. Detailed, but tractable, examples with figures are included every step of the way emphasizing how and why the algorithms work. Rarely introduced in a text are 3 modeling languages that can actually be used in commercial applications.

    An excellent text - enjoy.

    1 out of 1 people found this review helpful.

    Was this review helpful? Yes  No   Report this review
Sort by: Showing 1 Customer Reviews

If you find inappropriate content, please report it to Barnes & Noble
Why is this product inappropriate?
Comments (optional)