Using mixed integer programming to assign air cargo to flights

MIP is NP-complete; you can reduce any problem in NP to it. But there is a large and interesting set of MIP problems where the continuous relaxation to ordinary linear optimization ("linear programming" in the jargon, although that's as misleading a term as "analog computer" or "military intelligence") gives you enough interesting information about the MIP problem to solve it enormously more efficiently than you can with a generic SAT solver.

One of the notes in Dercuano is an overview I put together of the field last year: http://canonical.org/~kragen/dercuano-20191230.tar.gz file notes/linear-optimization-landscape.html. It seems that the best free-software solver is COIN-OR CBC, and the best free-software modeling language is GMPL, aka GNU MathProg, which is compatible with the popular proprietary linear-optimization modeling language AMPL, and includes its own somewhat weaker solver GLPK; it's much easier to get GLPK solving a problem than CBC, but the relevant incantations are in the note. But some of the proprietary solvers are much better; most of them are available on the NEOS Server.

I didn't evaluate embedded DSLs like Pyomo in any depth, unfortunately.

I'm somewhat disappointed with the Flexport post, which I feel is badly formatted and uses needlessly obscure notation and then never gets around to actually writing down a model in MathProg or Pyomo or anything similar. But I guess my own note is only a little better, and the Flexport article at least gives a MIP model of a nontrivial problem. (There are many more such examples in the GNU MathProg distribution, and MIPLIB has a wealth of extremely nontrivial ones.)

Mathematical optimization in general (optimization in the sense of minimizing a possibly constrained function, not in the sense of making code run faster) amounts to programming at a higher level; I think it was Norvig that described it as "the ultimate in agile software development", because you basically just write the tests. And linear optimization is the best-developed subfield of mathematical optimization: linear solvers can solve enormously larger problems than more general solvers.

(There's also an inferior PDF rendering of Dercuano for cellphones that can't handle tarballs: http://canonical.org/~kragen/dercuano.20191230.pdf )

If anyone is interested in learning more about MIP and other discrete optimization topics, there is a great MOOC on coursera (link: https://www.coursera.org/learn/discrete-optimization/). Lectures are quite engaging, delivered by enthusiastic and a bit eccentric prof. Van Hentenryck. Also there are no stupid quizzes, just 5 problems (with 6-8 instances each, ranging from comparatively small to huge) that you need to solve (in any programming language) in order to pass. The only drawback is significant investment of time it requires.

In my experience, each sufficiently complicated model becomes non-linear in some respect. For example, you might want to work with margins for time-slots that are non-linear but smooth.

So, even though I've worked with constrained linear programming in the past, I tend to prefer algorithms with meta-heuristics, such as simulated annealing or Tabu search. Although this might not provide the 'best' solution, it provides a wider range of modelling tools.

To elaborate a bit on a use-case. Lets say we want to plan a high-school roster. Teachers might have a maximum of 8 hours per day of work, but if we make a hard cut-off at that time, we might miss an interesting 8:15 schedule that gives a teacher more time to have proper lunch. If, furthermore, we do not break the 40 hr./week rule, it might be a workable schedule. Also, it provides the search algorithm a usable gradient, so the search space becomes smooth and easier to navigate. Finally, if we provide several top solutions, we give a human planner information on how the problem is (over-)constrained.

@dunkelheit, thank you for the link to the course. I'll give it a try!

It is sort of trivially true that any nonlinear model in practice can be approximated by a sufficiently complicated linear model. So yes, probably. However that is not without cost. It reduces the amount of computer time required and increases the amount of human interpretation and attention required (+ increased time to linearise the original model). On the face of it that is a questionable trade.

My anecdotes are somewhere close to the grandparent's where I'd prefer to see the heuristic method tried first before a linear model is attempted. If nothing else implementing a GA or simulated annealing algorithm is generally very cheap and debuggable in a way that moderately complicated linear models aren't. I'd guestimate that there are 5-10x more programmers who can implement a genetic algorithm than could tackle mixed integer optimisation. Debugging AMPL code is not a straightforward or satisfying experience.