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.

Summer Internship at Solver Foundation

I get a fair number of emails of the sort “I am studying at ….and I would like to work under your supervision as a summer intern”.  Most of the time they go on to say things like “I want to work under your supervision on stochastic optimization, supply chains, e-commerce” or an of a dozen things that suggest they 1) don’t know what I do, and 2) don’t really care to find out.  That is probably the economically efficient choice, since I don’t take on summer interns, and have even written about it.  I don’t know where this myth of summer internships for people from around the world comes from (unless there are a large group of people who welcome this?  Let me know!).

Once in a while, however, I see a summer internship and think:  “Wow!  I wish I was 20 (or 25) again!  That looks like a great opportunity!”  The Solver Foundation team just posted such an opportunity.  From the announcement:

The Solver Foundation team is looking for an intern for this summmer! A short description is below – this is a software development position, where the focus is on practical application of numerical optimization techniques. I believe in a practical, challenging, and hopefully rewarding experience where interns work on real code that relates to their areas of interest. If you’re interested, here’s what you should do:

  • Apply for the position here. Make sure you apply under the “Software and Hardware Development” category.
  • After you have applied, send a resume to natbr at microsoft dot com. We cannot guarantee a response to every inquiry due to volume.

A word of warning – this position is not for everyone. If things like simplex, L-BFGS, and KKT conditions are unfamiliar to you, this position might not be the best fit.

If you know what simplex, L-BFGS, and KKT mean, then this looks like an interesting way to spend the summer.  And they are pretty open with regards to education:

Bachelor’s, MS, or PhD students with deep knowledge of numerical optimization methods and software are particularly encouraged to apply.

This sounds a bit better than the Associate Dean gig I currently have, but I think I am stuck here.

David Johnson to Receive Knuth Prize

AT&T Labs researcher David Johnson will receive this year’s Knuth Prize from the ACM “for his contributions to theoretical and experimental analysis of algorithms”.  While Johnson is best known for his NP-Completeness book with Michael Garey, he has had an extraordinarily influential career in both the theory of approximation algorithms and in research on experimental evaluation of algorithms.  From the announcement:

The ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) will present its 2009 Knuth Prize to David S. Johnson of AT&T Labs for his contributions to theoretical and experimental analysis of algorithms.  Johnson’s innovations helped lay the foundation for algorithms used to address optimization problems, which involve the process of finding the best solution from all feasible solutions.  In addition, Johnson made many contributions to the early development of NP-completeness theory, which helps identify those problems that are hard to solve efficiently. The Knuth Prize, named in honor of Donald Knuth of Stanford University who has been called the “father” of the analysis of algorithms, will be presented at the ACM Symposium on Theory of Computing (STOC) June 6-8, 2010, in Cambridge, MA, where Johnson will present the Knuth Prize Lecture.

I got to know David almost 20 years ago when I agreed to coordinate one of his DIMACS Implementation Challenges.  This cooperation resulted in a book and, a decade later, a special issue of Discrete Applied Mathematics (with Anuj Mehortra). These Challenges are one of the ways David has explored issues in the evaluation of algorithms.  I had the chance recently to give a presentation on the effect of those Challenges.  David has had an enormous influence on me as I think about how to provide a firmer underpinning to the experimental analysis of algorithms and the way individuals and a field report on results.  This Prize makes me wish I had more time to spend on completing a planned system for reporting and confirming computational results.

I guess I am only surprised that David hadn’t already won this prize!  Very well deserved.

Final Olympic Results: Canada owns 45.25% of the Podium

Further to yesterday’s entry, we can now determine exactly how much of the podium Canada owns.  To determine the “winner” of the Olympics, you need to determine the relative values of gold, silver, and bronze medals (with the assumption that non-medalers do not count, which is arguably false, but necessary in order to stop me from spending the night compiling broader lists).  The final medal standings are (from nbcolympics.com):

Country Medalists GOLD SILVER BRONZE Total
CAN United States See Names 9 15 13 37
CAN Germany See Names 10 13 7 30
CAN Canada See Names 14 7 5 26
CAN Norway See Names 9 8 6 23
CAN Austria See Names 4 6 6 16

So, if you count every medal equally, then the USA won; if you only count gold, Canada won. But what if you count things 5 for a gold, 3 for a silver, and 1 for a bronze? Then the USA wins. How about 10, 5, 1? That would be Canada. Is there a set of points for Germany to win? It turns out there is not: anyone with operations research training would fiddle around for a while and figure out that 3/4 of the US medals plus 1/4 of the Canadian medals dominates the German medal counts.  Everyone else is dominated by the USA:  only Canada and the USA might win for a given set of medal weights.

