Using mixed integer programming to assign air cargo to flights
flexport.engineering
flexport.engineering
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.
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.
You don't need 5–10× more wizards, though; you only need one wizard. If her ILP optimal solution is 0.1% better than the GA heuristic solution — which it might not be! — that might mean 3% higher profits for your company for the year. We are not talking about riveting sheet metal here, where productivity is roughly proportional to the number of workers.
And shrugging off the people who understand the model as 'wizards' shows the pretty neat cultural problem - people start to believe they can't and won't understand why they are getting solutions that they get. Any fool can understand GAs and get a feel for the risks involved.
A fundamental problem with soft constraints in MIP is that we cannot create cuts in the conflict graph. Technically, everything conflicts with everything else, but at very high badness. So, we then have to decompose the problem in a preconceived way, such as on geographical boundaries, time boundaries or using heuristics. This engineering can be challenging, especially given that MIP is often hard to debug.
So, like the sibling comment: I prefer meta-heuristics over constraint logic programming in many cases, but I do not deny that CLP/MIP can be very useful as well.
I know they are more similar to each other than meta-heuristics, but I'm not sure shy.
Assuming your linearization is good, at least you'll get a global optimum and the MIP gap. With meta-heuristics you have no clue where you could end up right?
1) Most of this work is a simplified copy of the papers I linked to. Special thanks to James Bookbinder and his team at University of Waterloo.
2) I'm an OR novice, and this is my first optimization project. I feel now that I can roughly model the flight assignment domain, but what the solvers do is a mystery to me, and when I read about Lagrangian relaxation and column generation, I'm lost. Fortunately I haven't needed those techniques in this project.
3) The mathematical model, when written down, looks mystifying even to me, the author, and that's unfortunate. My goal in writing this post was to reduce the mystery and explain the model in plain English (plus math notation), but in the end I'm afraid it still looks eye-glazingly complicated. Data science can be all too happy to cloak itself in mystery by writing down what are actually pretty basic equations. I don't have a good solution to this.
Most of all, I got such joy out of building the model one constraint at a time and seeing the solver follow my directions and spit out optimal solutions. I couldn't believe it worked. It was like I discovered electricity. Lastly, much credit goes to Flexport leadership for allowing me, an OR novice, to embark on this optimization project.
On (2) that's the great part about solvers, is that they're essentially quite incredible black boxes. Most people who actually do optimization theory also don't really know how they work. (My money is on black magic for a number of cases.) Kidding aside, writing one is always informative and interesting (and, with languages like Julia, surprisingly not complicated).
3) My suspicion is that matrix notation would actually improve the end result quite a bit. A lot of the constraints you've written down have very common structure (e.g., the total weight constraint can be written as y = X'g, where m is the vector of weights, or the required assignment constraint, X1 = 1, where 1 is the all-ones vector).
Writing this out and the corresponding descriptions next to it would make it much easier to parse. E.g., for the above cases
min tr(CX) + c'y
s.t. X1 = 1 (all items need to be shipped)
X'g = y (y is the total weight on each ULD)
etc.
To me, those are probably the most interesting category of blog posts. Some interesting technical content that isn't accessible to a layperson in the literature.
> My goal in writing this post was to reduce the mystery and explain the model in plain English (plus math notation), but in the end I'm afraid it still looks eye-glazingly complicated.
In places maybe, but not overall. You'll find that as you learn, the more deeply you understand the subject, the more simply you'll be able to explain it. That's not true the other way round - not everyone with deep understanding of a subject can explain things well!
I've watched with interest as INFORMS has tried to rebrand OR as data science, but this is the first time I've seen anyone refer to it as such in the wild.
I hope you're able and encouraged to develop your interest in this area. It's actually all over the place (I'm currently working in rail), usually cloaked by a less sexy job title :)
I like to think that MIP is a framework that meets halfway between a natural modeling language and a natural solution language. The reason it's good is that the framework naturally lends itself to abusing linear programming as a subroutine, which can cut out a large amount of search state space. And you tend to find you can encode many problems without too much difficulty with just a handful of tricks.
You can encode a great deal into MIP. Piecewise linearized versions of non linear problems, or logical constraints.
Some interesting applications I've seen or played with:
- Verifying neural nets https://github.com/vtjeng/MIPVerify.jl
- Solving the classical Ising Model http://www.philipzucker.com/solving-the-ising-model-using-a-...
- Global Robot arm kinematics http://www.philipzucker.com/2d-robot-arm-inverse-kinematics-...
- model predictive control with collisions constraints http://www.philipzucker.com/flappy-bird-as-a-mixed-integer-p... See Russ Tedrake's group https://groups.csail.mit.edu/locomotion/pubs.shtml
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 )
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.
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?
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.
Using Python sum() is quite slow, so the packages provides a kind of lazy quicksum().
> 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 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.
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.)
Edit: I can personally attest that potential bootstrappers would find fertile ground making a service to do this stuff for transportation companies. I know of many who basically don't try to solve this problem because they don't have the talent and don't trust their ability to maintain something bought from a consultant. They need a service they can offload it to.
It occurs to me that such a "service" could to a significant extent pick winners and losers among transportation companies; whoever they chose to plan for would have lower costs by several percent, and so would have profits several times higher than the competition.
https://ampl.com/MEETINGS/TALKS/2019_09_Bolzano_Model-Based.... https://ampl.com/MEETINGS/TALKS/2018_08_Lille_Tutorial1.pdf
A recording of the first presentation will be available soon. The first uses a simpler example, but both were prepared for audiences not committed to the model-based approach. Their purpose was to familiarize people with model-based optimization and the circumstances in which it has clear advantages.
"An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers."
Kidding aside, generally this is very true, but for a surprising number of practical problems, the LP relaxation and some redundant constraints will often have zero integrality gap. (In many other problems, you’re hosed, so there’s also that.)
EDIT: For context, this is how LDPCs are decoded in robust cases. https://people.eecs.berkeley.edu/~wainwrig/Papers/FelWaiKar0...
I guess I react strongly whenever I hear this kind of sentiment because the result of rounding the continuous solution can be arbitrarily bad, but now we have a false sense of confidence that we did some kind of optimization, when we really didn't. My experience has been that rounding continuous solutions to integer gives some pretty interesting and incredibly bad solutions.
For posterity's sake, Wolsey has a good example of how things can go poorly in the introduction of the book Integer Programming:
max 1 x1 + 0.64 x2
st 50 x1 + 31 x2 <= 250
3 x1 - 2 x2 >= -4
x1, x2 >=0
x1, x2 integer
I'll also contend that the integer programming solvers nowadays are really good. If we can get away with rounding the solution, then the the solver will find the solution in only a few iterations because it often does precisely that in order to go through the branch, bound, and cut algorithm. The difference is that a good solver can get a certificate of optimality when it finds the solution, so that we know we're right.
User requests aren't always "here's a problem + the data, solve this to optimal". Here are other examples:
1. "here's the problem + data, solve it well enough within 10s" 2. "here's the problem + data, solve it well enough with a subset of the data" 3. "here's the problem + data, solve it partially, and then when near real-time updates come in, update solution to take new information into account"
While theoretically polynomially reducible, if the rewriting multiplies the number of variables by 1000 then it’s likely not good in practice.
Either way, I agree that there is likely some way in which the original commenter’s problem can be solved via MILP/MICP methods (indeed, I’ve found very few problems in practice that cannot be easily reduced) :)
IRL they just get rolled and we treat it as a new problem with a different set of schedules.