A-Waze-ing Directions - New algorithm from Toshiba 10x faster at finding the best solution

[rcmaehl]

Source:
Phys.org

Science Advances (White Paper)
 

Summary:
A break through in combinatorial optimization by Toshiba has greatly increased the speed and best selection in combinations of patterns. This could improve computation in which hundreds or thousands of options have to be considered at once, such as navigating streets, finance, and drug development.

Media:

 

Quotes/Excerpts:

Quote

Toshiba...has realized a major breakthrough in...the selection of the best solutions from among an enormous number of combinatorial patterns...with the development of an algorithm that delivers the world's fastest and largest-scale performance, and an approximately 10-fold improvement. Toshiba's new method can be applied to such daunting but essential tasks as identifying efficient delivery routes, determining the most effective molecular structures to investigate in new drug development, and building [Financial] portfolios. The Simulated Bifurcation Algorithm, quickly obtains highly accurate approximate solutions (good solutions) for combinatorial optimization problems.Potentially even more important, the algorithm also realizes excellent scalability at a low cost using current computers, which could revolutionize current optimization. Many problems can only be solved by sifting through a vast number of options to find the best combinations. These include realizing efficient logistics, directing traffic to ease congestion, applying molecular design to drug development, and optimizing financial portfolios. Today, such...optimization requires an enormous amount of computation...using current computers to find solutions remains difficult. Toshiba has solved these issues by developing a novel combinatorial optimization algorithm, the Simulated Bifurcation Algorithm. It is highly parallelizable, and can therefore easily speed up problem solving on standard digital computer. By using field-programmable gate arrays (FPGAs), a good solution to an optimization problem with 2,000 fully connected variables (approximately 2 million connections) can be obtained in just 0.5 milliseconds. This is approximately 10 times faster than the laser-based quantum computer recognized as the world's fastest can solve the same problem. Using a cluster of eight GPUs, Toshiba obtained a good solution for a large-scale problem involving 100,000 fully connected variables (about 5 billion connections) in only a few seconds.

 

My Thoughts:
I'm going to focus on something this will affect a large amount of people daily, Google Maps and Waze. This algorithm allows more highly scalable and multi-core processing of potential routes. While the majority of users will use the major roads such as highways and interstates, this will allow a lot better and faster alternative directions to avoid things such as congestion. It should not be understated however, how this could potentially influence finance portfolios and drug creation. It's nice to see major advances in traditional computing to continually rival quantum computing as we have it today.

[sof006]

Wow.... I didn't know Toshiba still did anything useful. Lol

 

But in all seriousness this is amazing.

 

[Bananasplit_00]

This seems pretty cool, hopefully it can be applied to lots of things

[Ja50n]

The X axis has no scale... without any numbers it looks like the old machine is faster.

[rawrdaysgoby]

I was expecting something different but never the less cool for those certain workloads 

[ScratchCat]

39 minutes ago, Ja50n said:

The X axis has no scale... without any numbers it looks like the old machine is faster.

The times are above the graphs.

The graphs are there to show that the new algorithm can produce approximations of similar quality and is not cutting more corners somewhere.

Quote

This is approximately 10 times faster than the laser-based quantum computer recognized as the world's fastest can solve the same problem.

Beating a quantum computer with a FPGA seems a far greater achievement. FPGAs can be put on a USB, a quantum computer less so.

[TVwazhere]

1 hour ago, rcmaehl said:

Toshiba...has realized a major breakthrough in...the selection of the best solutions from among an enormous number of combinatorial patterns...with the development of an algorithm that delivers the world's fastest and largest-scale performance, and an approximately 10-fold improvement. Toshiba's new method can be applied to such daunting but essential tasks as identifying efficient delivery routes, determining the most effective molecular structures to investigate in new drug development, and building [Financial] portfolios. The Simulated Bifurcation Algorithm, quickly obtains highly accurate approximate solutions (good solutions) for combinatorial optimization problems.Potentially even more important, the algorithm also realizes excellent scalability at a low cost using current computers, which could revolutionize current optimization. Many problems can only be solved by sifting through a vast number of options to find the best combinations. These include realizing efficient logistics, directing traffic to ease congestion, applying molecular design to drug development, and optimizing financial portfolios. Today, such...optimization requires an enormous amount of computation...using current computers to find solutions remains difficult. Toshiba has solved these issues by developing a novel combinatorial optimization algorithm, the Simulated Bifurcation Algorithm. It is highly parallelizable, and can therefore easily speed up problem solving on standard digital computer. By using field-programmable gate arrays (FPGAs), a good solution to an optimization problem with 2,000 fully connected variables (approximately 2 million connections) can be obtained in just 0.5 milliseconds. This is approximately 10 times faster than the laser-based quantum computer recognized as the world's fastest can solve the same problem. Using a cluster of eight GPUs, Toshiba obtained a good solution for a large-scale problem involving 100,000 fully connected variables (about 5 billion connections) in only a few seconds.

I'll take "How to fill a required character limit" for 500 Alex

