Applied Integer Programming E-Book

Der-San Chen

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 612

Veröffentlichungsjahr: 2011

Beschreibung

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.

Leseprobe

CONTENTS

PREFACE

PURPOSE, SCOPE, AND AUDIENCE

TOPIC COVERAGE, LEVEL OF PRESENTATION, AND IMPORTANT FEATURES

SUGGESTIONS FOR COURSE USE

ACKNOWLEDGMENTS

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 STRATEGIES

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

Copyright © 2010 by John Wiley & Sons, Inc. All rights reserved.

Published by John Wiley & Sons, Inc., Hoboken, New JerseyPublished simultaneously in Canada

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, exckpt as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization though payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 kver Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at http://www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Chen, Der-San, 1940–Applied integer programming: modeling and simulation/Der-San Chen, Robert G. Batson, Yu Dang.p. cm.Includes bibliographical references and index.ISBN 978-0-470-37306-4 (cloth)1. Integer programming. I. Batson, Robert G., 1950- II. Dang, Yu., 1977– III. Title.T57.74.C454 2010519.7′7–dc222009025987

Der-San dedicates this book to his blessed family,

Hannah, Suzy, and Benjamin

Bob dedicates this book to his wife Jane

and to his parents

Yu dedicates this book to her husband Qiu Fang

and to her parents

PREFACE

Integer programming (IP) is a class of constrained optimization problems in which some or all variables are integers and all mathematical functions in the objective and constraints are conventionally linear. In the professional community, the acronym MIP (mixed integer programming) is more often used, because many real-world problems involve a mix of continuous and integer-valued decision variables.

PURPOSE, SCOPE, AND AUDIENCE

We set out to write an easy-to-read, applied textbook for students enrolled in multiple academic disciplines and for professionals. In academia, the textbook is intended for graduate- and senior-level students of industrial engineering, operations research, management science, computer science, and applied mathematics. Other disciplines (such as operations management, supply chain management, logistics management, transportation engineering) that need a course in applied optimization would find this text a relevant option. Because of its application emphasis, this textbook can also be used as a reference book by practitioners whose jobs require modeling and solving real-world optimization problems using commercial integer programming software, as well as MIP software developers and analysts.

Instructors who are preparing students for careers in the practice of operations research and management science will find this book appealing. However, because of its application emphasis rather than mathematical rigor, this book is not suitable for instructors who are looking for theoretical underpinnings, such as mathematicians who are selecting a text for a course in discrete or combinatorial optimization.

Instructors of operations research and management science will find this text a natural continuation of and complement to well-known introductory textbooks in operations research and management science. As the subtitle indicates, the major approach of this book is modeling and solution. Modeling is emphasized because the insertion of integer variables in a linear program (LP) enables much more rich and realistic representations of decision situations. Both in the examples and exercises, students develop advanced modeling skills. Integer and linear programming terminology commonly referenced in commercial MIP solution software is covered in the text. This text provides extensive coverage of modeling techniques and solution methods with algorithms that are implemented in today’s commercial software.

TOPIC COVERAGE, LEVEL OF PRESENTATION, AND IMPORTANT FEATURES

This text is organized into three parts—Part I: Modeling, Part II: Review of Linear Programming and Network Flows, and Part III: Solutions. Part I (Chapters 1–6) includes areas of successful integer programming applications, systematic modeling procedure, types of integer programming models, transformation of non-IP models, automatic preprocessing for better formulation, and an introduction to combinatorial optimization. Part II (Chapters 7–10) reviews algebraic-geometric concepts and solution methods related to LP and network flows that are needed for understanding IP. Part III (Chapters 11–15) describes various solution approaches for large-scale IP and combinatorial optimization problems in addition to fundamentals of typical software systems. Solution approaches include classical, branch-and-cut, branch-and-price, primal heuristic, and Lagrangian relaxation. In Chapter 15, three popular modeling languages and one solver are introduced. Answers to selected problems from each chapter appear in an appendix. A more detailed preview of the text may be found in Section 1.5.

