Integer and Combinatorial Optimization E-Book

Laurence A. Wolsey

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Serie: Wiley-Interscience Series in Discrete Mathematics and Optimization
• Sprache: Englisch

Seitenzahl: 1347

Veröffentlichungsjahr: 2014

Beschreibung

Rave reviews for INTEGER AND COMBINATORIAL OPTIMIZATION "This book provides an excellent introduction and survey of traditional fields of combinatorial optimization . . . It is indeed one of the best and most complete texts on combinatorial optimization . . . available. [And] with more than 700 entries, [it] has quite an exhaustive reference list."-Optima "A unifying approach to optimization problems is to formulate them like linear programming problems, while restricting some or all of the variables to the integers. This book is an encyclopedic resource for such formulations, as well as for understanding the structure of and solving the resulting integer programming problems."-Computing Reviews "[This book] can serve as a basis for various graduate courses on discrete optimization as well as a reference book for researchers and practitioners."-Mathematical Reviews "This comprehensive and wide-ranging book will undoubtedly become a standard reference book for all those in the field of combinatorial optimization."-Bulletin of the London Mathematical Society "This text should be required reading for anybody who intends to do research in this area or even just to keep abreast of developments."-Times Higher Education Supplement, London Also of interest . . . INTEGER PROGRAMMING Laurence A. Wolsey Comprehensive and self-contained, this intermediate-level guide to integer programming provides readers with clear, up-to-date explanations on why some problems are difficult to solve, how techniques can be reformulated to give better results, and how mixed integer programming systems can be used more effectively. 1998 (0-471-28366-5) 260 pp.

Leseprobe

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

Published 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, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone]. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone].

Library of Congress Cataloging in Publication Data:

Nemhauser, George L.

Integer and combinatorial optimization.

(Wiley-Intersctence series in discrete mathematics and optimization)

“A Wiley-Interscience publication.”

Includes bibliographies and index.

1. Mathematical optimization. 2. Integer programming.

3. Combinatorial optimization. I. Wolsey, Laurence A.

II. Title. III. Series.

QA402.5.N453 1988 519.77 87-34067

ISBN 0-471-82819-X

ISBN 0-471-35943-2 (paperback)

Printed in the United States of America

19 18

To our parents

Preface

The explosion of new results in integer and combinatorial optimization that began about fifteen years ago inspired us to write a book that would unify theory and algorithms and could serve as a graduate text and reference for researchers and practitioners. We have been very excited about many of the new developments that have made it possible to solve large-scale integer programming problems and that have opened up new areas of research which surely will yield more robust and efficient algorithms. Little did we realize the enormity of the task. Both of us worked steadily on this project for more than four years. The end result was a manuscript of nearly 1400 typewritten pages which, although it does not come close to covering all of the literature, covers those topics that we believe constitute the most significant theoretical and algorithmic developments.

Optimization means to maximize (or minimize) a function of many variables subject to constraints. The distinguishing feature of discrete, combinatorial, or integer optimization is that some of the variables are required to belong to a discrete set, typically a subset of integers. These discrete restrictions allow the mathematical representation of phenomena or alternatives where indivisibility is required or where there is not a continuum of alternatives.

Discrete optimization problems abound in everyday life. An important and widespread area of applications concerns the management and efficient use of scarce resources to increase productivity. These applications include operational problems such as the distribution of goods, production scheduling, and machine sequencing. They also include planning problems such as capital budgeting, facility location and portfolio selection, and design problems such as telecommunication and transportation network design, VLSI circuit design and the design of automated production systems. Discrete optimization problems also arise in statistics (data analysis), physics (determination of minimum energy states), cryptography (designing unbreakable codes), politics (selecting fair election districts), and mathematics (as a powerful technique for proving combinatorial theorems). Moreover, applications of discrete optimization are in a period of rapid development because of the widespread use of microcomputers and the data provided by information systems. This is particularly relevant in the manufacturing sector of the economy where increased competition and flexibility provided by new technology make it imperative to seek better solutions from larger and more complex sets of alternatives.

This book is about the mathematics of discrete optimization, which includes the representation of problems by mathematical models and, especially, the solution of the models. The focus is on understanding the mathematical underpinnings of the algorithms that make it possible to solve (exactly or approximately) the large and complex models that arise in practical applications.

Chapter I.1 discusses problem formulation, which is important not only to demonstrate the scope of applications, but also because the structure of the formulation is of crucial importance to solving the model. Chapter I.1 gives a comprehensive treatment of this subject.

