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 (&quot;linear programming&quot; in the jargon, although that&#x27;s as misleading a term as &quot;analog computer&quot; or &quot;military intelligence&quot;) gives you enough interesting information about the MIP problem to solve it enormously more efficiently than you can with a generic SAT solver.<p>One of the notes in Dercuano is an overview I put together of the field last year: <a href="http:&#x2F;&#x2F;canonical.org&#x2F;~kragen&#x2F;dercuano-20191230.tar.gz" rel="nofollow">http:&#x2F;&#x2F;canonical.org&#x2F;~kragen&#x2F;dercuano-20191230.tar.gz</a> file notes&#x2F;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&#x27;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.<p>I didn&#x27;t evaluate embedded DSLs like Pyomo in any depth, unfortunately.<p>I&#x27;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.)<p>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 &quot;the ultimate in agile software development&quot;, 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.<p>(There&#x27;s also an inferior PDF rendering of Dercuano for cellphones that can&#x27;t handle tarballs: <a href="http:&#x2F;&#x2F;canonical.org&#x2F;~kragen&#x2F;dercuano.20191230.pdf" rel="nofollow">http:&#x2F;&#x2F;canonical.org&#x2F;~kragen&#x2F;dercuano.20191230.pdf</a> )