Optimization problems are everywhere in engineering: Balancing design tradeoffs is an optimization problem, as are scheduling and logistical planning. The theory — and sometimes the implementation — of control systems relies heavily on optimization, and so does machine learning, which has been the basis of most recent advances in artificial intelligence.
This week, at the IEEE Symposium on Foundations of Computer Science, a trio of present and past MIT graduate students won a best-student-paper award for a new “cutting-plane” algorithm, a general-purpose algorithm for solving optimization problems. The algorithm improves on the running time of its most efficient predecessor, and the researchers offer some reason to think that they may have reached the theoretical limit.
But they also present a new method for applying their general algorithm to specific problems, which yields huge efficiency gains — several orders of magnitude.
“What we are trying to do is revive people’s interest in the general problem the algorithm solves,” says Yin-Tat Lee, an MIT graduate student in mathematics and one of the paper’s co-authors. “Previously, people needed to devise different algorithms for each problem, and then they needed to optimize them for a long time. Now we are saying, if for many problems, you have one algorithm, then, in practice, we can try to optimize over one algorithm instead of many algorithms, and we may have a better chance to get faster algorithms for many problems.”
Lee is joined on the paper by Aaron Sidford, who was an MIT graduate student in electrical engineering and computer science when the work was done but is now at Microsoft Research New England, and by Sam Wong, who earned bachelor’s and master’s degrees in math and electrical engineering and computer science at MIT before moving to the University of California at Berkeley for his PhD. Read more