Jump to content
Search In
  • More options...
Find results that contain...
Find results in...
rcmaehl

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

Recommended Posts

Posted · Original PosterOP

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:
++**Toshiba's breakthrough algorithm realizes world's fastest, largest-scale combinatorial optimization

 

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.


NotCPUCores Dev | Desktop Build: Ryzen 7 1800X @ 4.0GHz, AsRock Fatal1ty X370 Professional Gaming, 32GB Corsair DDR4 @ 3000MHz, RX480 8GB OC, Benq XL2730 1440p 144Hz FS


 

Link to post
Share on other sites

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

 

But in all seriousness this is amazing.

 


System Specs:

CPU:  Intel 8700K (3.7-4.7GHz Turbo)  GPU: ASUS RTX 2080 Ti DUAL OC MB: MSI Z370 Gaming Plus   RAM: Corsair 3000MHz 2x8GB(16GB)  CPU Cooler: Kraken X42 AIO  Sound card: Creative Sound Blaster Z  SSD: OCZ ARC100 480GB  HDD: Western Digital 1TB Black, Seagate Barracuda 1TB both 7200RPM, WD Green 2TB (storage)  PSU: Pro750W XFX 80 Plus Gold  Case: NZXT H500 Optical Drive: -

 

 

Link to post
Share on other sites

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


I spent $2500 on building my PC and all i do with it is play MTGA & watch anime at 720p...

Builds:

The Toaster Project! Northern Bee! The Cassette Deck!

 

The original LAN PC build log! (Old, dead and replaced by The Toaster Project & 5.0)

Spoiler

"Here is some advice that might have gotten lost somewhere along the way in your life. 

 

#1. Treat others as you would like to be treated.

#2. It's best to keep your mouth shut; and appear to be stupid, rather than open it and remove all doubt.

#3. There is nothing "wrong" with being wrong. Learning from a mistake can be more valuable than not making one in the first place.

 

Follow these simple rules in life, and I promise you, things magically get easier. " - MageTank 31-10-2016

 

 

Link to post
Share on other sites
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.

Link to post
Share on other sites
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

Image result for kuzco's poison


"Put as much effort into your question as you'd expect someone to give in an answer"- @Princess Luna

Make sure to Quote posts or tag the person with @[username] so they know you responded to them!

Purple Build Post ---  Blue Build Post --- Blue Build Post 2018 --- Project ITNOS --- P600S VS Define R6/S2

CPU i7-4790k    Motherboard Gigabyte Z97N-WIFI   RAM G.Skill Sniper DDR3 1866mhz    GPU EVGA GTX1080Ti FTW3    Case Corsair 380T   

Storage 1x Samsung EVO 250GB, WD Black 3TB, WD Black 5TB    PSU Corsair CX550M      Cooling Cryorig H7

Link to post
Share on other sites
Posted · Original PosterOP
5 minutes ago, TVwazhere said:

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

Image result for kuzco's poison

 

To be fair 2 million is less than 5 billion.


NotCPUCores Dev | Desktop Build: Ryzen 7 1800X @ 4.0GHz, AsRock Fatal1ty X370 Professional Gaming, 32GB Corsair DDR4 @ 3000MHz, RX480 8GB OC, Benq XL2730 1440p 144Hz FS


 

Link to post
Share on other sites
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)


I don't work for Floatplane Media, so any Floatplane comments that I make are my own and may be incorrect or in conflict with the official view.

 

For Floatplane support, please use the wizard linked in this topic

Link to post
Share on other sites
Posted · Original PosterOP
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.


NotCPUCores Dev | Desktop Build: Ryzen 7 1800X @ 4.0GHz, AsRock Fatal1ty X370 Professional Gaming, 32GB Corsair DDR4 @ 3000MHz, RX480 8GB OC, Benq XL2730 1440p 144Hz FS


 

Link to post
Share on other sites
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? 

Link to post
Share on other sites
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.


I don't work for Floatplane Media, so any Floatplane comments that I make are my own and may be incorrect or in conflict with the official view.

 

For Floatplane support, please use the wizard linked in this topic

Link to post
Share on other sites
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 :D


"Put as much effort into your question as you'd expect someone to give in an answer"- @Princess Luna

Make sure to Quote posts or tag the person with @[username] so they know you responded to them!

Purple Build Post ---  Blue Build Post --- Blue Build Post 2018 --- Project ITNOS --- P600S VS Define R6/S2

CPU i7-4790k    Motherboard Gigabyte Z97N-WIFI   RAM G.Skill Sniper DDR3 1866mhz    GPU EVGA GTX1080Ti FTW3    Case Corsair 380T   

Storage 1x Samsung EVO 250GB, WD Black 3TB, WD Black 5TB    PSU Corsair CX550M      Cooling Cryorig H7

Link to post
Share on other sites
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 :D

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.


LINK-> Kurald Galain:  The Night Eternal 

Top 5820k, 980ti SLI Build in the World*

CPU: i7-5820k // GPU: SLI MSI 980ti Gaming 6G // Cooling: Full Custom WC //  Mobo: ASUS X99 Sabertooth // Ram: 32GB Crucial Ballistic Sport // Boot SSD: Samsung 850 EVO 500GB

Mass SSD: Crucial M500 960GB  // PSU: EVGA Supernova 850G2 // Case: Fractal Design Define S Windowed // OS: Windows 10 // Mouse: Razer Naga Chroma // Keyboard: Corsair k70 Cherry MX Reds

Headset: Senn RS185 // Monitor: ASUS PG348Q // Devices: Galaxy S9+ - XPS 13 (9343 UHD+) - Samsung Note Tab 7.0 - Lenovo Y580

 

LINK-> Ainulindale: Music of the Ainur 

Prosumer DYI FreeNAS

CPU: Xeon E3-1231v3  // Cooling: Noctua L9x65 //  Mobo: AsRock E3C224D2I // Ram: 16GB Kingston ECC DDR3-1333

HDDs: 4x HGST Deskstar NAS 3TB  // PSU: EVGA 650GQ // Case: Fractal Design Node 304 // OS: FreeNAS

 

 

 

Link to post
Share on other sites

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?


Computer's don't make errors. What they do, they do on purpose. By now your name and particulars have been fed into every laptop, desktop, mainframe and supermarket scanner that collectively make up the global information conspiracy, otherwise known as The Beast.

 

You just be careful. Computers have already beaten the Communists at chess. Next thing you know, they'll be beating humans.

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


×