[rcmaehl]

5 minutes ago, TVwazhere said:

I'll take "How to fill a required character limit" for 500 Alex

 

To be fair 2 million is less than 5 billion.

[colonel_mortis]

2 hours ago, rcmaehl said:

This could improve computation in which hundreds or thousands of options have to be considered at once, such as navigating streets, finance, and drug development.

This algorithm doesn't help with navigation. Instead, it's a new efficient (but approximate) algorithm for a problem called MAX-CUT, which can potentially be extended to other problems that are in the class of problems called NP-Complete. NP-Complete problems are hard (in a strict mathematical sense that I won't go into) to solve with computers, so a more efficient algorithm for approximating them is a good thing.

 

Finding a route between two points is not NP-Complete—in fact, we already have efficient algorithms for doing it (Dijkstra's algorithm and A*).

 

Problems that are NP-Complete, and which could potentially be solved more efficiently using this algorithm, include laying out components on a PCB and finding the optimal order in which to visit waypoints (when there are thousands of waypoints).

 

Unfortunately, the paper has far too much physics and not enough computer science for me to understand the algorithm itself (which is, as I understand it, based on simulating a physical process)

[rcmaehl]

18 minutes ago, colonel_mortis said:

This algorithm doesn't help with navigation.  Problems that are NP-Complete, and which could potentially be solved more efficiently using this algorithm, include finding the optimal order in which to visit waypoints (when there are thousands of waypoints).

Should I specify taxis/buses? I had assumed this would affect the normal consumer as each intersection and turn you could possibly make en-route to a location in itself is a waypoint. Granted not every waypoint had to be visited but I can see what you're saying.

[Techicolors]

22 minutes ago, colonel_mortis said:

This algorithm doesn't help with navigation. Instead, it's a new efficient (but approximate) algorithm for a problem called MAX-CUT, which can potentially be extended to other problems that are in the class of problems called NP-Complete. NP-Complete problems are hard (in a strict mathematical sense that I won't go into) to solve with computers, so a more efficient algorithm for approximating them is a good thing.

 

Finding a route between two points is not NP-Complete—in fact, we already have efficient algorithms for doing it (Dijkstra's algorithm and A*).

 

Problems that are NP-Complete, and which could potentially be solved more efficiently using this algorithm, include laying out components on a PCB and finding the optimal order in which to visit waypoints (when there are thousands of waypoints).

 

Unfortunately, the paper has far too much physics and not enough computer science for me to understand the algorithm itself (which is, as I understand it, based on simulating a physical process)

would this algorithm help in optimizing for the travelling salesman problem? 

[colonel_mortis]

21 minutes ago, rcmaehl said:

Should I specify taxis/buses? I had assumed this would affect the normal consumer as each intersection and turn you could possibly make en-route to a location in itself is a waypoint. Granted not every waypoint had to be visited but I can see what you're saying.

Even taxis and buses are unlikely to benefit from it in practice (taxis usually go from A to B like cars, and while you could argue that bus route planning is like the TSP problem of having a bunch of waypoints and trying to find the best route between them, in practice the bus stops will be chosen based on the route rather than the other way around).

It is applicable to a delivery driver who has to deliver parcels to a bunch of addresses though. The waypoints are fixed, but the order in which they are visited doesn't matter.

19 minutes ago, Techicolors said:

would this algorithm help in optimizing for the travelling salesman problem? 

It may do, and that is listed in the phys.org article as a possible application, but it may also be the case that once you translate TSP into MAX-CUT it becomes slower or less accurate than just using one of the many existing (and quite efficient and/or accurate, depending on your needs) TSP heuristics.

[TVwazhere]

4 hours ago, rcmaehl said:

To be fair 2 million is less than 5 billion.

The amount of time was also increased to compensate, so its basically the 125/25 vs 20/4. 

 

I'm all for this new algorithm, but maybe someone should have proof read this with more of an eight grade level of grading 

[Curufinwe_wins]

6 hours ago, TVwazhere said:

 

I'm all for this new algorithm, but maybe someone should have proof read this with more of an eight grade level of grading 

Oh, the sweet irony. 

 

Anyways... this is cool. It looks like it sacrifices finding more of the lower-bound optimal solutions for finding moderately good ones quicker, and the timescale was specifically chosen to illustrate when their metric (average determined value) intersects.

 

Quite useful, but I think the notably lower low end values of traditional methods will still end up being used for a large number of applications. Parcel delivery is a good counter example IMO if this algorithm seems to have lower variance in outputs and a general speedup.

[williamcll]

But can this help with everyday computer tasks?

[Trik'Stari]

Had a 500 mile drive on Monday.

 

Waze interrupted about half way through with a detour because there was a major accident on the interstate we were traveling on. It took us through some small town, before directing us to get back on, via an on ramp.

 

Problem was, that on ramp was where the accident occurred and was closed because there was a jeep on fire in the middle of it, and about 3 fire trucks and other EMS vehicles.

 

Good job waze?