Now not every point system makes sense. Giving 10 points for a bronze and 1 point for a gold might match up with certain egalitarian views, but would not really be in keeping with a competition. So we can limit ourselves to point systems with gold >= silver >= bronze. Further, we can normalize things by making the weights add up to 1 (since multiplying a weighting by a constant number across the scores doesn’t change the ordering) and having the weights be non-negative (since getting a medal shouldn’t hurt your score).

This gives a base set of linear equalities/inequalities. If we let wg, ws, and wb be the weights for gold, silver and bronze, we are interested in weights which satisfy

wg >= ws >= wb
wg+ws+wb = 1
wg, ws, wb >= 0

Now, which weights favor Canada? It turns out that, with some basic algebra, you can deduce (using the medal counts above) that Canada wins whenever wg > 8/13 (and ties with wg=8/13). So as long as you put more than 61.5385% of the weight on gold, Canada wins. This amounts to about 45.25% of the feasible region. USA wins on the remaniing 54.75% of the region. If Canada had won one more silver medal, they would have prevailed on more than half the reasonable region.

The diagram illustrates the weights for the USA and Canada, giving only the weights for gold and silver (the weight for bronze is 1-gold-silver). The red region are the weights where Canada wins; the blue is for the USA. Point A is “all medals are equal”; Point B is “count only gold and silver”; Point C is “Count only gold”.  The yellow line corresponds to the weight on gold equaling 8/13.

Bottom line: on this measure, the USA won the Olympics in an extraordinarily close race.  Canada may not have “Owned the Podium” but they came darn close.

Canada owns 40% of the Olympic podium

In this year’s Olympics, much has been made of the Canadian efforts to “own the podium“.  Canada has spent $118 million in training its athletes, far more than the US has spent ($55 million over four years).  Since it seems that, despite a late rush, the Canadian goal of winning more medals than any other country will not be met, the Own the Podium effort appears to be a failure.  But perhaps operations research can come to the rescue here.

The problem is, perhaps, in defining the goal.  By defining the goal in terms of overall medals, the Canadians were perhaps too modest.  If they had simply strived for excellence and defined their goal in terms of “Most gold medals”, then they would have succeeded:  they have 13 gold compared to the Germany’s 10 gold with two events to go.

It does seem kind of strange to define winning as “Most Medals”:  a bronze is not the same as a gold!  But it also seems pretty strange to only count gold:  the others seem to have some value.

Rather than look at any particular weighting of the medals, perhaps we should look at any reasonable weighting and see who wins.  If we give weights wg, ws, and wb to each of gold, silver, and bronze, and let ng, ns, and nb be the number of such medals won, then the score of a country is wg*ng+ws*ns+wb*nb.  The stated Canadian goal had (wg,ws,wb)= (1,1,1).  Counting gold only has (wg,ws,wb) = (1,0,0).  What other weights would be reasonable?