As an application-oriented text, we aim to teach students about the art and science of mathematical modeling for the collection of problems that fit the MIP framework and about the algorithms and associated practices that enable those models to be solved most efficiently. To make algorithms easier to comprehend, this book places unique emphasis not only on how the algorithms work but also on why they work. To achieve these goals, 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. We want the student, who we envision will become a practitioner, to have a well-organized and comprehensive reference that eases the learning hurdles in integer programming and provides suggestions/guidelines for practice, once on the job.

The book makes liberal use of examples and flowcharts. Each new concept or algorithm mentioned is illustrated by a numerical example. The book contains over 100 figures, either flowcharts or simple geometric drawings, to illustrate the concepts in the text. A unique feature is that where possible, we use graphics to draw together diverse problems or approaches into a well-structured whole. Chapters typically have between 10 and 20 exercises; some are simple applications similar to examples, and some are more comprehensive and challenging, such as choosing the appropriate methods from several presented, and applying them collectively to a problem. This again simulates the authors. experiences as practitioners. There are a few problems that require the reader to investigate a topic further or to attempt to prove an assertion or provide a counterexample. In summary, we attempted to write an applied integer programming text that emphasizes modeling and solution, with due attention to fundamentals of theory and algorithms. We believe it meets an unfulfilled need for an IP text that links together problem solving, theory, algorithms, and commercial software.

SUGGESTIONS FOR COURSE USE

This book is self-contained, requiring only a background in linear or matrix algebra. The book offers a great deal of flexibility to university course instructors. The entire book can be used for a two-semester sequence in linear and integer programming, at the level of seniors or masters students in engineering, computer science, or business schools. For students already completing a full course in linear programming, Parts I and III can be used as a masters-level course entitled Integer Programming or Integer and Combinatorial Programming. For students with a partial knowledge of linear programming obtained in an undergraduate survey of operations research, a compromise is to cover sections of Part I, II, and III. For instance, one coauthor taught a masters-level course Integer Programming using Chapters 1–4, 7–10, 11, 12, and 15.

ACKNOWLEDGMENTS

Der-San Chen would like to express his gratitude to Dr. Stanley Zionts, SUNY at Buffalo, for leading him to the field of integer programming through dissertation guidance. Similarly, Robert Batson recognizes Dr. Wei-Shen Hsia, The University of Alabama (UA), for introducing him to optimization theory while supervising his dissertation research. Drs Chen and Batson are affiliated with the College of Engineering at UA; Dr. Yu Dang received her Ph.D. in Operations Management from UA, and is affiliated with Quickparts.com, Inc. Former UA graduate student Sriram Venkataraman assisted Dr. Batson with preparation of the appendix. The authors would like to recognize Dr. Tao Huang of the SAS Institute who graciously contributed Section 15.3 to the text and suggested improvements to the organization and contents of the rest of the text. Also, many thanks to our Wiley Editor, Susanne Steitz-Filler, who offered encouragement when the going got tough.

PART I

MODELING

2

MODELING AND MODELS

In Chapter 1, we mathematically defined a mixed integer program (MIP). A mathematical definition in general has the advantages of being precise, concise, and capable of data manipulation. But to most managers and even some practitioners, it may be too abstract to comprehend and difficult to relate to reality. To alleviate this difficulty, we begin this chapter with an explanation of the real-world meanings of the MIP assumptions (or conditions). Section 2.1 describes these assumptions and their physical implications. Having this background, we then introduce a three-step procedure for modeling real-world problems in Section 2.2. This procedure systematically leads the practitioner toward an MIP model. In case the constructed model is not an MIP, the transformation techniques introduced in the next chapter may be used to obtain an equivalent MIP.

Recall in Chapter 1 we tabulated many successful IP application papers published in Interfaces and classified them by problem type. Each problem type will be given one to three examples in Sections 2.3–2.9. These examples may appear to be simpler than the real-world problems described in the application articles. Nevertheless, they do provide primary characteristics of the model types.

2.1 ASSUMPTIONS ON MIXED INTEGER PROGRAMS

Recall the following mixed integer program defined in Chapter 1:

The mixed IP comprises two fundamental building blocks: variables (including continuous and integer ) and input parameters (including , , , , , , , ). The objective function is a summation of several functions, each containing a single variable. Likewise, each constraint function (the left-hand side of an inequality) is also a summation of several functions of single variables. Both the objective and the constraint functions in the mixed IP are separable and linear. gives an anatomy of all assumptions imposed on a mixed integer program.