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

101–110 of 210 posts

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

#101

Post by PartiallyTyped »

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…

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

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

#102

Post by WhitneyLand »

eigenket wrote: post #99
WhitneyLand wrote: post #98

Earlier quoted context omitted.

[flagged]

Run time, runtime and run-time are all commonly used for the thing you want to call run time. None are incorrect. https://www.collinsdictionary.com/dictionary/english/runtime

Informally they are used interchangeably. However, their definitions are different.

The subject here, is academic research involving algorithmic complexity. What papers do you know of that refer to algorithmic complexity and “runtime”?

Context matters. It is incorrect in this context.

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

#103

Post by whyever »

WhitneyLand wrote: post #98
mzl wrote: post #95

Lowering the algorithmic upper bound for a core NP-complete problem is always extremely interesting. However, this is not necessarily related to improving runtime for practical implementations solving the problem in question. Solvers for mixed integer programming (MIP) use a lot of algorithms in conjunction with loads of heuristics. Building up the library of heuristics and strategies is a crucial part of why the imp…

[flagged]

Isn't this a stylistic choice? For example, some style guides would suggest to use "run time", but also "run-time error".

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

#104

Post by Tarean »

andrewp123 wrote: post #66

It seems their result has been out for almost a year now... https://arxiv.org/abs/2303.14605 I'm curious how this affects Traveling Salesman. I was under the impression that all NP-Complete problems take O(n!). Does this method improve it at all?

Often, the concrete problems we are interested in have some internal structure that make them easier to solve in practice. Solving Boolean formulas is NP-complete but we routinely solve problems with millions of variables.

ILP (and sat) solvers are interesting because they are great at ruling out large areas that cannot contain solutions. It's also easy to translate many problems into ILP or SAT problems.

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

#105

Post by eigenket »

WhitneyLand wrote: post #102
eigenket wrote: post #99

Earlier quoted context omitted.

Run time, runtime and run-time are all commonly used for the thing you want to call run time. None are incorrect. https://www.collinsdictionary.com/dictionary/english/runtime

Informally they are used interchangeably. However, their definitions are different. The subject here, is academic research involving algorithmic complexity. What papers do you know of that refer to algorithmic complexity and “runtime”? Context matters. It is incorrect in this context.

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.

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

#106

Post by Bimos »

xkcd386 wrote: post #84
nkh wrote: post #15

For now, the new algorithm hasn’t actually been used to solve any logistical problems, since it would take too much work updating today’s programs to make use of it. But for Rothvoss, that’s beside the point. “It’s about the theoretical understanding of a problem that has fundamental applications,” he said. I don't see how "it would take to much work updating today's programs". Most domain specific models call out to…

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 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 type algorithm will overcome the difficulties you mentioned and eventually replace B&B, totally or partly (like barrier vs simplex methods)?

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

#107

Post by benterix »

imtringued wrote: post #78
black_puppydog wrote: post #47

Earlier quoted context omitted.

It's quite easy to go tell other people what they should do with their time. These researchers are in the business of improving algorithms. Implementing them in large industrial (or open source) code bases in a maintainable way -- and then actually maintaining that code -- is a different skillset, a different set of interestes, and as was pointed out, besides the point. Either you believe their results, then be grate…

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

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

#108

Post by WhitneyLand »

eigenket wrote: post #105
WhitneyLand wrote: post #102

Earlier quoted context omitted.

Informally they are used interchangeably. However, their definitions are different. The subject here, is academic research involving algorithmic complexity. What papers do you know of that refer to algorithmic complexity and “runtime”? Context matters. It is incorrect in this context.

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.

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

#109

Post by GaryNumanVevo »

WhitneyLand wrote: post #102
eigenket wrote: post #99

Earlier quoted context omitted.

Run time, runtime and run-time are all commonly used for the thing you want to call run time. None are incorrect. https://www.collinsdictionary.com/dictionary/english/runtime

Informally they are used interchangeably. However, their definitions are different. The subject here, is academic research involving algorithmic complexity. What papers do you know of that refer to algorithmic complexity and “runtime”? Context matters. It is incorrect in this context.

Keeping the HN tradition of "pedantry at all costs" alive, I applaud you

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

#110

Post by mzl »

WhitneyLand wrote: post #98
mzl wrote: post #95

Lowering the algorithmic upper bound for a core NP-complete problem is always extremely interesting. However, this is not necessarily related to improving runtime for practical implementations solving the problem in question. Solvers for mixed integer programming (MIP) use a lot of algorithms in conjunction with loads of heuristics. Building up the library of heuristics and strategies is a crucial part of why the imp…

[flagged]

The original paper (https://arxiv.org/pdf/2303.14605.pdf) that the linked article reports on is a theoretical algorithms paper, and does not contain any references to actual solvers or implementations.

For practical cases it is not that important what the worst-case complexity is, but rather what the expected complexity is of solving problems that occur in practice.

Post reply on HN