[mccourt]

I'd also like to throw in some work by a former colleague of mine at Argonne, Sven Leyffer on nonlinear programming: - A compendium he co-edited named (appropriately enough) Mixed Integer Nonlinear Programming - A review paper he co-authored for Acta Numerica: http://www.mcs.anl.gov/papers/P3060-1112.pdf

Also, yeah, the "Alexander Schrijver - Theory of Linear and Integer Programming" reference is solid.

[wolfgke]

The survey article by Sven Leyffer is a good paper, but comes from a completely different direction:

It comes from people from convex optimization trying to additionally apply some integrality conditions (a little bit as second-class citizen). On the other hand classical combinatorial optimization is integrality conditions as first-class citizen. I, coming from (M)ILP, would argue that the MINLP people coming from convex optimization tend to sidestep all the problems that make ILP so hard (and interesting). On the other hand MINLP people would equally vocally argue that the (M)ILP people tend to prefer "academic" problems and don't grasp how many important research questions they miss.

It's up to the reader to decide which side is right. :-)

My personal opinion in this "flamewar" is that if you come from a computer science background (in particular theoretical computer science) you will probably prefer classic MILP culture. On the other hand if you come from engineering you will probably prefer MINLP theory as outlined in Sven Leyffer's survey paper.

[mccourt]

Yeah, I think that's probably the split - folks from computer science/discrete math on one side and folks from engineering on the other. I grew up in math, but I was on the numerical analysis side so I definitely ended up on the MINLP side, which is why that's what I generally reference. There is certainly something elegant about ILP problems which gets lost when treating them with the sledgehammer that is gradient-based convex optimization.

[wolfgke]

> There is certainly something elegant about ILP problems which gets lost when treating them with the sledgehammer that is gradient-based convex optimization.

It is funny that you call gradient-based convex optimization a "sledgehammer" since people working in combinatorial optimization (opposed to ILP) tend to denote ILP methods (e.g. cutting plane algorithms, branch & bound, branch & cut, relaxation hierarchies, ...) also as a "sledgehammer". :-D They are just jealous. :-)