Professor, former student share prestigious award for problem-solving theory

Sherali and Adams won the prestigious award for developing a mathematical methodology called the "Reformulation-Linearization Technique" (RLT), although a slate of Sherali's Ph.D. students worked on the project during the course of several years, Sherali said. 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, he 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.

Source: Virginia Tech