Solving the large-scale problem of large-scale problem solving
The challenge facing schedulers at UPS and other major delivery companies is not too difficult for the average person to appreciate.
You must determine the most efficient routes for hundreds of trucks that are transporting products to a variety of locations and are operated by drivers who may work only a limited number of hours per day.
Fashioning an optimal solution to a complicated task in the face of multiple constraints makes the UPS scenario a classical optimization problem, says Ted Ralphs, assistant professor of industrial and systems engineering.
But the routing riddles that confront delivery companies represent only a small fraction of the potentially limitless problems tackled by optimization experts, he says.
Ralphs writes software to solve large-scale optimization problems, which can have thousands of variables or more and which sometimes must be solved by clusters of computers working in parallel. He has three active grants from the National Science Foundation, the most recent of which requires him to come up with algorithms, or sets of instructions, to solve large-scale problems in real time. An example of this type of problem is the need for software that can tell surgeons as they treat tumors, especially brain tumors, the optimal quantity of radiation, and the optimal location to deliver it, in order to destroy cancerous tissue without harming healthy tissue.
I can basically find optimization problems anywhere I look, says Ralphs. The scheduling of classes at Lehigh, for example, has to take into account conflicting factors - professors who teach at certain times, students who have to have certain courses, and the availability of rooms. It's an increasingly hard problem that the registrar's office is now using software to solve.
The Internet is another example of optimization. You have to make sure data gets where it needs to go subject to numerous constraints, such as computer capacity and location of wireless base stations. That's what I find exciting about optimization - the problems are everywhere and they affect everyone.
Ralphs and his students have recently been asked to develop software that can fashion flexible solutions to optimization problems whose variables and constraints are not only many but shifting.
An example of this kind of problem is the challenge of determining the most efficient schedules for an airline's crews. The task of staffing hundreds of daily flights with crews who spend much of their time away from home and can spend only a limited amount of time in the air is tricky enough. It can be complicated immensely when storms or unexpected mechanical problems cause flight delays or cancellations, or when employees are too sick to work.
Sometimes you can spend lots of time solving a difficult optimization problem, says Ralphs, only to find out either that your input data was not correct or that some of your variables have changed. The challenge then is to use the same information, the same solution method, to quickly resolve wrinkles that come up. Instead of going back to the beginning, in other words, you try to make a minor adjustment to a solution that you spent hours coming up with.
To do this, you need to keep a record of all the steps you made in fashioning the solution and determine which can remain the same and which need to be reconsidered in a new solution.
One challenge for optimization experts that Ralphs has embraced is to develop software programs that are user-friendly for the growing number and variety of people seeking help with optimization problems.
Ralphs sits on the board of directors of the Computational Infrastructure for Operations Research, or COIN-OR Foundation, which is a non-profit organization that produces open-source software for optimization problems.
It takes a lot of work to produce software, says Ralphs. But there's no reward system for academics who make software easy to use. So a lot of software produced by academics ends up sitting on their computers without ever being used.
The goal of COIN-OR is to make optimization software available to people in the real world. We try to maintain infrastructure that people can build on and use.
The endeavors to which his software can be applied can be surprising, Ralphs found out recently when he received an e-mail from a scientist working in bioinformatics.
The scientist, seeking to develop a medicine, needed to know the 3-D structure of a protein encoded by the DNA sequence of a certain bacteria. In order to see the protein in 3-D, the scientist needed to be able to predict the energy state of the protein in all of its possible chemical bond configurations.
The potential number of chemical bonds made the problem an optimization challenge. Ralphs referred the scientist to web sites containing his software, which helped the scientist solve his problem.
It is very rewarding for me to get e-mail from someone who's using my software, says Ralphs. I try to make things as easy to use as I can.
Ralphs, who developed a software called SYMPHONY to solve large-scale optimization problems, directs the Computational Optimization Research at Lehigh (COR@L) Laboratory, along with Rosemary Berger and Jeff Linderoth, two other assistant professors of industrial and systems engineering. He supervises seven Ph.D. candidates and chairs the university's High-Performance Computing Steering Committee.
You must determine the most efficient routes for hundreds of trucks that are transporting products to a variety of locations and are operated by drivers who may work only a limited number of hours per day.
Fashioning an optimal solution to a complicated task in the face of multiple constraints makes the UPS scenario a classical optimization problem, says Ted Ralphs, assistant professor of industrial and systems engineering.
But the routing riddles that confront delivery companies represent only a small fraction of the potentially limitless problems tackled by optimization experts, he says.
Ralphs writes software to solve large-scale optimization problems, which can have thousands of variables or more and which sometimes must be solved by clusters of computers working in parallel. He has three active grants from the National Science Foundation, the most recent of which requires him to come up with algorithms, or sets of instructions, to solve large-scale problems in real time. An example of this type of problem is the need for software that can tell surgeons as they treat tumors, especially brain tumors, the optimal quantity of radiation, and the optimal location to deliver it, in order to destroy cancerous tissue without harming healthy tissue.
I can basically find optimization problems anywhere I look, says Ralphs. The scheduling of classes at Lehigh, for example, has to take into account conflicting factors - professors who teach at certain times, students who have to have certain courses, and the availability of rooms. It's an increasingly hard problem that the registrar's office is now using software to solve.
The Internet is another example of optimization. You have to make sure data gets where it needs to go subject to numerous constraints, such as computer capacity and location of wireless base stations. That's what I find exciting about optimization - the problems are everywhere and they affect everyone.
Ralphs and his students have recently been asked to develop software that can fashion flexible solutions to optimization problems whose variables and constraints are not only many but shifting.
An example of this kind of problem is the challenge of determining the most efficient schedules for an airline's crews. The task of staffing hundreds of daily flights with crews who spend much of their time away from home and can spend only a limited amount of time in the air is tricky enough. It can be complicated immensely when storms or unexpected mechanical problems cause flight delays or cancellations, or when employees are too sick to work.
Sometimes you can spend lots of time solving a difficult optimization problem, says Ralphs, only to find out either that your input data was not correct or that some of your variables have changed. The challenge then is to use the same information, the same solution method, to quickly resolve wrinkles that come up. Instead of going back to the beginning, in other words, you try to make a minor adjustment to a solution that you spent hours coming up with.
To do this, you need to keep a record of all the steps you made in fashioning the solution and determine which can remain the same and which need to be reconsidered in a new solution.
One challenge for optimization experts that Ralphs has embraced is to develop software programs that are user-friendly for the growing number and variety of people seeking help with optimization problems.
Ralphs sits on the board of directors of the Computational Infrastructure for Operations Research, or COIN-OR Foundation, which is a non-profit organization that produces open-source software for optimization problems.
It takes a lot of work to produce software, says Ralphs. But there's no reward system for academics who make software easy to use. So a lot of software produced by academics ends up sitting on their computers without ever being used.
The goal of COIN-OR is to make optimization software available to people in the real world. We try to maintain infrastructure that people can build on and use.
The endeavors to which his software can be applied can be surprising, Ralphs found out recently when he received an e-mail from a scientist working in bioinformatics.
The scientist, seeking to develop a medicine, needed to know the 3-D structure of a protein encoded by the DNA sequence of a certain bacteria. In order to see the protein in 3-D, the scientist needed to be able to predict the energy state of the protein in all of its possible chemical bond configurations.
The potential number of chemical bonds made the problem an optimization challenge. Ralphs referred the scientist to web sites containing his software, which helped the scientist solve his problem.
It is very rewarding for me to get e-mail from someone who's using my software, says Ralphs. I try to make things as easy to use as I can.
Ralphs, who developed a software called SYMPHONY to solve large-scale optimization problems, directs the Computational Optimization Research at Lehigh (COR@L) Laboratory, along with Rosemary Berger and Jeff Linderoth, two other assistant professors of industrial and systems engineering. He supervises seven Ph.D. candidates and chairs the university's High-Performance Computing Steering Committee.
Posted on:
Wednesday, August 31, 2005
Share This Story:
