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

41–50 of 58 posts

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

#41

Post by LolWolf »

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

Heya! Very nice and congratulations on the front page :)

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.
Congrats again on the front page and the article!

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

#42

Post by kragen »

LolWolf wrote: post #40
agravier wrote: post #31

Earlier quoted context omitted.

mixed integer convex programming, not comic (unfortunately; although I hope someone takes this as a challenge). Or maybe you meant conic programming? As in MISOCP

Oh, oops, I just realized I actually wrote "comic," oops! (My phone really does not like the word conic for whatever reason...) Would be a fun (and uhh, interesting?) challenge indeed, whatever that would entail :)

It fits in well with your username! There have been a number of (computer) programming environments that used a comic-strip-like format to depict a sequence of events; I think some are profiled in Watch What I Do and/or Your Wish Is My Command, which I don't have with me at the moment.

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

#43

Post by kxyvr »

LolWolf wrote: post #19
_v7gu wrote: post #14

Earlier quoted context omitted.

If I may quote from the Integer Programming chapter in Vohra's book, "Before proceeding you should convince yourself that no ‘simple’ scheme based on solving the underlying linear program and rounding the resulting solution can find the optimal integer solution."

Depends on the problem (in max-flow, min-cut the trivial rounding scheme gets you the optimal point immediately :). 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 c…

I suppose that we could also state that solving with a totally unimodular matrix also absolves us from going through the trouble of going through branch and bound, but that's a pretty niche case.

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 = -4
      x1, x2 >=0
      x1, x2 integer
The linear programming solution is (376/193,950/193), which is approximately (1.9482,4.9223). The integer optimal solution is (5,0), which is far away.

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.

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

#44

Post by kristianp »

They did a poor job of explaining what Integer Programming is. Here's the wikipedia intro:

"An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers."

https://en.wikipedia.org/wiki/Integer_programming

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

#45

Post by anonsivalley652 »

kragen wrote: post #2

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…

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

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

#46

Post by anonsivalley652 »

mochomocha wrote: post #32
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…

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.

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

#47

Post by roenxi »

kragen wrote: post #22
roenxi wrote: post #10

Earlier quoted context omitted.

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

> I'd guestimate that there are 5-10x more programmers who can implement a genetic algorithm than could tackle mixed integer optimisation. 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…

:o That is cheating! You can't assume that one solution is better than another then use that assumption to support the conclusion that it is better. There is no particular reason to believe the ideal solution to the linear approximation is better than the approximate solution of a non-linear model.

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.

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

#48

Post by kragen »

roenxi wrote: post #47
kragen wrote: post #22

Earlier quoted context omitted.

> I'd guestimate that there are 5-10x more programmers who can implement a genetic algorithm than could tackle mixed integer optimisation. 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…

:o That is cheating! You can't assume that one solution is better than another then use that assumption to support the conclusion that it is better. There is no particular reason to believe the ideal solution to the linear approximation is better than the approximate solution of a non-linear model. And shrugging off the people who understand the model as 'wizards' shows the pretty neat cultural problem - people start…

The meaning I intended was not the meaning you read.

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

#49

Post by rkangel »

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

> Most of this work is a simplified copy of the papers I linked to

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!

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

#50

Post by rkangel »

mint2 wrote: post #18

What happens if/when shipments miss their ready times?

Presumably there are contractual penalties associated with missing delivery times, that then map to the cost of doing things. In the real world if you can miss the deadline on one delivery, and that allows everything else to work much more simply and cheaply then that's probably the right call.
Post reply on HN