|
|||
| ARGONNE HOME PAGE | ARGONNE INTRANET | NEWS HOME PAGE | BACK ISSUES |
|
July 17, 2000 -- Some of this week's stories:
 30-year-old
computing challenge cracked
Argonne-West
employee picnic set for July 22
Deadline
nears for employee survey
Vegetation
recovering at Argonne-East
One-click
ad form now online
Lab
speakers are needed |
It took 1,000 computers in thirteen locations around the world a week to solve, but a 32-year-old mathematics problem has surrendered to an algorithm (a set of problem-solving instructions) developed by researchers at Argonne, the University of Iowa and Northwestern University.
The challenge problem, a quadratic assignment problem (QAP) known as NUG30, was believed only a year ago to be out of reach for the current generation of optimization algorithms and computing platforms. The method used to crack the problem holds promise in such real-world applications as deciding the layout of departments in a hospital or manufacturing facility, and the design of aircraft cockpit panels and computer chips.
The problem involves assigning 30 facilities to 30 fixed locations so as to minimize the total cost of transferring material between the facilities. NUG30 was first proposed in 1968 as a test of computer capabilities, but remained unsolved because of its great complexity, ranking as one of the most difficult combinatorial optimization problems.
"The complexity of a QAP with 30 locations is really hard to imagine," noted Kurt Anstreicher, a researcher at the University of Iowa. "You might think that with a fast computer you could just check all the possible assignments of facilities to locations, and choose the best one. But the number of assignments is so large that even if you could check a trillion per second, this process would take more than 100 times the age of the universe."
Anstreicher collaborated with colleagues Nate Brixius (Iowa), Jean-Pierre Goux (MCS and Northwestern University), and Jeff Linderoth (MCS) to solve NUG30.
Keys to solving the problem were the design of a state-of-the-art algorithm, by Anstreicher and Brixius, and its implementation on an extremely powerful computing platform.
The algorithm reduced the number of assignments to a manageable level by repeatedly eliminating possibilities that could not lead to an optimal assignment. To explore the remaining possibilities quickly and cheaply, the team made use of the untapped power of hundreds of underutilized workstations connected via the Internet. Computers were accessed via a high-throughput computing system known as Condor, developed by Miron Livny and co-workers at the University of Wisconsin.
To execute the algorithm, they used the Master-Worker distributed-processing interface to the Condor system developed by Goux, Linderoth, and their colleagues Sanjeev Kulkarni and Mike Yoder of the University of Wisconsin-Madison. The interface was developed as part of metaNEOS, a project that ties together researchers in optimization and distributed computing at the University of Wisconsin, Argonne, Northwestern University and other institutions.
"The Condor system and the Master-Worker interface are able to manage a large, diverse grid of computational resources, allowing us to use it as a single parallel computing platform," Linderoth said. Because Condor uses such resources as PCs and the idle time on user workstations, the cost of performing computations is low.
"The availability of this powerful, easily programmable, low-cost computing platform has tremendous implications for the solution of complex optimization problems and for computational science in general," Goux added.
At its peak, the program enlisted more than 1,000 computers simultaneously at Argonne, the University of Wisconsin, Georgia Institute of Technology, National Center for Supercomputing Applications, Italian Instituto Nazional di Fisica Nucleare, Albuquerque High Performance Computing Center, Northwestern University and Columbia University. Some of these machines were PCs from dedicated clusters and others were components of supercomputers, but many were workstations on the desks of individuals unconnected with the project.
If the problem could have been run on a single, fast computer workstation, it would have taken approximately seven years to complete. By using a large number of computers in parallel, NUG30 required a little less than a week of continuous computing.
"This was one of the largest and most complex computations ever performed to solve a discrete optimization problem," said Steve Wright (MCS). "It signals a new era in the use of computational grids for solving complex problems in numerical computing."
More information on the NUG30 solution can be found at http://www.mcs.anl.gov/metaneos/nug30.
Argonne-West's 49th annual summer picnic will be held Saturday, July 22, at Heise Hot Springs from 10 a.m. to 2 p.m.
Activities this year will include children's games, a fun jump, volleyball, swimming and golfing. Other attractions include live music, pie-throwing contest, water balloon toss and a variety of food and beverages.
All Argonne employees and their families are invited to the annual get-together. Admission is free.
The deadline for completing the Employee Opinion Survey is Friday, July 21. All employees are encouraged to participate.
The survey is provided via the World Wide Web. The password is "argonne."
The survey may be completed at work or at home, and takes about 20 minutes to complete.
Survey answers are sent directly to International Survey Research Association (ISR), and individual input is confidential.
Employees who do not have access to a computer may receive a paper copy from their division and department offices.
Surveys will also be available in each Argonne library, the Diversity Program Office at Argonne-East, or from Terry Brooks (RPS-HR) at Argonne-West.
Paper copies should be completed and returned to the Diversity Program, Building 201. There is also a survey return box in the Human Resources lobby.
ISR will manage and analyze survey data, and remove all individual identification from the responses before forwarding a summary to the laboratory.
Employees with questions or concerns, or who need further accommodations to complete the survey, should contact the Diversity Program Office at Argonne-East at ext. 2-3021 or Brooks at Argonne-West at ext. 3-7144.
Argonne-East's vegetation has been recovering since the fallow and white-tailed deer herds were thinned five years ago, but it could be another five years before the vegetation recovers completely, said Glen Dunn, U. S. Department of Agriculture wildlife biologist at Argonne.
Before the deer were culled or relocated, the browse line was five feet high in some places. The deer ate everything, from trees to ornamental plants. Today the browse line is not as evident, Dunn said.
"Vegetation is coming back slowly. It takes a while, more than a year or two," Dunn said.
Fewer deer mean not only less impact on vegetation, but also fewer car-deer collisions, less soil erosion by streams and healthier, well-nourished herds.
The large numbers of deer may also have been reducing biodiversity by eating spring-flowering native woodland species and young oak trees, said Robert Van Lonkhuyzen (EA). In the 10 years he has worked at Argonne, he has rarely seen an oak seedling.
"We suspected that the deer were eating them," he said. Yearly studies would be useful to prove or disprove this, he said.
Last year, the area east of the main gate was burned and cleared of buckthorn and honeysuckle, two exotic (non-native) plant species. Since then, other flowers deer like to eat have been growing in the clearing, said Donna Green (DOE). When the deer population was higher, Green said she did not see those flowers.
"It's hard to say why the flowers are coming back, whether it's because there are fewer deer or more light available to the plants after the brush was cleared," she said. "We didn't have a really good baseline of the vegetation before the deer were thinned."
With fewer deer, Argonne might be able to manage its plant life better, Green said. Argonne's Land Management and Habitat Restoration Committee works to restore habitat and improve biodiversity at the laboratory. A few years ago, Argonne also became a member of Chicago Wilderness, a coalition of more than 90 organizations that is working together to protect and restore natural communities in the Chicago region .
— Yolanda Lukaszewski
Only one fallow deer born since deer herds were reduced in 1995 has grown to adulthood. The population is not reproducing as it once did. That could be due to genetics, said Glen Dunn, U. S. Department of Agriculture wildlife biologist at Argonne.
The fallow deer herd originated from two does, one of which was pregnant. The herd grew from these three deer to 135 by 1995.
"There is not a lot of genetic variety and this could have caused inbreeding," Dunn said. Genetic diversity is not a concern for the white-tailed deer.
The herds are otherwise healthy because they now have plenty of space and food, Dunn said.
Fallow deer have historically been thinned every time they exceeded 200 onsite, Dunn said. The ideal number of deer for a given area is 10-20 deer per square mile, he said. For an area the size of Argonne that would be about 20 deer. An estimated 30-40 fallow deer and 70 white-tailed deer currently live at Argonne.
Although they have become an unofficial symbol of Argonne, fallow deer are wild animals and as such, are not owned or cared for by the laboratory.
— Yolanda Lukaszewski
A new "one-click" online classified ad form has been posted at the Argonne News World Wide Web site.
The form allows users to submit an ad request by clicking on a button, instead of printing the form and faxing it to the Argonne News office.
To find the form, go to the Argonne News World Wide Web site and click on "Classifieds."
The Argonne Speakers' Bureau needs staff employees to talk to the community about the research being done at the laboratory. The Speakers' Bureau helps take some of the mystery out of the laboratory and builds goodwill between the community and Argonne.
Talks are usually 20-30 minutes long, with 10 minutes afterward for questions. Speakers can give a general talk on research being done at Argonne using the slide show OPA provides, or they can talk about their own research.
The best speakers can explain their research in ways easy for laypersons to understand.
Anyone comfortable with public speaking can join the Speakers' Bureau. For more information, call Cindy Wilkinson (OPA) at ext. 2-5561.
