Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Using mixed integer programming to assign air cargo to flights

flexport.engineering

Post reply on HN
Print view View original

51–58 of 58 posts

Re: Using mixed integer programming to assign air cargo to flights

#51

Post by 4er »

We're seeing here the debate over model-based vs. method-based approaches to optimization. My argument for the model-based approach is reflected in these two sets of slides:

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.

Re: Using mixed integer programming to assign air cargo to flights

#52

Post by astrec »

andrew771 wrote: post #37

Hi all, author here. I'm very humbled that this made it to the front page! A few things I want to say: 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,…

Congrats on the post. Enjoyed it.

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 :)

Re: Using mixed integer programming to assign air cargo to flights

#53

Post by 7thaccount »

edejong wrote: post #11
zelos wrote: post #7

Earlier quoted context omitted.

Could you handle your example in MIP through the objective function, making time outside normal hours expensive, but balancing that with a positive value for lunchtime? Possibly with an integer value limiting the number of days where normal hours can be violated?

In addition to this remarks of the sibling comment, we don't always have a well-understood objective function. For example, how much is lunchtime worth compared with time outside normal hours? What we can say is that there is a certain 'badness' to it, which should increase exponentially or polynomially as we thread further outside of our preferred domain. These are known as soft constraints. A fundamental problem wi…

Aren't CLP/MIP very different mathematically/programatically?

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?

Re: Using mixed integer programming to assign air cargo to flights

#54

Post by 7thaccount »

kragen wrote: post #39
andrew771 wrote: post #38

Earlier quoted context omitted.

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 Pyom…

> 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…

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.

Re: Using mixed integer programming to assign air cargo to flights

#55

Post by 7thaccount »

comment_guy wrote: post #13

That's pretty cool these guys get to put 1950's math to work in real life. In my experience, I was never able to sell this idea to anyone based on the (potentially justified) excuse that it was completely unmaintainable without a math guy around. 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 basic…

Lots of logistics and truck companies use this behind the scenes (source: my friend writes MIP models for a trucking company). Also...many industries have been using LP/MIP models for ages. The entire US grid commits generators and dispatches them with MIP solvers running some MASSIVE models 24/7 (source: I work with that software).

Re: Using mixed integer programming to assign air cargo to flights

#56

Post by leethargo »

kragen wrote: post #20
leethargo wrote: post #5

Earlier quoted context omitted.

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 performan…

> 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…

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.

Re: Using mixed integer programming to assign air cargo to flights

#57

Post by leethargo »

leethargo wrote: post #56
kragen wrote: post #20

Earlier quoted context omitted.

> 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…

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().

Re: Using mixed integer programming to assign air cargo to flights

#58

Post by leethargo »

anonsivalley652 wrote: post #46
mochomocha wrote: post #32

Earlier quoted context omitted.

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

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
Post reply on HN