The remainder of Part I presents mathematics and algorithms that are the foundations for the discrete optimization theory and techniques of Parts II and III. There are chapters on well-established subjects including linear programming (Chapter I.2), graphs and networks (Chapter I.3), and computational complexity (Chapter I.5). The presentation of polyhedral theory (Chapter I.4) begins with basic results from linear algebra and then emphasizes precisely those results that are essential to a fundamental understanding of the algebra and geometry of the convex hull of a discrete set. Chapter I.6 gives new algorithms and results on linear programming and, in particular, establishes the fundamental connection between separation and optimization. Chapter I.7 presents a modern treatment of the classical problem of solving linear equations in integers and also includes an introduction to the recent work on reduced bases for integer lattices.

Parts II and III present basic approaches and algorithms for solving discrete optimization problems. Part II deals with general problems and those that contain some structure. These are the problems that are hard to solve but, for the most part, they are the ones that arise in practical applications.

Chapters II.1 and II.2 treat the problem of describing the set of feasible solutions to an integer program by a set of linear inequalities. It begins with elementary ideas, but also includes a thorough development of advanced topics such as superadditive valid inequalities and the use of structure to obtain facet-defining inequalities. Objective functions for integer programs are introduced in Chapter II.3 where the fundamental approaches of relaxation and duality are developed for the purpose of obtaining upper bounds on the optimal value. Most of the advanced material in these chapters has appeared only in research articles and monographs, but is essential for the development of future generation algorithms for solving integer programs.

Algorithms are presented in Chapters II.4, II.5 and II.6. Chapter II.4 presents classical branch-and-bound and cutting plane algorithms. Specialized algorithms that use varying degrees of structure to obtain exact or approximate solutions are presented in Chapters II.5 and II.6. Here we study and illustrate a number of techniques that, for the most part, have been developed over the last decade and are not covered in the currently available textbooks. These include strong cutting plane algorithms, primal and dual heuristic analysis, decomposition and reduced bases, and their applications to 0-1 integer programs, the traveling salesman problem and fixed-charge network flow problems.

Part III treats highly structured combinatorial optimization problems for which elegant results are known. Chapter III.1 studies polyhedra with integral extreme points. It includes classical results on total unimodularity and recent results on totally balanced, balanced, and perfect matrices and on the blocking and antiblocking theory of polyhedra. Chapters III.2 and III.3 are on the classical combinatorial problems of matching and matroids, respectively. In both of these chapters the emphasis is on optimization algorithms, polyhedral combinatorics and duality. Chapter III.3 also introduces the significant role of submodular and supermodular functions in combinatorial optimization.

Notes appear at the end of each chapter. Their purpose is to reference our source materials, and to comment briefly on extensions and related topics that are not discussed in the body of the text. The citations and references are selective. With the exception of Chapter I.1, in Part I our objective is to provide foundation material, and thus the notes are limited to a small number of references that cover the corresponding topics in much greater detail than is done here. However, in Parts II and III we have attempted to cite the original papers in which the material appears as well as some other influential works.

The book can be used as a graduate text or for self-guided reading in several ways. Since we cannot imagine a reader who would want to undertake a straight cover-to-cover reading and since our experience has shown that it is not possible to cover the whole book in even a two-semester, graduate level course, it is necessary to be selective in a first reading.

For graduate students in mathematical programming, especially those planning to undertake research in discrete optimization, we suggest a full academic year course (course AY). Three one-semester options are: a course emphasizing practical algorithms (course PA), a course emphasizing general theory (course GT), and a course in polyhedral combinatorics (course PC).

Each course should begin with some exposure to Chapter I.1 on model formulation, which is important not only to demonstrate the scope of applications, but also because the structure of the formulation is of crucial importance in solving the model.

Chapters I.2 and I.3 are only for review, since it is wise for any reader of the book to have studied linear programming as a prerequisite. But a typical linear programming course, unfortunately, does not cover polyhedral theory. Therefore, all courses should cover Chapter I.4. In course PA, just enough of the first four sections should be covered (without proofs) for the student to understand the concept of facets of polyhedra and the idea of Theorem 6.1 on the convex hull of a discrete set of points.

