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

Researchers have found a faster way to do integer linear programming

quantamagazine.org

Post reply on HN
Print view View original

201–210 of 210 posts

Re: Researchers have found a faster way to do integer linear programming

#201

Post by mturmon »

dang wrote: post #79
mturmon wrote: post #36

Earlier quoted context omitted.

If you don’t know, you are in for a treat. Here is Bellman’s own description of how he came up with the term “dynamic programming “ — I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes. An interesting question is, ‘Where did the name, dynamic programming, come from?’ The 1950s were not good years for mathematical research. We had a very interesting gentleman…

Oh gosh—I was vastly out of the loop: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que... Thanks! That's a classic for sure.

Not least, for the delightful characterization of that versatile word, "dynamic"!

Re: Researchers have found a faster way to do integer linear programming

#202

Post by Bimos »

xkcd386 wrote: post #160
Bimos wrote: post #106

Earlier quoted context omitted.

Thanks for your information. I think it really bridge the gap between the people who are interested in this algorithm and MILP "users". I have two more questions. 1. Usually we deal with models with both integer and continuous variables (MILP). Conceptually B&B tackles ILP and MILP in similar ways. Is there any difficulty for lattice based method to be extended to solve MILP? 2. How likely do you think this lattice t…

> Is there any difficulty for lattice based method to be extended to solve MILP? I don't think that continuous variables are an issue. Even when all the explicit variables are integer, we have implicit continuous variables as soon as we have an inequality: the slack of that inequality. There is probably some linear algebra trick one can use to transform any problem into a form that is convenient for lattice-based alg…

Thank you!

Re: Researchers have found a faster way to do integer linear programming

#203

Post by eru »

tylerhou wrote: post #190
eru wrote: post #55

Earlier quoted context omitted.

Yes? We do manage to solve ILP problems in practice quite nicely. In fact, most NP problems that you come across in practice are relatively tractable for most practical instances. Eg for the knapsack problem you have to actually work very hard to get a hard instance in the first place.

It was a response to > It's surprising how many problems can be formulated as linear optimization. i.e., all problems in NP (which is most problems you're likely to encounter on a day-to-day basis) can be solved with ILP, and many of them can be solved or well-approximated quickly.

You are technically correct.

To interpret the observation a bit more meaningfully:

It's surprising how many problems can be formulated as continuous (!) linear optimisation.

And it is surprising how many problems can be formulated somewhat naturally as mixed-integer linear optimisation. And 'many of them can be solved or well-approximated quickly', exactly as you say.

---

I seem to remember that continuous linear optimisation is to P what integer linear optimisation is to NP. In the sense that there's some natural reduction of many problems in P to continuous linear optimisation.

(I don't remember if that's just an informal observation, or whether there's some formal way to reduce problems in P in eg linear time to linear optimisation? https://en.wikipedia.org/wiki/P-complete#P-complete_problems mentions Linear Optimisation as being P-complete, but I haven't vetted all the fine-print, eg about what specific reduction they are using.)

Re: Researchers have found a faster way to do integer linear programming

#204

Post by eru »

ubj wrote: post #67
eru wrote: post #53

Earlier quoted context omitted.

You are right that integer linear programming is NP-hard; but faster algorithms for continuous linear programming are also super interesting and impactful. Continuous linear programming is also _hard_. Not in the sense of NP-hard, but in the sense of there being lots of algorithmic and engineering aspects that go into an efficient, modern LP solver. Even just the numerics are complicated enough. (And many integer lin…

True, these are all fair points! I didn't intend to diminish the impact or complexity of linear programming solvers. Well-written solvers are some of the most useful and powerful computational tools that exist today.

Definitely. Advances in numerics in general, matrix multiplication in particular, and solving of systems of (continuous) linear equation and continuous linear programming are to computing what advances in basic material science are to engineering.

Modern concrete and steel (and plastics etc) allow you to build so much more advanced, but also simpler, than the kinds of wacky shenanigans people had to pull off in eg the 19th century just to get high pressure steam engines to work (if they could do that at all).

Re: Researchers have found a faster way to do integer linear programming

#205

Post by WJW »

tylerhou wrote: post #191
WJW wrote: post #179

Earlier quoted context omitted.

Do you have a link to some materials to help get me started? I did an optimization/ILP MOOC once and that was indeed a lot of fun.

https://people.seas.harvard.edu/~cs224/fall14/lec.html In particular, seems like lectures 9-11 have LP content.

Thanks!

Re: Researchers have found a faster way to do integer linear programming

#206

Post by PartiallyTyped »

WJW wrote: post #179
PartiallyTyped wrote: post #101

Earlier quoted context omitted.

One of my favourite courses in grad school was approximation algorithms and it involved reductions to LP. Lots of fun, can recommend.

Do you have a link to some materials to help get me started? I did an optimization/ILP MOOC once and that was indeed a lot of fun.

We used the book "the design of approximation algorithms"

https://www.designofapproxalgs.com/book.pdf

Re: Researchers have found a faster way to do integer linear programming

#207

Post by Chinjut »

"The problem’s dimension influences the dimension of this shape: With two variables it takes the form of a flat polygon; in three dimensions it is a Platonic solid, and so on."

It certainly needn't be a _Platonic_ solid! The author must have meant to write merely "solid" or "polyhedron" or some such thing

Re: Researchers have found a faster way to do integer linear programming

#208

Post by nojs »

ford wrote: post #4

Software engineers interested in ML/algorithms should learn about linear programming. It's surprising how many problems can be formulated as linear optimization. For example, in college I was talking to my Industrial Engineer friend about the average minimum number of swaps required to place billiards balls in an acceptable starting position in the rack (triangle). We both happened to write programs that used monte-c…

When I traded betting markets I was able to formulate a lot of multi-market arbitrage problems as ILP. The integer part turned out to be quite important as I recall, since you can generally only trade in whole cents.

Re: Researchers have found a faster way to do integer linear programming

#209

Post by raverbashing »

7thaccount wrote: post #198
raverbashing wrote: post #88

Earlier quoted context omitted.

Honestly? The search for the 'exactly optimal solution' is way overrated I think you can get a moderately efficient solution using heuristics at 1/10 of the time or less Not to mention developer time and trying to figure out which constraints make your problem infeasible. Especially as they get more complicated because you want to make everything linear

The vast majority of the United States power grid (many thousands of power plants) are optimized in auctions every hour for the next day and every 5 minutes on the operating day. Finding the globally optimal solution is pretty important for both fairness and not wasting billions of dollars each year. I'd agree with you for a lot of problems though, but keep in mind there are plenty where they need full optimality or…

Yes and your very complex linear branch and bound solution won't run in 5 min.

That's what I'm getting at

Re: Researchers have found a faster way to do integer linear programming

#210

Post by vpastore »

aleph_minus_one wrote: post #148
benterix wrote: post #107

Earlier quoted context omitted.

And given how much the licenses cost, I'd love a new player to show up and bring them down to a reasonable level.

Since version 8.0.3, SCIP is available under Apache 2.0 License: > https://www.scipopt.org/index.php#news So the new player to show up is here. :-)

[dead]
Post reply on HN