COMPUTER SCIENTIST SOLVES OLD SALESMAN PROBLEM

January 19, 2001

SCIENCE AND ENGINEERING NEWS

It was a combination of things, physical and metaphysical that killed Arthur Miller’s traveling salesman Willie Loman.

Now a computer scientist at Washington University in St. Louis has developed and tested an algorithm that might at least have made Loman’s road traveled a little easier.

Weixiong Zhang, Ph. D., associate professor of computer science at Washington University, has developed an algorithm that attacks an old problem in the computing and business worlds known as the Traveling Salesman Problem (TSP). An algorithm is the backbone of computer operations; it is a step-wise mathematical formula, similar to a recipe, that solves a problem or reaches an otherwise desired end. The Traveling Salesman Problem is actually an umbrella term for a whole host of planning and scheduling problems, often involving routes; a classic one being a postman’s route, for instance.

Zhang currently is working with an AT&T Bell Labs collaborator David S. Johnson, Ph.D., a pioneer and widely acknowledged leading expert in the area of computational complexity. They have applied the algorithm bearing Zhang’s name to ten theoretical Traveling Salesman Problems and found it to be the best solution for half the problems, including one the AT&T Bell Labs is focusing on. The Zhang algorithm can be applied to a host of real-life problems.

One of the problems that AT&T Bell Labs is concerned with is one that involves the routes of payphone coin collectors. Zhang’s algorithm, in the case of payphone coin collectors, maps a route through these different phone booths enabling the service person to avoid backtracking, one-way streets, or visiting the same booth twice, getting him back to the office at a reasonable time. In the business world, this saves a company time and expense.

Zhang and his collaborator tested his algorithm on four different classes of coin collecting routes, with routes of 100, 316, 1,000, and 3,162 different payphones. Compared with six other algorithms tested, the Zhang algorithm found the shortest, most efficient, or cost-effective route in each case. The algorithm is scalable and robust; it can compute for up to half million “nodes,” in this case payphones, and it computed some routes in a matter of seconds.

Beyond the phone booth problem, the Zhang algorithm and the otherswere tested on a category called “No-wait flowshop problems.” Picture an automobile paint shop with multiple stations for painting different portions of a car. The algorithm maps the most efficient route from start-to-finish. Also computed were routes for tiny disk drive readers inside a computer and routes for moving heavy oil-drilling equipment on a large field. In the case of the disk drive reader, a short route must be chosen to minimize the distances that the reader must “travel” to speed up data access operations. In the case of the drilling equipment, a short route means a short “travel” distance for the equipment. The algorithm also can be applied to what is called very large scale integration (VLSI). For such aproblem, a route is needed that will connect all the minuscule components on a computer chip so that they can interface and function together.

Each of the TSPs tested are considered asymmetrical, which takes into account that the distance from place A to place B is not the same as that from B to A. Asymmetrical problems more closely reflect real-world situations. For instance, traveling on a freeway, you might be able to get on and reach adestination without paying a toll, but on the way back you might have to cross a bridge that has a toll. Thus, the cost in one direction is not the same as that going back. The Zhang algorithm factors in these real-life asymmetries. The results of the research were presented Jan. 5, 2001, at the Third Workshop on Algorithm Engineering and Experiments (Alenex 01), held at Washington, D.C. Some of the results also will be included as a chapter in a forthcoming book on the Traveling Salesman Problem. The work is partially funded by the National Science Foundation. “The Traveling Salesman Problem is one of the first computer science problems to be approached in the past century, and it is one of the first problems shown to be in the class called NP-Complete,” saidZhang.

Loosely speaking, NP-Complete is a class of problems that are believed unsolvable within a reasonable amount of time in the worst case. Thus, approximation algorithms are very important for solving real-world problems such as the payphone coin collector problem. Zhang’s algorithm is considered to be one of the two best approximation algorithms for the Asymmetric Traveling Salesman Problem. The other is what is called the Kanellakis-Papdimitrious local search algorithm, named after two noted computer scientists.

Algorithms such as Zhang’s are memory-efficient and meant to be embedded in hardware as a small but essential part of what’s called mechanical electronic manufactured systems (MEMs). Zhang currently is working on algorithms that are meant to run on smart devices, with very small memory and limited power.

“Memory is a very big issue today,” Zhang said. “With MEMs, you bundle the software so it’s very tightly integrated with the hardware and each smart device, with just a few thousand bits of memory and small amounts of data, all connect with each other to build and run a larger application. Running time-and space-efficient algorithms, you build a big system out of these small smart devices.” Zhang also is working on efficient search algorithms for analyzing biological data such as DNA, RNA and protein sequences. He is particularly interested in applying his skills in computer science and artificial intelligence to a relatively new but very active area called computational biology, or bioinformatics.