The coverage of Chapter I.5 on computational complexity will depend on the students’ backgrounds and the instructor’s taste; but at the very least, students in all courses should be introduced to the concepts of polynomial computation and NP-completeness. Similarly, students in all courses should be introduced to the concept of separation and the polynomial equivalence of separation and optimization (Section I.6.3). This should be done very informally in course PA. Sections I.6.2, I.6.4 and I.6.5 are independent reading and should be omitted in a first reading of the book. Chapter I.7, and then Section II.6.5, might be covered only in courses AY and GT if time permits at the end of the course. They can also be omitted in a first reading.

Courses PA and GT focus on different parts of Part II. Course PC can omit Part II altogether, but would be more interesting if Sections II.l.l, II.1.2 (first-half), II.2.1, II.2.3, and II.6.3 also were included.

The following sections from Part II are common to courses AY, PA, and GT: II.l.l, II.2.1, II.2.2, II.3.1, II.3.6, II.3.7, II.4.1, II.5.1, II.5.2 and II.5.3.

Course PA should also cover Sections II.4.2, II.5.4, II.5.5, II.6.1 (knapsack problem) and II.6.2, and, if time permits, Sections II.2.4 and II.6.4. The instructor may find some time for the important class of problems and algorithms discussed in the later two sections by omitting or only sketching some proofs from the earlier sections.

Course GT should also cover Sections II.1.2 (leaving out the subsection on bounded integer variables), II.1.3, II.1.4, II.1.5, II.2.3, II.3.2, and II.3.3, and the first two sections of Chapter III.1. If time permits, additional theoretical material could be selected from Sections II.1.6, II.1.7, II.3.4, II.3.5, or some algorithms could be studied from Sections II.4.3, II.5.4 and the first three sections of Chapter II.6.

With respect to Part II, course AY is the union of the material covered in courses PC and GT. From Part III, course AY should also cover sections III.1.1, III.1.2, III.1.4 and the first three sections of Chapter III.2. Any remaining time could be spent on either sections III.1.5, III.1.6, or the first few sections of Chapter III.3.

The material to be selected from Part III for course PC can vary according to taste. We suggest all of Chapter III.1 except for Section III.1.3, the first 3 sections of Chapter III.2 and the first 5 sections of Chapter III.3.

This book could not have been written without the tremendous support that we received from the Center for Operations Research and Econometrics (CORE) of the Université Catholique de Louvain, and thus we are extremely grateful to Jacques Dreze, the founder and intellectual leader of CORE.

We met at CORE in the winter of 1970. Nemhauser spent the academic year 1969-1970 at CORE and Wolsey presented a seminar on his early work on the group-theoretic approach to integer programming. Subsequently, Wolsey became a permanent member of CORE and Nemhauser returned to CORE for the period 1975—1977 as Research Director. During this period, the authors collaborated extensively on research in the analysis of heuristics and other topics in integer and combinatorial optimization stimulated by an active research group that included Jack Edmonds, Bob Bland, Guy de Ghellinck, Rick Giles, Bob Jeroslow, Tom Magnanti, Bill Pulleyblank, Mike Ball and Gerard Cornuejols. All of these people, as well as our Dutch neighbors, Jan-Karel Lenstra and Alexander Rinnooy Kan, contributed to our understanding of the subject and motivation to write a book.

A NATO research grant made it possible for us to continue our research collaboration through the late seventies and early eighties, and we began to draft the manuscript earnestly during Nemhauser’s fourth year at CORE in 1983-1984. During the writing of the book we benefitted from numerous discussions with our friends and professional colleagues including Egon Balas, Vasek Chvátal, Marshall Fisher, Martin Grötschel, Ellis Johnson, Manfred Padberg. Lex Schrijver, Jorgen Tind and Les Trotter. We are particularly grateful to Gerard Cornuejols who read Parts I and II and provided extensive comments and suggestions and to Bill Pulleyblank who did the same for Part III. We are also thankful for the comments we received on various drafts of the text from Jorgen Tind, Bob Jeroslow, Alan Goldman, Anton Kolen, Jan-Karel Lenstra, Lex Schrijver, Donna Crystal Llewellyn, Martin Dyer, Mike Todd, Jean-Philippe Vial and John Vande Vate. Our students in courses given at CORE, Cornell and Georgia Tech found typos and other mistakes that otherwise would have been missed; special thanks are due to Ronny Aboudi, Yves Pochet and Gabriele Sigismondi.

The chores of deciphering our untidy handwritten drafts and of retyping endless revisions were done graciously and with utmost care and patience by the late Elizabeth Pecquereau, formerly a secretary at CORE. We are very sad that we will not be able to share the joy of seeing the final product with our dear friend Elizabeth. Fabienne Henry of CORE and Yvonne Kissi of Georgia Tech also did excellent jobs in typing parts of the manuscript. Sheila Verkaren of CORE always managed to spare some of Elizabeth’s or Fabienne’s time for our book, even though we were using far more than our fair share of CORE’S secretarial resources.

