Remembering Manfred Padberg

Manfred Padberg Manfred W. Padberg (born 10 October 1941 in Bottrop, Germany) died on May 12, 2014 after a long battle with cancer. His research centered on the study of linear and combinatorial optimization, with an emphasis on developing polyhedral theory and fast algorithms that can aid in the solution of large, real-world optimization problems. 

Manfred Padberg grew up in Zagreb, Croatia and Westphalia, Germany. He began his studies in 1961 at the University of Münster, where he received hisDiplomin mathematics in 1967. He then spent a year as a research assistant at the University of Mannheim.  In 1968, he moved to the US under a Ford Foundation Fellowship to study operations research and industrial engineering at Carnegie Mellon University, Pittsburgh, where he received both his master’s degree and doctorate (1971) under the direction of Egon Balas. From 1971 to 1974, he was a research fellow at the International Institute of Management, Berlin, Germany. In 1974, he returned to the US as Associate Professor in operations research at Stern School of Business, New York University, becoming a Full Professor in 1978. He remained at NYU until becoming Professor Emeritus and moving to Paris in 2002. During his career in operations research, he was a guest scientist and/or a visiting professor at the University of Bonn, at the IBM Thomas J. Watson Research Center in Yorktown Heights, INRIA in Rocquencourt, at the École Polytechnique in Paris, the National Institute of Standards (NIST) in Maryland, the European Institute of Advanced Studies in Management (EIASM) in Brussels, the Center for Operations and Economics (CORE) in Louvain-la-Neuve, the Zuse Institute in Berlin, the Institute for Systems Analysis and Informatics (IASI) in Rome, and the State University of New York at Stony Brook. His fluency in Italian, French, English and German allowed him to lecture throughout the world. He spent his retirement in Paris and Marseille.

Over his lifetime, Manfred received all of the most significant prizes in the field of operations research, including: 

Manfred is best known for his work on applying polyhedral cuts to difficult optimization problems, often called “branch-and-cut” (a term he coined). He was most interested in graph-related problems and the algorithmic design of solution methodologies for such problems. He was always motivated by real-world applications and worked to solve previously unsolvable problems.

During the latter part of his research, he worked on ideal matrices and almost-perfect graphs.

To best summarize his work, we quote the citation associated with his receiving the John von Neumann Theory Prize:

"

Since receiving his Ph.D. from Carnegie Mellon University in 1971, Manfred Padberg has made fundamental contributions to both the theoretical and computational side of integer programming and combinatorial optimization. His early work on facets of the vertex packing polytope and their liftings, and on vertex adjacency on the set partitioning polytopes, paved the way toward the wider us of polyhedral methods in solving integer programs. His characterization of perfect 0/1-matrices reinforced the already existing ties between graph theory and 0/1-programming.

Padberg is the originator and main architect of the approach known as branch-and-cut. Concentrating on the traveling salesman problem as the main testbed, Padberg and Rinaldi successfully demonstrated that if cutting planes generated at various nodes of a search tree can be lifted so as to be valid everywhere, then interspersing them with branch and bound yields a procedure that vastly amplifies the power of either branch and bound or cutting planes themselves. This work had and continues to have a lasting influence.

One of the basic discoveries of the 1980’s in the realm of combinatorial optimization arrived at by three different groups of researchers in the wake of the advent of the ellipsoid method for convex programming, was the equivalence of optimization and separation: Padberg and M.R. Rao formed on these groups.

Padberg’s work combines theory with algorithm development and computational testing in the best tradition of Operations Research and the Management Sciences. In his joint work with Crowder and Johnson, as well as in subsequent work with others, Padberg set an example of how to formulate and handle efficiently very large scale practical 0/1 programs with important applications to industry and transportation.

"

For more on his work, one should refer to the following texts (or to the more than 110 papers that he published): 

He is survived by his wife, Suzy Mouchet-Padberg, his brother Friedhelm Padberg, his sister Christa Padberg, his daughter Britta Padberg-Schmitt, his son Marc Oliver Padberg, his stepson Hannibal Renberg and five grandchildren: Franziska, Franz Josef, Mia, Maya and Mei.