“If we say that information and computer technology were the leaders in the technology world in the last century, then biology will be the leader of this century,” said Zhang. “The combination of information technology and biology will not only provide us the knowledge of life science, but also help to cure diseases and make our lives wonderful to live.”

============================================================

Supercomputers Streamline Prediction of Dangerous Arrhythmia

June 2, 2020

Heart arrhythmia can prove deadly, contributing to the hundreds of thousands of deaths from cardiac arrest in the U.S. every year. Unfortunately, many of those arrhythmia are induced as side effects from various medicati Read more…

Indiana University to Deploy Jetstream 2 Cloud with AMD, Nvidia Technology

June 2, 2020

Indiana University has been awarded a \$10 million NSF grant to build ‘Jetstream 2,’ a cloud computing system that will provide 8 aggregate petaflops of computing capability in support of data analysis and AI workload Read more…

10nm, 7nm, 5nm…. Should the Chip Nanometer Metric Be Replaced?

June 1, 2020

The biggest cool factor in server chips is the nanometer. AMD beating Intel to a CPU built on a 7nm process node* – with 5nm and 3nm on the way – has been instrumental to AMD’s datacenter market resurgence. Nanomet Read more…

Supercomputer-Powered Protein Simulations Approach Lab Accuracy

June 1, 2020

Protein simulations have dominated the supercomputing conversation of late as supercomputers around the world race to simulate the viral proteins of COVID-19 as accurately as possible and simulate potential bindings in t Read more…

HPC Career Notes: June 2020 Edition

June 1, 2020

In this monthly feature, we'll keep you up-to-date on the latest career developments for individuals in the high-performance computing community. Whether it's a promotion, new company hire, or even an accolade, we've got Read more…

AWS Solution Channel

Computational Fluid Dynamics on AWS

Over the past 30 years Computational Fluid Dynamics (CFD) has grown to become a key part of many engineering design processes. From aircraft design to modelling the blood flow in our bodies, the ability to understand the behaviour of fluids has enabled countless innovations and improved the time to market for many products. Read more…

Supercomputer Modeling Shows How COVID-19 Spreads Through Populations

May 30, 2020

As many states begin to loosen the lockdowns and stay-at-home orders that have forced most Americans inside for the past two months, researchers are poring over the data, looking for signs of the dreaded second peak of t Read more…

Indiana University to Deploy Jetstream 2 Cloud with AMD, Nvidia Technology

June 2, 2020

Indiana University has been awarded a \$10 million NSF grant to build ‘Jetstream 2,’ a cloud computing system that will provide 8 aggregate petaflops of comp Read more…

10nm, 7nm, 5nm…. Should the Chip Nanometer Metric Be Replaced?

June 1, 2020

The biggest cool factor in server chips is the nanometer. AMD beating Intel to a CPU built on a 7nm process node* – with 5nm and 3nm on the way – has been i Read more…

COVID-19 HPC Consortium Expands to Europe, Reports on Research Projects

May 28, 2020

The COVID-19 HPC Consortium, a public-private effort delivering free access to HPC processing for scientists pursuing coronavirus research – some utilizing AI Read more…

\$100B Plan Submitted for Massive Remake and Expansion of NSF

May 27, 2020

Legislation to reshape, expand - and rename - the National Science Foundation has been submitted in both the U.S. House and Senate. The proposal, which seems to Read more…

IBM Boosts Deep Learning Accuracy on Memristive Chips

May 27, 2020

IBM researchers have taken another step towards making in-memory computing based on phase change (PCM) memory devices a reality. Papers in Nature and Frontiers Read more…

Hats Over Hearts: Remembering Rich Brueckner

May 26, 2020

HPCwire and all of the Tabor Communications family are saddened by last week’s passing of Rich Brueckner. He was the ever-optimistic man in the Red Hat presiding over the InsideHPC media portfolio for the past decade and a constant presence at HPC’s most important events. Read more…

Nvidia Q1 Earnings Top Expectations, Datacenter Revenue Breaks \$1B

May 22, 2020

Nvidia’s seemingly endless roll continued in the first quarter with the company announcing blockbuster earnings that exceeded Wall Street expectations. Nvidia Read more…

Microsoft’s Massive AI Supercomputer on Azure: 285k CPU Cores, 10k GPUs

May 20, 2020