Over a period of four years, Ellen Nemhauser and Marguerite Wolsey were frequently ignored while their husbands spent evenings and weekends writing, and occasionally were imposed upon by a boarder who ate and slept at their house, but otherwise was too involved in mathematics to engage in civil conversation or to wash the dishes. We thank them for their love and patience and hope to make amends.

GEORGE L. NEMHAUSERLAURENCE A. WOLSEY

Atlanta, Georgia, USALouvain-la-Neuve, BelgiumFebruary, 1988.

Contents

PART I. FOUNDATIONS

I.1 The Scope of Integer and Combinatorial Optimization

1. Introduction

2. Modeling with Binary Variables I: Knapsack, Assignment and Matching, Covering, Packing and Partitioning

3. Modeling with Binary Variables II: Facility Location, Fixed-Charge Network Flow, and Traveling Salesman

4. Modeling with Binary Variables III: Nonlinear Functions and Disjunctive Constraints

5. Choices in Model Formulation

6. Preprocessing

7. Notes

8. Exercises

I.2 Linear Programming

1. Introduction

2. Duality

3. The Primal and Dual Simplex Algorithms

4. Subgradient Optimization

5. Notes

I.3 Graphs and Networks

1. Introduction

2. The Minimum-Weight or Shortest-Path Problem

3. The Minimum-Weight Spanning Tree Problem

4. The Maximum-Flow and Minimum-Cut Problems

5. The Transportation Problem: A Primal-Dual Algorithm

6. A Primal Simplex Algorithm for Network Flow Problems

7. Notes

I.4 Polyhedral Theory

1. Introduction and Elementary Linear Algebra

2. Definitions of Polyhedra and Dimension

3. Describing Polyhedra by Facets

4. Describing Polyhedra by Extreme Points and Extreme Rays

5. Polarity

6. Polyhedral Ties Between Linear and Integer Programs

7. Notes

8. Exercises

I.5 Computational Complexity

1. Introduction

2. Measuring Algorithm Efficiency and Problem Complexity

3. Some Problems Solvable in Polynomial Time

4. Remarks on 0-1 and Pure-Integer Programming

5. Nondeterministic Polynomial-Time Algorithms and NP Problems

6. The Most Difficult NP Problems: The Class NPC

7. Complexity and Polyhedra

8. Notes

9. Exercises

I.6 Polynomial-Time Algorithms for Linear Programming

1. Introduction

2. The Ellipsoid Algorithm

3. The Polynomial Equivalence of Separation and Optimization

4. A Projective Algorithm

5. A Strongly Polynomial Algorithm for Combinatorial Linear Programs

6. Notes

I.7 Integer Lattices

1. Introduction

2. The Euclidean Algorithm

3. Continued Fractions

4. Lattices and Hermite Normal Form

5. Reduced Bases

6. Notes

7. Exercises

PART II. GENERAL INTEGER PROGRAMMING

II.1 The Theory of Valid Inequalities

1. Introduction

2. Generating All Valid Inequalities

3. Gomory’s Fractional Cuts and Rounding

4. Superadditive Functions and Valid Inequalities

5. A Polyhedral Description of Superadditive Valid Inequalities for Independence Systems

6. Valid Inequalities for Mixed-Integer Sets

7. Superadditivity for Mixed-Integer Sets

8. Notes

9. Exercises

II.2 Strong Valid Inequalities and Facets for Structured Integer Programs

1. Introduction

2. Valid Inequalities for the 0-1 Knapsack Polytope

3. Valid Inequalities for the Symmetric Traveling Salesman Polytope

4. Valid Inequalities for Variable Upper-Bound Flow Models

5. Notes

6. Exercises

II.3 Duality and Relaxation

1. Introduction

2. Duality and the Value Function

3. Superadditive Duality

4. The Maximum-Weight Path Formulation and Superadditive Duality

5. Modular Arithmetic and the Group Problem

6. Lagrangian Relaxation and Duality

7. Benders’ Reformulation

8. Notes

9. Exercises

II.4 General Algorithms

1. Introduction

2. Branch-and-Bound Using Linear Programming Relaxations

3. General Cutting-Plane Algorithms

4. Notes

5. Exercises

