Professor shares prestigious award on new problem-solving theory
The Institute for Operations Research and the Management Sciences (INFORMS) has awarded its Frederick W. Lanchester Prize research award to Hanif Sherali, a University Distinguished Professor and the W. Thomas Rice Chair of Engineering in the Virginia Tech Grado Department of Industrial and Systems Engineering.
The INFORMS prize is shared by Sherali with Warren Adams, a former student of Sherali's at Virginia Tech and now a mathematical sciences professor at Clemson University, for the best contribution to operations research and the management sciences published in English. The oldest award given by INFORMS, the Lanchester award includes a medallion and $5,000 cash. It recently was presented at the INFORMS national meeting in Washington D.C.
Sherali and Adams won the prestigious award for developing a mathematical methodology called the "Reformulation-Linearization Technique" (RLT), although a slate of Ph.D. students under Sherali worked on the project during the course of several years. The RLT is the first procedure developed for automatically constructing an explicit algebraic representation of the ideal convex hull representation for general classes of discrete problems, and can likewise solve wide classes of continuous nonconvex problems, Sherali said. The theory can be used to reformulate a difficult problem through a mathematical transformation that makes previously difficult, unapproachable problems easier to solve.
"Such problems arise in production, location-allocation, distribution, process and engineering design, and several operational contexts in various service industries," Sherali said. "This technique largely supports two paradigms that are revolutionizing the field. First, historically, the fields of discrete optimization and continuous nonlinear optimization have remained quite separate, with researchers specializing in one of these arenas and having only a basic working-knowledge of the other. The RLT technique has helped unify these two seemingly disparate fields by demonstrating that both discrete and continuous nonconvex problems can be viewed and treated in a common light, so that approaches developed for one type of problem can be beneficially transferred to the other. This has opened a flurry of research activity in the interface. Second, in recent years, researchers working with nonconvex optimization problems have come to realize that in order to successfully solve such formidable problems, it is not sufficient to simply construct a 'mathematically correct' model formulation. Rather, it is imperative to derive a 'good' formulation, where goodness is characterized by how tightly the underlying continuous, lower-bounding, linear programming relaxation of the model envelopes the so-called convex hull -- a set of weighted averages -- of feasible solutions."
"The new theory has enabled the solution of several standard test cases of the quadratic assignment problem and the design of water distribution networks, which previously were unsolved for 30 to 40 years," Sherali said. "Many researchers in cross-disciplinary fields are now using our RLT methodology to solve challenging, previously unsolved problems," he added. "Also, the popular commercial global optimization package, BARON, implements RLT constructs."
Seeds for the RLT theory first appeared in Sherali's own dissertation in 1979, with substantial work on the theory starting in 1989 under a National Science Foundation grant. The first seminal paper on the theory appeared in the SIAM Journal on Discrete Mathematics in 1990, where the Reformulation-Linearization Technique term was coined. The two prize-winners also published a book in 1999 on the RLT theory, and continue to refine the theory.
The award is given based on the developed theory's originality, the new areas of application it opens up, the degree to which existing theory or method is unified or simplified, according to the Institute for Operations Research and the Management Sciences.
Adams graduated with his Ph.D. from Virginia Tech in 1985, with Sherali serving as his adviser. "I have published various other works, but am most proud of the RLT," Adams said. "It has been an absolutely wonderful experience working with Dr. Sherali, and I am thrilled to have been on this 'research ride' with him. He is the brightest and most capable researcher I have met. He is also my friend."
Work on the RLT theory is not complete, though. "There are still many computational challenges that remain at applying RLT effectively to solve several formidable applications in design and operational contexts," Sherali said.
A Virginia Tech faculty member since 1979, Sherali was named a University Distinguished Professor by the Virginia Tech Board of Visitors in 2007. Additional honors given to Sherali include the IIE David F. Baker Distinguished Research Award, the Thomas Saaty Prize for Advances in Mathematical and Management Sciences, the INFORMS Koopman Research Prize, and the INFORMS Computer Science Research Award. He is the only member of the engineering faculty to receive the Dean's Award of Excellence in all three categories -- teaching, research, and service.
INFORMS is the largest professional operations research society in the world. It serves the scientific and professional needs of educators, investigators, scientists, students, managers and consultants, as well as the organizations they serve, by publishing scholarly journals that describe the latest operations-research methods and applications.