Microsoft has unveiled a supercomputing monster – among the world’s five most powerful, according to the company – aimed at what is known in scientific an Read more…

Supercomputer Modeling Tests How COVID-19 Spreads in Grocery Stores

April 8, 2020

In the COVID-19 era, many people are treating simple activities like getting gas or groceries with caution as they try to heed social distancing mandates and protect their own health. Still, significant uncertainty surrounds the relative risk of different activities, and conflicting information is prevalent. A team of Finnish researchers set out to address some of these uncertainties by... Read more…

[email protected] Turns Its Massive Crowdsourced Computer Network Against COVID-19

March 16, 2020

For gamers, fighting against a global crisis is usually pure fantasy – but now, it’s looking more like a reality. As supercomputers around the world spin up Read more…

[email protected] Rallies a Legion of Computers Against the Coronavirus

March 24, 2020

Last week, we highlighted [email protected], a massive, crowdsourced computer network that has turned its resources against the coronavirus pandemic sweeping the globe – but [email protected] isn’t the only game in town. The internet is buzzing with crowdsourced computing... Read more…

Global Supercomputing Is Mobilizing Against COVID-19

March 12, 2020

Tech has been taking some heavy losses from the coronavirus pandemic. Global supply chains have been disrupted, virtually every major tech conference taking place over the next few months has been canceled... Read more…

Supercomputer Simulations Reveal the Fate of the Neanderthals

May 25, 2020

For hundreds of thousands of years, neanderthals roamed the planet, eventually (almost 50,000 years ago) giving way to homo sapiens, which quickly became the do Read more…

DoE Expands on Role of COVID-19 Supercomputing Consortium

March 25, 2020

After announcing the launch of the COVID-19 High Performance Computing Consortium on Sunday, the Department of Energy yesterday provided more details on its sco Read more…

Steve Scott Lays Out HPE-Cray Blended Product Roadmap

March 11, 2020

Last week, the day before the El Capitan processor disclosures were made at HPE's new headquarters in San Jose, Steve Scott (CTO for HPC & AI at HPE, and former Cray CTO) was on-hand at the Rice Oil & Gas HPC conference in Houston. He was there to discuss the HPE-Cray transition and blended roadmap, as well as his favorite topic, Cray's eighth-gen networking technology, Slingshot. Read more…

Honeywell’s Big Bet on Trapped Ion Quantum Computing

April 7, 2020

Honeywell doesn’t spring to mind when thinking of quantum computing pioneers, but a decade ago the high-tech conglomerate better known for its control systems waded deliberately into the then calmer quantum computing (QC) waters. Fast forward to March when Honeywell announced plans to introduce an ion trap-based quantum computer whose ‘performance’ would... Read more…

Tech Conferences Are Being Canceled Due to Coronavirus

March 3, 2020

Several conferences scheduled to take place in the coming weeks, including Nvidia’s GPU Technology Conference (GTC) and the Strata Data + AI conference, have Read more…

Exascale Watch: El Capitan Will Use AMD CPUs & GPUs to Reach 2 Exaflops

March 4, 2020

HPE and its collaborators reported today that El Capitan, the forthcoming exascale supercomputer to be sited at Lawrence Livermore National Laboratory and serve Read more…

‘Billion Molecules Against COVID-19’ Challenge to Launch with Massive Supercomputing Support

April 22, 2020

Around the world, supercomputing centers have spun up and opened their doors for COVID-19 research in what may be the most unified supercomputing effort in hist Read more…

Cray to Provide NOAA with Two AMD-Powered Supercomputers

February 24, 2020

The United States’ National Oceanic and Atmospheric Administration (NOAA) last week announced plans for a major refresh of its operational weather forecasting supercomputers, part of a 10-year, \$505.2 million program, which will secure two HPE-Cray systems for NOAA’s National Weather Service to be fielded later this year and put into production in early 2022. Read more…

15 Slides on Programming Aurora and Exascale Systems

May 7, 2020

Sometime in 2021, Aurora, the first planned U.S. exascale system, is scheduled to be fired up at Argonne National Laboratory. Cray (now HPE) and Intel are the k Read more…

Summit Supercomputer is Already Making its Mark on Science

September 20, 2018

Summit, now the fastest supercomputer in the world, is quickly making its mark in science – five of the six finalists just announced for the prestigious 2018 Read more…

Fujitsu A64FX Supercomputer to Be Deployed at Nagoya University This Summer

February 3, 2020

Japanese tech giant Fujitsu announced today that it will supply Nagoya University Information Technology Center with the first commercial supercomputer powered Read more…