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

11–20 of 58 posts

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

#11

Post by edejong »

zelos wrote: post #7
edejong wrote: post #6

In my experience, each sufficiently complicated model becomes non-linear in some respect. For example, you might want to work with margins for time-slots that are non-linear but smooth. 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 provide…

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

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

#13

Post by comment_guy »

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

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

#14

Post by _v7gu »

siilats wrote: post #12

Cvx solves a relaxed problem trivially in matlab and then you can heuristically round to integer. http://stanford.edu/class/ee364b/lectures.html Under L1 convex cardinality

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

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

#15

Post by kragen »

zelos wrote: post #7
edejong wrote: post #6

In my experience, each sufficiently complicated model becomes non-linear in some respect. For example, you might want to work with margins for time-slots that are non-linear but smooth. 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 provide…

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?

Yes, as I explained in https://news.ycombinator.com/item?id=22157419 you can model literally anything in MIP if it's in NP, but the structure of the problem may or may not peek through enough for your solver to run efficiently. Some MIP solvers are effectively alien technology from the future, so this can be worthwhile, but it isn't always.

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

#16

Post by LolWolf »

aliceryhl wrote: post #3

Oh lucky you, your optimization problem is linear. I do something similar, but we have to use heuristics because our problem can't be modelled as a linear problem.

I’d be curious to hear more... often a lot of nonlinear problems can be turned into mixed integer cone programs (MICPs) which are also often fast to approximately or exactly solve in practice.

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

#17

Post by kragen »

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…

Many of the fundamental algorithms used were developed during the 1980s and 1990s, as were modeling languages like AMPL. So it's not 1950s math, even if the "simplex algorithm" was discovered in 1947.

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.

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

#19

Post by LolWolf »

_v7gu wrote: post #14
siilats wrote: post #12

Cvx solves a relaxed problem trivially in matlab and then you can heuristically round to integer. http://stanford.edu/class/ee364b/lectures.html Under L1 convex cardinality

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 cases. https://people.eecs.berkeley.edu/~wainwrig/Papers/FelWaiKar0...

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

#20

Post by kragen »

leethargo wrote: post #5
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…

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

Post reply on HN