This discovery may change the world in unpredictable and, perhaps very big, ways. Discoveries like this put all the self-important feature / model developers that we work with in our big tech day jobs into context.
Researchers have found a faster way to do integer linear programming
11–20 of 210 posts
Re: Researchers have found a faster way to do integer linear programming
#12About 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.e., seven factorial). This is a version of the famed “traveling salesman problem,” which has kept mathematicians busy for centuries, fruitlessly searching for a general solution. One strategy for solving the problem is with brute force— examine every possible route, compare them all, and pick the best one. This takes a ton of work and computational power— by the time you’re up to ten places to visit, there are more than 360,000 possible ways to do it, more than 80 billion with fifteen places to visit. Impossible. But take the roughly ten thousand ants in a typical colony, set them loose on the eight- feeding- site version, and they’ll come up with something close to the optimal solution out of the 5,040 possibilities in a fraction of the time it would take you to brute- force it, with no ant knowing anything more than the path that it took plus two rules (which we’ll get to). This works so well that computer scientists can solve problems like this with “virtual ants,” making use of what is now known as swarm intelligence."
Re: Researchers have found a faster way to do integer linear programming
#13I have a dumb question: how long will it take before this result becoming a pratical MIP solver beating SCIP or gurobi?
Re: Researchers have found a faster way to do integer linear programming
#14This discovery may change the world in unpredictable and, perhaps very big, ways. Discoveries like this put all the self-important feature / model developers that we work with in our big tech day jobs into context.
Can you explain specifically what about it you think will change the world and why?
Re: Researchers have found a faster way to do integer linear programming
#15For 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 Gurobi, CPLEX, or FICO solvers for large problems, and open source ones like SCIP for the small ones. There is a standard MPS format where you can run exchange models between all of these solvers, and the formulation of the problem shouldn't change, just the solving approach inside the solver.
Can someone enlighten me? I could see if they are arguing, this will require a new implementation, and if so, there is a ton of benefit the world would see from doing so.
Re: Researchers have found a faster way to do integer linear programming
#16I have a dumb question: how long will it take before this result becoming a pratical MIP solver beating SCIP or gurobi?
Couldn't either of those implement this algorithm?
Re: Researchers have found a faster way to do integer linear programming
#17Minor 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.
Re: Researchers have found a faster way to do integer linear programming
#18Linear programming is very cool, I loved Vasek Chvatal's book as a kid having accidently bought it thinking it was for computers.
But it's tricky to understand and implement and it struggles with real life constraints. i.e. This whole specialty just for integers.
Monto Carlo is trivial to understand and implement, adapts to changes and constraints trivially and should be just as good.
I'm sure for something high end like chip design you will do both. I'd be surprised to hear of real life stories where linear programming beats Monty Carlo.
Re: Researchers have found a faster way to do integer linear programming
#19For 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.
Re: Researchers have found a faster way to do integer linear programming
#20People really need to come up with better names. "Linear Programming" or "Integer Linear Programming" mean absolutely nothing. Also anything dealing with finding the minimum distance distances can be short circuited by keeping the shortest distance and not taking paths that exceed that. This is how approximate nearest neighbor works and can still speed up the full solution. Figuring out full paths that have short ave…
This made me wonder why it's called programming (since clearly it's not the sense of the word programming most HN'ers are used to). https://en.wikipedia.org/wiki/Mathematical_optimization#Hist...
From that link:
Programming in this context does not refer to computer programming, but comes from the use of program by the United States military to refer to proposed training and logistics schedules, which were the problems Dantzig studied at that time
Is that also true of 'dynamic programming'?