Clearly, gold is at least as valuable as silver which is at least as valuable as bronze, so we want wg>=ws>=wb.  Also, we can normalize so that wb+ws+wb=1 (since, for instance, (2,2,2) is the same as (1,1,1) which is the same as (1/3, 1/3, 1/3)).   With these requirements, there are only three teams that might be considered ahead at this point.  Consider the leading countries (from nbcolympics.com:

Country Medalists GOLD SILVER BRONZE Total
CAN United States See Names 9 14 13 36
CAN Germany See Names 10 12 7 29
CAN Canada See Names 13 7 5 25
CAN Norway See Names 8 8 6 22
CAN Austria See Names 4 6 6 16

Norway, Austria, and every other country (other than Germany and Canada) is dominated by the USA, so cannot be the winner, no matter the weight.

There are many weights other than (1,0,0) for which Canada is the winner.  For instance (.68, .16, .16) is also a win for Canada.  Even (.64, .32,.04) results in Canada in first.

Going through the grid of possible values, it seems that Canada is currently in first in about 40% of the cases;  the USA is in first in the remaining 60% of the weights.  Germany is never in first, being dominated by the combination of 74% USA and 26% Canada.  So perhaps it is fair to say that Canada owns 40% of the podium, trailing the USA with 60%.

If Canada were to beat the USA in hockey on Sunday, they would go up to 45%.  This assumes no further medals in the men’s 50km cross country.  But if a Canadian could also win the cross country, then the fraction of weights for which Canada wins goes up to 54.7%.  There is still a chance for Canada to “Own the Podium!”.

OPT-Art takes first place

My friend and co-author Bob Bosch was awarded First Prize in the Mathematical Art Exhibition held by the American Mathematical Society. This work was based on the Traveling Salesman Problem:

He describes his work in the exhibition catalog: “I began by converting a drawing of a two-component link into a symmetric collection of points. By treating the points as the cities of a Traveling Salesman Problem and adding constraints that forced the salesman’s tour to be symmetric, I constructed a symmetric simple-closed curve that divides the plane into two pieces: inside and outside. With a water jet cutter, I cut along this Jordan curve through quarter-inch thick, six-inch diameter disks of steel and brass. By swapping inside pieces I obtained two copies of the sculpture. Here, steel is inside and brass is outside… After I get an idea for a piece, I translate the idea into a mathematical optimization problem. I then solve the problem, render the solution, and see if I’m pleased with the result. If I am, I stop. If not, I revise the mathematical optimization problem, solve it, render its solution, and examine it. Often, I need to go through many iterations to end up with a piece that pleases me. I do this out of a love of mathematical optimization–the theory, the algorithms, the numerous applications.”

If you have a spare hour or two, be sure to check out the complete exhibition. Hmmm.. I have had some thoughts about translating my baseball schedules into Lego. I wonder if that could compete? Maybe not.

I am the proud owner of two Boschs: I received a copy of a domino portrait of myself (I periodically use the portrait as my photo). I also have a spectacular traveling salesman art based on work by Warhol. If you visit my office, I have placed it so it is seen at the end of a long hallway. It is a conversation piece for all the hallway residents. You can get your own Bosch at Domino Artwork. There are also instructions for teachers who want to make a domino portrait of Barack Obama, Abe Lincoln, Martin Luther King, and others as classroom projects.

Thanks to Twitter’s @wjcook (Georgia Tech’s TSP guru Bill Cook) for the pointer.

Operations Rules the National Academy of Engineering!

I see from Anna Nagurney’s blog that three operations research people have been elected to the National Academy of Engineering:

This group includes INFORMS (Institute for Operations Research and the Management Sciences) members: Dr. Cynthia Barnhart, the Associate Dean of Engineering at MIT, Dr. Hau Lee, of the Stanford Graduate School of Business, and the former editor of the journal Management Science, and Dr. William Pulleyblank, a Vice President of IBM.

This is a very well deserved honor for the three of them.

Free IBM/ILOG Software…

… if you are an academic.

As part of the “blue-washing” of ILOG, the academic licensing system for IBM’s OPL Studio, constraint programming system, and CPLEX has changed to become part of IBM’s Academic Initiative Program.  Here is the full announcement:

Effective February 15, 2010, IBM is offering no-charge full-version ILOG Optimization products via IBM’s Academic Initiative program (http://www.ibm.com/academicinitiative). This move builds on the availability of limited Teaching Editions available since August 2009, and now provides registered members with renewable one-year access to IBM ILOG OPL-CPLEX, CPLEX, CP Optimizer and CP for both teaching and research use. Registered members can access ILOG Optimization software at: https://www.ibm.com/developerworks/university/software/get_software.html, where they can search for ILOG Optimization or individual solvers by name. Depending on the search criteria, electronic assemblies will be retrieved for IBM ILOG OPL Development Studio, CPLEX, CP Optimizer or CP on all commercially available platforms. To run the software, members will also need to download a key from: https://www.ibm.com/developerworks/university/support/ilog.html, but are no longer required to install ILM. Note that as part of Academic Initiative, IBM also makes its professionally-developed training materials available for use in classrooms and labs at: https://www14.software.ibm.com/webapp/devtool/scholar/web/coursewarePickPage.do?source=ai-course-websphere.

I signed up for the program yesterday, and it was painless. Once I showed my inability to read simple instructions by missing the “how to download a key” section (an issue quickly and cheerfully handled by IBM), I was up and going with CPLEX. There are also some educational materials on both the CP and CPLEX side which look very well done.

INFORMS Practice Tutorials

The INFORMS Practice meeting coming up in Orlando has an extremely impressive set of methodology tutorials planned.  Here is the list:

360i
M. Kevin Geraghty, MS, Vice President, Research & Analytics, on “Marketing in Online Social Spaces.”

Business Forecast Systems, Inc.
Eric A. Stellwagen, BA, CEO & Co-Founder, on “Beyond Time Series Forecasting: Improving Forecasting Accuracy by Modeling the Impact of Promotions, Business Interruptions and Other Aperiodic Events.”

Chevron Corporation
Franklyn G. Koch, MS, Decision Analysis Practice Leader, Chevron Projects Resources Company, on “How Game Theory Yields New Insights to Decision Analysis in the Energy Industry.”

Federal Energy Regulatory Commission
Richard O’Neill, PhD, Chief Economic Advisor, on “Better, Smarter Electricity Markets: How Better Optimization Software Can Save Billions.”

Forio Business Simulations
Michael Bean, MS, President, on “How to Create Web-Based Simulations and Interactive Data Visualizations.”.

Georgia Institute of Technology
Ellis L. Johnson, PhD, Professor & Coca-Cola Chair; Industrial & Systems Engineering, on “A Framework for Choosing Optimization Software.”

Hewlett-Packard Corporation
Pramod Singh, PhD, Analytics Solution Architect, on “Marketing Campaign Optimization Is Hard (Especially in the Future).”

IBM Research
Robin Lougee-Heimer, PhD, Research Staff Member; Program Manager, COIN-O.R., on “Using Open-Source Solvers in Prime-Time Applications.”

Innovative Decisions, Inc.
Donald L. Buckshaw, MS, Senior Principal Analyst, on “The Balance Beam Process for Prioritization and Weight Elicitation.”

Intechné
Sanjay Saigal, PhD, President, on “Fueled by Randomness: Practical Probability Management.”

Intel Corporation
Erik F. Hertzler, MBA, Capital Supply Chain Staff Engineer, TME Capital Planning Group, on “Using Option Contracts with Suppliers to Reduce Risk and Build Win-Win Relationships.”

SAS Institute Inc.
Michael Gilliland, MS, MSE, Product Marketing Manager, Forecasting, on “Why are Forecasts So Wrong? What Management Must Know About Forecasting.”

Schneider National, Inc. & Princeton University
Ted L. Gifford, MS, Distinguished Member of Technical Staff and Hugo Simao, PhD, Senior Operations Research Engineer, on “Approximate Dynamic Programming Captures Fleet Operations for Schneider National.”

University of Cincinnati, College of Business
Jeffrey D. Camm, PhD, Professor and Head; Quantitative Analysis & Operations Management, on “The Art of Modeling.”

Xerium Technologies, Inc. & Vanguard Software Corporation
David Bryant, Vice President, Operations and Brian Lewis, PhD, Vice President, Professional Services, on “Global Optimization for Complex Production Scheduling Decisions.”

Veritec Solutions
Warren H. Lieberman, PhD, President, on “Effective Pricing.”

A few points: it is surprising how many tutorials are being given by non-academics: it will be fantastic to get a real-world view on these issues. Second, I am very impressed with the range of topics being discussed. Third, I would really like to see about 2/3 of these, but know that I will only have time for 2 or 3 (since Monday is fully scheduled for me for the Edelman competition). This is going to be frustrating! I think I will volunteer to do the conference scheduling in order to maximize the number of tutorials I can see.

If you are interested in this conference, note that the super saver registration deadline is March 1.

OR Snow Jobs

In my last post, I was grousing about being snowed in (Carnegie Mellon has been canceled three days and counting) and the need for more operations research in these sorts of situations.  I am pleased to see that my own university is taking up the challenge.  CMU President Jared Cohon has offered the services of the university to help the city create a state-of-the-art planning and operations system.  From an article in the Pittsburgh Post Gazette (and thanks to @bryanroutledge for pointing this out):

[Pittsburgh City Council Member] Mr. Peduto said CMU has offered to marshal faculty, staff and and students to create a “state of the art” snow removal tracking system that identifies priority areas for snow removal, maximizes the use of city equipment and follows through after emergencies with studies to guide budget decisions. It could also include geo-tracking of snow plows and treated streets, which is used in Maryland and elsewhere, he said.

The offer includes help from “the department of engineering and of computer science, the Heinz School” and other CMU departments, said Mr. Peduto, whose district includes the Oakland campus. “They’ve offered the full services of the university to create a better system.”

Snow removal has certainly been looked at by those in operations research. For instance, James Campbell of University of Missouri-St. Louis has been working on these problems for more than fifteen years. Even earlier, in 1976, Gene Woolsey wrote on snow removal in a delightful Interfaces article entitled “Three digressions on the routing of trucks” (the article is also available in the wonderful book The Woolsey Papers). In the article, Gene writes about giving a talk to city managers in Colorado:

After my speech, a city manager approached me with the following problem he had been facing for some time. It seems that the city council in his city had some years ago cleverly set the tim for council meetings at 6:00AM on alternate Tuesdays. The reason for this time should be immediately obvious, as it assures that only the citizen who is really upset will rise up to vent his spleen at that hour.

Unfortunately, when it comes to snow removal, lots of people rose early to complain. Gene’s solution?

Find out how the council members get to the council meeting from their homes, and clear those streets first. If you are not already doing this, and you do it in the future, I suspect that the complaints will go down.

That is really an OR snow job! If I had to guess, Pittsburgh discovered this plan years ago. This week’s storm suggests the need for a somewhat more all-encompassing approach.