TL;DR fun math no impl
Researchers have found a faster way to do integer linear programming
151–160 of 210 posts
Re: Researchers have found a faster way to do integer linear programming
#152Re: Researchers have found a faster way to do integer linear programming
#153Earlier quoted context omitted.
Fine, I edited "most" in my previous comment to "many". There are still plenty of examples (even on the first page) where the "runtime" is used to mean algorithmic complexity https://arxiv.org/abs/2401.14645 https://arxiv.org/abs/2401.13770 https://arxiv.org/abs/2401.12253 https://arxiv.org/abs/2401.12205 https://arxiv.org/abs/2401.10856
I’ll respond to what I think are the real points: Precision doesn’t matter in this case? I disagree. It was a dick move and pretentious to call it out? Maybe so, it was not my intent and I apologize if it was the case.
Since you think it was a dick move, then maybe consider that.
Language matters when you want to get across. (and so does context).
Re: Researchers have found a faster way to do integer linear programming
#154For 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…
I think what this work does is establish a new, and lower, upper bound on the number of points that need to be explored in order to find an exact solution.
From some of your other replies it looks to me like you're confusing that with an improved bound on the value of the solution itself.
It's a little unclear to me whether this is even a new solution algorithm, or just a better bound on the run time of an existing algorithm.
I will say I agree with you that I don't buy the reason given for the lack of practical impact. If there was a breakthrough in practical solver performance people would migrate to a new solver over time. There's either no practical impact of this work, or the follow on work to turn the mathematical insights here into a working solver just haven't been done yet.
Re: Researchers have found a faster way to do integer linear programming
#155Lowering 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…
[deleted]
Re: Researchers have found a faster way to do integer linear programming
#156About the travelling salesperson problem, below is a quote from the latest Sapolsky's book Determined: A Science of Life without Free Will. I am not sure how relevant this is for software developers, but still fascinating: "An ant forages for food, checking eight different places. Little ant legs get tired, and ideally the ant visits each site only once, and in the shortest possible path of the 5,040 possible ones (i…
If ants can smell where other ants have been, they are kind'a doing Dijkstra's algorithm. Is this the "swarm intelligence" the book is getting to?
Re: Researchers have found a faster way to do integer linear programming
#157Earlier quoted context omitted.
So, many researchers don't use terms with due care. And many article are rejected by Nature.
> So, many researchers don't use terms with due care. And many article are rejected by Nature. The reason is much simpler: many (most) researchers are not native English speakers. For example, my doctoral advisor (who knows English well, but is not a native speaker) could hardly help me with questions concerning more subtle aspects of English terms used in the research area. He told me that hardly anybody cares. Even…
[deleted]
Re: Researchers have found a faster way to do integer linear programming
#158For 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 new algorithm of R&R would need to replace the algorithms at the core of Gurobi, CPlex, etc. These tools are marvels of engineering, extremely complex, results of decades of incremental improvements. If would likely take significant research effort to even figure out a way to incorporate the new discoveries into these engines.
> results of decades of incremental improvements.
Gurobi was only founded in 2008. I don't doubt the optimizer was the result of "decades of incremental improvements", but the actual implementation must have been started relatively recently.
Re: Researchers have found a faster way to do integer linear programming
#159Earlier 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.
> most real-world problems are far from worst case scenarios, therefore improving the worst case currently has little practical use.
This statement is probably mostly correct, but I think that in one way it could be misleading: I would not want to imply that real-world problem instances are somehow easier than the worst-case, in terms of computational complexity. They still very much exhibit exponential increase in computational cost as you scale them up.
Instead, most read-world instances have structure. Some of that structure is well understood (for example, 99% of optimization problems involve extremely sparse matrices), some is not. But sometimes, we can exploit structure even without understanding it fully (some algorithmic techniques work wonder on some instances, and we don't fully know why).
It could be argued that by exploiting structure, it is the constant factor in the big-O computational complexity that gets dramatically decreased. If that is the case, the theory and practice do not really contradict each other. It is just that in practice, we are willing to accept a larger exponent in exchange for a smaller constant factor. Asymptotically it is a losing bargain. But for a given instance, it could be extremely beneficial.
Re: Researchers have found a faster way to do integer linear programming
#160Earlier 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 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 algorithms.
> 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)?
Very unlikely in the next 5 years. Beyond that, they could be the next small revolution, maybe. "Cutting planes" were another tool that had some good theory but were thought to be impractical. Then 25 years ago, people found a way to make them work, and they were a huge boost to solvers. We may be due for another big jump.
Lattice-based method are already effective in some niches. Branch-and-bound solvers are horrible at cryptography and number theory problems (those problems are bad fits for floating-point arithmetic in general), and lattice-based methods shine there. There are also some rare dense optimization problems that benefit from lattice-based methods (typically, one would use lattices in a pre-processing step, then pass the reformulated problem to a regular branch-and-bound solver [1]).
[1] https://link.springer.com/chapter/10.1007/3-540-48777-8_1