II.5 Special-Purpose Algorithms

1. Introduction

2. A Cutting-Plane Algorithm Using Strong Valid Inequalities

3. Primal and Dual Heuristic Algorithms

4. Decomposition Algorithms

5. Dynamic Programming

6. Notes

7. Exercises

II.6 Applications of Special-Purpose Algorithms

1. Knapsack and Group Problems

2. 0-1 Integer Programming Problems

3. The Symmetric Traveling Salesman Problem

4. Fixed-Charge Network Flow Problems

5. Applications of Basis Reduction

6. Notes

7. Exercises

PART III. COMBINATORIAL OPTIMIZATION

III.1 Integral Polyhedra

1. Introduction

2. Totally Unimodular Matrices

3. Network Matrices

4. Balanced and Totally Balanced Matrices

5. Node Packing and Perfect Graphs

6. Blocking and Integral Polyhedra

7. Notes

8. Exercises

III.2 Matching

1. Introduction

2. Maximum-Cardinality Matching

3. Maximum-Weight Matching

4. Additional Results on Matching and Related Problems

5. Notes

6. Exercises

III.3 Matroid and Submodular Function Optimization

1. Introduction

2. Elementary Properties

3. Maximum-Weight Independent Sets

4. Matroid Intersection

5. Weighted Matroid Intersection

6. Polymatroids, Separation, and Submodular Function Minimization

7. Algorithms To Minimize a Submodular Function

8. Covering with Independent Sets and Matroid Partition

9. Submodular Function Maximization

10. Notes

11. Exercises

References

Author Index

Subject Index

Part IFOUNDATIONS

I.1

The Scope of Integer and Combinatorial Optimization

1. INTRODUCTION

Integer and combinatorial optimization deals with problems of maximizing or minimizing a function of many variables subject to (a) inequality and equality constraints and (b) integrality restrictions on some or all of the variables. Because of the robustness of the general model, a remarkably rich variety of problems can be represented by discrete optimization models.

An important and widespread area of application concerns the management and efficient use of scarce resources to increase productivity. These applications include operational problems such as the distribution of goods, production scheduling, and machine sequencing. They also include (a) planning problems such as capital budgeting, facility location, and portfolio analysis and (b) design problems such as communication and transportation network design, VLSI circuit design, and the design of automated production systems.

In mathematics there are applications to the subjects of combinatorics, graph theory, and logic. Statistical applications include problems of data analysis and reliability. Recent scientific applications involve problems in molecular biology, high-energy physics, and x-ray crystallography. A political application concerns the division of a region into election districts.

Some of these discrete optimization models will be developed later in this chapter. But their number and variety are so great that we only can provide references for some of them. The main purpose of this book is to present the mathematical foundations of integer and combinatorial optimization models along with the algorithms that can be used to solve the problems.

Throughout most of this book, we assume that the function to be maximized and the inequality restrictions are linear. Note that minimizing a function is equivalent to maximizing the negative of the same function and that an equality constraint can be represented by two inequalities. It is also common to require the variables to be nonnegative. Hence we write the linear mixed-integer programming problem as

(MIP)

We assume throughout the text that all of the data sets are rational, that is, that each of the individual numbers is rational. Although in making this assumption we sacrifice some theoretical generality, it is a natural assumption for solving problems on a digital computer.

The set is called the feasible region, and an (x,y) ∈ S is called afeasible solution. An instance is said to be feasible if S ≠ ∅. The function

is called the objective function. A feasible point (x0, y0) for which the objective function is as large as possible, that is,

is called an optimal solution. If (x0,y0) is an optimal solution, cx0+ hy0 is called the optimal value or weight of the solution.

In Section 1.4.6, we will show that every feasible instance of MIP either has an optimal solution or is unbounded. This result requires the assumption of rational data. With irrational data, it is possible that no feasible solution attains the least upper bound on the objective function.

Thus to solve an instance of MIP means to produce an optimal solution or to show that it is either unbounded or infeasible.

The linear (pure) integer programming problem

(IP)

is the special case of MIP in which there are no continuous variables. The linear programming problem

(LP)

is the special case of MIP in which there are no integer variables.

In many models, the integer variables are used to represent logical relationships and therefore are constrained to equal 0 or 1. Thus we obtain the 0-1 MIP (respectively 0-1 IP) in which is replaced by x ∈ Bn, where Bn is the set of n-dimensional binary vectors.

(CP)

Some examples of combinatorial optimization problems will be given later in this chapter.