Profiles in OR/MS: Jeff Linderoth
|
Postdoctoral Research Assistant Argonne National Laboratory, Mathematics and Computer Science Division B.S. General Engineering University of Illinois at Urbana-Champaign 1992 M.S. Operations Research Industrial and Systems Engineering, Georgia Tech, 1994 |
PhD Industrial Engineering,
Contact Information: |
Questions & Answers
Q. Tell me about your educational and professional background and how you arrived at your current position as a Postdoctoral Research Assistant in the Mathematics and Computer Science (MCS) Division at Argonne National Laboratory?
A. I studied General Engineering at the University of Illinois. After my sophomore year, I began doing optimization research with a professor in the department, and at this point, I decided that optimization was the field for me. I have always had an interest in computing, so I decided to do my graduate studies in computational optimization. Georgia Tech is a very strong school in this area, and I was able work with many wonderful professors during my stay there. After Georgia Tech, I received an offer to come to Argonne, which was a perfect fit for my interests. Argonne is at the forefront of large-scale optimization research, and the research lab environment offers a nice balance between the academic and industrial OR/MS worlds.
Q. I recently visited the MSC Division page of the Argonne National Laboratory website where it states that "[The MCS Division's] mission is to increase scientific productivity in the 21st century by providing intellectual and technical leadership in the computing." Can you elaborate on the overall mission of Argonne National Labs and the role of the MCS division within this research center?
A. Argonne actually has a fourfold mission: conducting basic research, operating national science facilities, enhancing the nation's energy resources, and developing better ways to manage environmental problems. The MCS Division falls principally under the first area: developing the sophisticated tools and technologies needed by DOE's scientific applications. But MCS researchers do more than merely meet the needs of DOE scientists. We seek to provide a solid theoretical foundation for scientific experimentation. We also try to anticipate needs and to create new technology that will advance the state of the art of large-scale computing and make researchers more productive. All this makes MCS—and Argonne—an exciting place to work.
Q. What are some of the projects that you have worked on while employed at Argonne?
A. I have been primarily working on the metaNEOS project. The concept behind the metaNEOS project is that traditional computing paradigms are changing and that optimization algorithms must be ready to adapt to these changes. In particular, we are exploring ways to solve large optimization problems on "metacomputing" platforms.
Q. What is a metacomputing platform?
A. This is a broad term that refers to a collection of computers and storage and visualization devices connected by a network. In metaNEOS, our focus is on metacomputers built from a large number of workstations. The owners of these workstations typically do not even know one another! Since these resources are non-dedicated, we must vacate our processes from the workstation as soon as its owner returns.
Q. Is it hard to find owners willing to lend out their computers?
A. From a sociological standpoint, users are quite willing to contribute their machines if they are allowed to specify the conditions under which outside jobs are allowed to run. Thus, metacomputers can be built up of a large number of processors – using CPU cycles that would have otherwise been wasted. Using this inexpensive computing platform we have solved optimization problem instances of record-breaking complexity.
Q. Wow! What are some examples?
A. We are currently able to solve a 50,000 scenario stochastic linear programming problem arising from telecommunication network design. If you were to write down the full linear program from this problem it would have 4 million rows and 20 million columns!
Our flagship application for metacomputing has been the solution of large quadratic assignment problems. Previously, the most successful branch and bound algorithm was able to solve a problem of size n=" 25" in 66 days on a single machine. Kurt Anstreicher and Nate Brixius from the University of Iowa have recently developed an alternative, computationally efficient, branch and bound approach. Working with the metaNEOS team, a parallel version of their branch and bound algorithm was implemented for our metacomputing platform. Now, the same size n=" 25" instance is solved in about two hours! We also are able to solve larger problems than ever before – up to size n=" 28." Such a problem would have taken around 400 days to solve on one workstation—even for the sophisticated branch and bound algorithm that Kurt and Nate developed—but we solved it in a little more than 3 days. (For more information, visit Cover Stories: Condor)
Q. What types of optimization problems can best be adapted to this type of computing environment?
A. The metacomputing environment is not suited for solving all types of optimization problems. In order to keep the processors of a metacomputer working efficiently, it is best if the computation is large grained—meaning that it can be broken into portions of work of large size. It also is useful if there is very little sychronization required between the grains of work. We have found that many optimization algorithms have—or can be modified to have—these desirable characteristics.
Q. What other projects have you worked while at Argonne?
A. Another project has been to help the Department of Energy define an optimal schedule in which, because of security concerns, the optimization problem must be solved in a decomposed and distributed manner. We have applied a classical variable splitting and decomposition algorithm, but due to the practical instance we are trying to solve we have had to apply many problem specific heuristics.
One major challenge of this project arises from the fact that I have no security clearance and the end user is very concerned about divulging the true nature of the problem to non-secure personnel such as myself. The lack of knowledge about the true nature of the problem has made developing a useful model abstraction and solution algorithm quite challenging. Working on this project has helped me learn (the hard way) just how important it is for OR/MS practitioners to have "first-hand" knowledge of the project.
Q. Would a metacomputing environment conflict with the security concerns of such a project?
A. In this particular case, the users are not concerned about the machines that compute the solutions, but rather they are concerned about divulging the constraints making up their problem.
Q. Can you elaborate on the security issues that must be in place for both the owners of the machines within the metacomputing platform and for the end user whose solution is being computed within this environment?
A. Security is a very important issue. We have chosen to build our optimization algorithms on top of existing metacomputing toolkits. As such, the security features offered to the owners of machines and the end users are precisely those implemented in these metacomputing tookits.
For example, our algorithms will run with the Condor resource management and scheduling software. Condor implements low level operating system constructs guaranteeing that all programs running on a remote machine cannot harm the system. However, our current algorithms offer little in the way of security to the end user.
Other metacomputing toolkits (for example Globus) – developed in part at Argonne National Laboratory) have facilities for encrypting messages. As metacomputing becomes more a part of the mainstream computing culture, better end user security features will undoubtedly be important.
Q. What are the most valuable technical skills that you believe are needed to be successful in the OR/MS industry?
A. My academic side wishes that I had studied more mathematics while in school. More pragmatically, practical computational skills and familiarity with OR/MS software are important for both academic and industrial practitioners. As an OR/MS practitioner, even if you don't do implementations yourself, you must understand the issues involved in taking ideas from the drawing board to prime time.
Q. What are some of the most valuable non-technical skills that you believe are needed to be successful in the OR/MS industry?
A. You can never be too polished at public speaking. Verbal communication skills are essential regardless of your particular OR/MS arena.
Q. In what ways do you continue to expand your knowledge of new technologies and techniques in OR/MS?
A. Going to conferences is one of the best ways to keep abreast of the OR/MS field. It is important to attend conferences and speak directly with people about their current work. By the time you read about advances in technical journals, they are often "well-known" techniques.
Q. What do you find most rewarding about your career in OR/MS?
A. Like probably 90% of other OR/MS professionals, I find problem solving to be the most rewarding aspect of my career.
Q. What do you predict the future has in store for the field of OR/MS and for OR/MS practitioners?
A. I am optimistic about the future of OR/MS. In the '90s, we only scratched the surface of practical areas where OR/MS techniques can be applied.
The growth and expansion of the Internet and e-commerce will offer us many new challenges. In particular, the increasing "networked" nature of business is leading to large stores of data. OR/MS techniques and intelligent software will be critical if researchers are to make effective use of this data.
Computational biology is another area where I think OR/MS techniques and Optimization may play an important role.
We all need to keep our skills sharp for the challenges ahead!