Great Book on Integer Programming

I just received the book “50 Years of Integer Programming 1958-2008”  published by Springer and edited by the blue-ribbon group of  Michael Jünger, Thomas Liebling, Denis Naddef, George Nemhauser, William Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, and Laurence Wolsey (full disclosure:  I received a complimentary copy, presumably hoping I would post something entitled “Great Book on Integer Programming”.  Of course they risked me posting “Someone’s Littering My Mailbox with Junk” if I didn’t like the book. That is the risk when you give a free book to someone with a day job:  I don’t really rely on this blog to support my family so I can afford to just post what I think).

This book grew out of a 2008 workshop held in Aussois, France.  The “50 years” aspect dates the beginning of integer programming to Gomory’s famous cutting plane approach to integer programming.  Given the “50 years” aspect, it is appropriate that the first part of the book (about 340 pages) consists of reprints of some of the most important foundational papers in this field.  These papers begin with Dantzig, Fulkerson, and Johnson on solving a “large-scale” traveling salesman problem (49 cities), and continue with papers by Kuhn (Hungarian Algorithm for assignment), Hoffman and Kruskal (total unimodularity), Gomory (cutting planes), Land and Doig (Branch and Bound), Balinski ( 1965 survey), Edmonds (matroid partition), Karp (reducibility), Geoffrion (Lagrangian relaxation), and Balas (disjunctive programming).  I have read all of these papers, some as an undergraduate at Waterloo, some as a doctoral student, and some in my professional life as a professor.  Seeing them again was like seeing old friends.  The best part is the introductions to each of the papers.  We are fortunate that many of these authors are still with us and were able to provide some background on where the papers came from.  For some, the authors have passed away, but the editors have done a good job of finding people who could offer insightful perspectives.

I particularly enjoyed re-reading the paper on the Traveling Salesman Problem by Dantzig, Fulkerson and S. Johnson.  This paper formally belongs in the pre-history of integer programming, having been published in Operations Research in 1954.  In the paper, the authors show how to find a solution to a 49 city TSP.  I was struck again how much work this took to solve without the use of computers.  This paper occurred even before terminology was fixed (so constraints become restraints in this paper).  Dual variables are solved for directly by taking advantage of the structure of sparse linear programming solutions to this problem, since all the subproblems were solved by hand (over 1176 variables!).  And I loved the conclusions:

It is clear that we have left unanswered practically any question one might pose of a theoretical nature concerning the traveling-salesman problem;  however, we hope that the feasibility of attacking problems involving a moderate number of points has been successfully demonstrated, and that perhaps some of the ideas can be used in problems of a similar nature.

If only some of today’s researchers had the same level of perspective and humility!

I also loved a paragraph from Gomory’s introduction to his two papers.  After developing what would later be known as “Gomory cuts”, he decided to test it on a (1958) computer:

During the exciting weeks that followed, I finally worked out a finiteness proof and the programmed the algorithm on the E101, a pin board computer that was busy during the day but that I could use after midnight.  The E101 had only about 100 characters and the board held only 120 instructions at one time, so that I had to change boards after each simplex maximization cycle and put in a new board that generated the cut, and the put the old board back to re-maximize.  It was also hard work to get the simplex method down to 120 E101 instructions.  But the results were better and more reliable than my hand calculations, and I was able to steadily and rapidly produce solutions to four- and five- variable problems.

I thought I was hard core, reminiscing about working with punch cards, but Gomory reveals me as a slacker!

The historical section is followed by three general survey articles:  Conforti, Cornuéjols, and Zambelli on polyhedral approaches, Bill Cook on combinatorial integer programming, and Vanderbeck and Wolsey on reformulations and decomposition.  The final section are a series of surveys on modern topics:  geometry of numbers, nonlinear integer programming, MIP computation, symmetry, semidefinite relaxations, and group theoretic approaches.  The authors chosen are the leading people in each area, and the articles are extremely well done.   With these papers, this book now is the reference book for the current state of the art in integer programming.  The Amazon page for the book has the first dozen or so pages available with their “Look Inside” feature, so you can check out the full table of contents.

The book comes with two DVDs.  One contains the presentations from Section II in hour-long sessions.  The second DVD has a very entertaining discussion between moderators George Nemhauser and Bill Pulleyblank and “founders” Egon Balas, Michel Balinski, Jack Edmonds, Ralph Gomory, Art Geoffrion and Richard Karp (Alan Hoffman, Harold Kuhn, and Aisla Land were unable to attend).  I haven’t watched the whole thing yet, so if it ends in a brawl, don’t spoil it for me!  It was great to see that panel all together.

Overall, I haven’t enjoyed getting a book as much in a long time (certainly not since Bill Cook’s Traveling Salesman book, and I wouldn’t want to choose between these two).  I think I would even pay Springer’s list price of $99 for it, though I really wish they would price this more reasonably (though the price is not absurd:  they have many books that offer far less that cost far more) .  Everyone even vaguely interested in integer programming should have this on their bookshelf.