Integer and Combinatorial Optimization

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,...