In New York doing Mixed Integer Programming

I am in New York at Columbia University, attending the Mixed Integer Programming (MIP) workshop. This workshop series was started about 5 years ago, and has grown into a hundred person workshop/conference. It is still run pretty informally (no nametags: I guess it is assumed that everyone knows everyone else. Having just shaved off my beard, I would prefer letting people know my name rather than relying on their ability to recognize me!).

So far, the most interesting aspects have been approaches much different than current practice. Rekha Thomas of the University of Washington had a very nice talk on a variant of Chvatal Rank (called Small Chvatal Rank) which involved using Hilbert basis calculations to find normals of facets of the integer hull (you can think of this as Chvatal rank independent of the right hand side). I’m not sure if it is useful, but it certainly generated a number of neat results. Peter Malkin of UC-Davis talked about using systems of polynomial equations to prove the infeasibility of problems like 3-coloring. I have seen versions of this work before (given by coauthor Susan Margulies) and always begin thinking “this can’t possibly work” but they are able to prove a lack of 3-coloring for impressively large graphs.

One of the most intriguing talks was given by John Hooker, who is exploring what he calls “principled methods of modeling” (or formulation). John has a knack of looking at seemingly well-known approaches and seeing them in a new and interesting way. It is not yet clear that this principled approach gets you anything that is not folklore formulation tricks, but it is interesting to see a theoretical underpinning to some of the things we do.

Postscript. Now that I think about it a bit more, John did present a problem that would have been difficult to formulate without his principled approach. I’ll try to track down an explanation of that example.