Comment by kragen | Hacker News Reader

Comment by kragen | Hacker News Reader

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 )

Embedded DSLs in Python sometimes have a lot of overhead because of the way large expressions are built with operator overloading (x + y + z + ...), creating lots of intermediate objects.

But there are solver-specific alternatives, such as for Gurobi or MOSEK that provide good performance, as well as vector-oriented modeling such as cvxpy.

Myself, I'm partial to Julia's JuMP as an embedded DSL that has good performance, a general purpose language and "nice" syntax, that is comparable to algebraic modeling languages.

> Embedded DSLs in Python sometimes have a lot of overhead because of the way large expressions are built with operator overloading (x + y + z + ...), creating lots of intermediate objects.

Is this really a concern in practice? My mental model is that the algebraic model is, you know, half a page to 10 pages of code without any loops or recursion, and you evaluate it to get an MPS file, and you feed that MPS file to your solver, which then chews on it for the next 15 seconds to 15 days. It's hard to imagine that Python's dynamic dispatch overhead would contribute more than a few milliseconds to this multi-day process. What am I missing?

There are low-latency applications of MIPs where such overheads matter. Sometimes one needs to solve small MIPs very often under strong latency requirements.

Indeed there are, but you don't to re-run the Python code expressing the model to do that. You build the model once, then tweak the numbers in the constraints and weights.

There's always rewriting in other languages or transpilation. If a framework is so crucial, not just for prototyping, perhaps the runtime components (as opposed to model building) could be ported to something like C, C++ or Rust.

True. For some classes of problems, code generation is actually used here: https://cvxgen.com/docs/index.html

I can't find a benchmark right now, but the specific issue with Python in this case was not dynamic dispatch, but memory allocation and GC.

And yes, that lead to having the model creation time dominate the solve time by an order of magnitude. So it was a large-but-easy problem. Happens in particular when you use LP or QP, as opposed to MIP.

Actually, see the issue described here: https://stackoverflow.com/questions/38434300/why-is-quicksum...

Using Python sum() is quite slow, so the packages provides a kind of lazy quicksum().

Edit: formatting

> badly formatted

I apologize for this. Flexport uses the Medium.com platform, and I couldn't find any better way to write math notation than embedding LaTeX gists.

> needlessly obscure notation

I agree 100%! I would like to hear ideas about how to eliminate this notation. I feel it's keeping too many people away from the field.

> never gets around to actually writing down a model in MathProg or Pyomo or anything similar

Again, spot on. The post was long enough without explaining how to do it in Pyomo, so I'm saving that for part 3.

> I agree 100%! I would like to hear ideas about how to eliminate this notation. I feel it's keeping too many people away from the field.

I didn't mean you shouldn't use the standard mathematical notation, which seems to be what you're talking about. I meant you should use it in the standard way. Don't use superscripts that are neither powers nor variables; for example, don't use U^M to mean "max weight capacity" and U^V to mean "max volume capacity". UM and UV, M and V, or even U_M and U_V would be an improvement. Don't typeset your display math with the subscripts to the right of the Σ as if it were part of a paragraph; put them underneath. Don't put extra spaces in the middle of your subscripts. If you only have two subscripts (with numeric values, not things like "M" and "V"), it's okay and probably better to make one of them a superscript, especially if you parenthesize it to reduce the chance that people will mistake it for a power. Don't leave out your variable of summation when you write Σyⱼcⱼ or, as you did in another case, write it in upper case. Don't write sets as comma-separated sequences of elements without {} around them.

Alternatively you could write the whole model down in GNU MathProg, which is more verbose but not that much, arguably more precise, and universally understood by people who work in the field in anything other than pure theory. Or Pyomo, which I've never written anything in, but assume can't be that much worse or nobody would use it. Either way it would be easier to use multi-letter names for your variables and parameters if you thought that made things clearer.

I don't think the standard mathematical notation is keeping people away from the field; students who already know basic algebra don't seem to have much trouble with the notation. Figuring out how to make reasonable MILP models or how to diagnose the problem when the solver says your model is infeasible, those seem to take a lot more work.

> Flexport uses the Medium.com platform,

Why? You want to screen people out of your recruiting process that haven't signed up for Medium accounts? Or you want to signal that you're a nontechnical company that can't figure out how to install Wordpress? There are Docker images for that now, you know.

On the last note, I'm guessing the engineers or analysts working on MIP models want to work on that and not also go learn and maintain their own blog site where Medium suffices. The article seems to be free to read without an account. I've read dozens of Medium blog posts over the past few years and learned all about companies without making an account. It is proprietary and closed off like FB and other sites are, but that's still a lot easier than WordPress + Docker woes if that is not part of your core business.

What's neat is the tackling of NP and NP-complete problems that can do better than humans given infinite time and infinite Excel-fu.

I wonder about how to go further to attack NP-hard problems, like Traveling Salesman, because it maybe that P != NP, and existing approximate holistic solutions lead to suboptimal solutions as anyone using Google Maps knows. At what point do we seriously consider letting AI/ML to do algorithm design itself? (Self-programming systems.)

Reply on news.ycombinator.com