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

141–150 of 210 posts

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

#141

Post by _Algernon_ »

WhitneyLand wrote: post #108
eigenket wrote: post #105

Earlier quoted context omitted.

Going on arXiv computer science and searching for the string "runtime" returns 6135 results, many of which seem use it in the sense we're talking about here. https://arxiv.org/search/cs?query=runtime&searchtype=all&abs... In any case Quanta Magazine is not a formal academic journal, and neither is hacker news. We're having an informal discussion about a popular science article.

Your 6135 results are ignoring that there are two different usages. I said “run time” relates to algorithmic complexity. That’s one definition. The other definition is also valid in research, as it relates to environments. Like Java. The first result in your query is an example of the second definition. It is not an example showing these are interchangeable.

Realizing when you're wrong and dealing with it with grace is a skill that needs to be learned, and one you should take the time to practice.

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

#142

Post by ricogallo »

3abiton wrote: post #139
sanketskasar wrote: post #136

Can the folks on HN guide me on how to learn and master linear programming and create a consulting career out of it? I've been exposed to linear programming slightly at work and I find this to be powerful technique to solve a lot of problems that are currently written with generic software programming with better results. I feel there is good opportunity to create a consulting career/business out of it, though having…

To be fair, I don't see why LP is still being used for many applications nowadays and not replaced, as it tends to be a brute force techniques.

Would you care to elaborate?

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

#145

Post by 7thaccount »

keithalewis wrote: post #130
7thaccount wrote: post #90

Earlier quoted context omitted.

Computational economics is a relatively new field where intelligent agents are used with lots of runs instead of general optimization solvers I believe. Pretty nifty. One of my colleagues publishes a good bit on it.

Wassily Leontief and his Nobel Prize would like to have a chat with your colleague.

Can you be more specific?

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

#146

Post by isaacfung »

eru wrote: post #53
ubj wrote: post #17

Minor nitpick, but the title of this submission should specify "Integer Linear Programming", since the integer part is a much bigger deal. Polynomial time algorithms have been known for linear programming for decades; _integer_ linear programming is NP-hard.

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…

Yea, Daniel Spielamn and Shang-Hua Teng won the Gödel Prize for their work on smoothed analysis of simplex algorithms. They introduced a way to formally study the worst case complexity of algorithms when the inputs are randomly perturbed by a small amount.

https://www.di.ens.fr/~vergnaud/algo0910/Simplex.pdf

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

#147

Post by asimpletune »

djoldman wrote: post #138
xkcd386 wrote: post #84

Earlier quoted context omitted.

The randomized algorithm that Reis & Rothvoss [1] present at the end of their paper will not be implemented in Gurobi/CPLEX/XPRESS. It remains a fantastic result regardless (see below). But first let me explain. In terms of theoretical computational complexity, the best algorithms for "integer linear programming" [2] (whether the variables are binary or general integers, as in the case tackled by the paper) are based…

Thanks for these resources and comments. Would say that the following is a good summary? -> This is an important theoretical result, but most real-world problems are far from worst case scenarios, therefore improving the worst case currently has little practical use.

No they're saying theoretical improvements does not directly lead to practical, because theory and practice have diverged due to how computers work. Instead, theoretical will most likely lead to indirect gains, as the techniques used will result in the next-generation of practical improvements.

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

#148

Post by aleph_minus_one »

benterix wrote: post #107
imtringued wrote: post #78

Earlier quoted context omitted.

>business of improving algorithms You do realize that the solver companies are in exactly the same boat, right?

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

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

#149

Post by isaacfung »

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…

A lot of polynomial time algorithms for combinatorial optimization problems can be interpreted as primal dual algorithms for the corresponding LPs, e.g. mst, matching(bipartite or general graph), network flow, matroid intersection, submodular flow. The extreme point solutions of some LPs also have interesting properties that you can exploit to design approximation algorithms for NP-complete problems. For example, you can prove that there is always a variable with value at least half in an extreme point solution of the steiner forest problem, so you can just iteratively round a variable and resolve the LP to get a 2-approximation. When I was in grad school that was the only 2-approximation algorithm for this problem. Another interesting thing is that you can solve LPs with exponentially many constraints as long as you have a polynomial time separation oracle.

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

#150

Post by antonioevans »

Has anyone considered the potential of integrating the recent ILP breakthrough into transformer models? Given ILP's prowess in optimization, I'm curious about its application in enhancing transformer efficiency, especially in inference speed. Could this ILP method streamline computational resource allocation in transformers, leading to a significant leap in AI model optimization? Keen to hear thoughts on practical challenges and theoretical implications of merging these two fields.
Post reply on HN