Researchers will find this book--a collection of papers written to honor Manfred Padberg on the occasion of his sixtieth birthday--to be extremely useful as a reference on various aspects of combinatorics. The papers are grouped into the following topics: packing, stable sets, and perfect graphs; polyhedral combinatorics; general polytopes; semidefinite programming; and computation. A brief curriculum vitae, a survey of Padberg’s work, and an appendix with the text of the three speeches given during this celebration are also included.

Each of the parts into which the book is subdivided represents an important area of research. In all of these areas, the contribution of Padberg has been extremely relevant. The papers, all written by outstanding scholars, demonstrate the relevance of the work done by Padberg, and provide state-of-the-art information on various aspects in combinatorial optimization.

Combinatorial packing problems, the coloring of matrices, and perfect and almost perfect graphs are the topics of the papers in the first part of the book. The first two papers investigate the combinatorial packing problem and polyhedral relationship, with set packing problems and bicoloring results for matrices that can be used to characterize the total unimodularity of a matrix. The remaining three papers in this part all address perfect graphs (the ranking of three-chromatic perfect graphs, primal operations for stable sets, and almost perfect graphs).

The papers in the second part of the book are devoted to polyhedral combinatorics. Again, five papers are in this part. The first paper provides a complete linear description of the polytope P(C), the convex hull of the incidence vectors of all sets in C (a set in C is a subset of the finite set E). The construction of valid inequalities (with the goal of developing a branch-and-cut algorithm) is used for the survival networks design problem. The construction of valid inequalities (for the traveling salesman problem (TSP)) makes up the bulk of the next paper. In particular, domino inequalities are discussed, as well as their contribution to the description of the symmetric TSP polytope. The next paper discusses 0/1 matrices with the consecutive ones property, and a branch-and-cut algorithm is proposed. Such matrices play an important role in computational biology. A specific problem in computational biology (the protein folding problem) is addressed in the next paper, and an approach based on integer programming is proposed.

General polytopes are covered next, in two papers. The first presents different techniques for bounding the edge expansion of a 0/1 polytope from below, and studies special classes of these polytopes. The second paper discusses geometrical and combinatorial aspects of linear program polyhedra.

Two papers are included in the next part, devoted to semidefinite programming. The first paper discusses the primal convergence of a spectral bundle method, and the convergence of a conceptual cutting plane algorithm is presented. The second paper provides a comparison of several semidefinite relaxations for a special polytope. The application to the max-cut problem is also discussed.

The last part of the book is devoted to a paper on computation. The Steinberg wiring problem, the progress in mixed integer programming, and optimization problems arising in graph drawing are the topics discussed here.

The papers included in this book provide the reader with state-of-the-art information for various topics in combinatorial optimization, and the book can be used as an additional textbook in advanced PhD courses.