2009 Tucker Prize Citation

The Tucker Prize for an outstanding paper authored by a student has been awarded to Mohit Singh, Microsoft Research, Cambridge, for his thesis: Iterative Methods in Combinatorial Optimization.

Mohit Singh obtained his undergraduate degree in Computer Science and Engineering from the Indian Institute of Technology, Delhi in 2003. He completed his Ph.D. in the Algorithms, Combinatorics and Optimization program from Tepper School of Business, CMU under the supervision of Prof. R. Ravi in May 2008. He is currently a post-doctoral researcher at Microsoft Research, New England. His research interests lie in theoretical computer science, combinatorial optimization, and approximation algorithms. He published two or more papers in each of the following prestigious conferences STOC, FOCS, IPCO and APPROX.

Singh's thesis introduces a new technique for solving important optimization problem exactly and extends it to solving their NP-hard variants obtained by introducing complicating side constraints.

The method, iterative in nature, suggests a natural recursive algorithm for obtaining exact solutions to problems by writing a carefully constructed linear programming relaxation and arguing that the relaxation always has a zero- or one-element in an optimal basic solution. The crux of the argument exploits the fact that the set of tight constraints at a basic solution can be represented by a sparse family, hence the cardinality of the support of the solution is also sparse.

The thesis shows a large set of problems amenable to this technique ranging from spanning trees in directed and undirected graphs, minimal matroid bases and perfect matchings.

While it is an impressive contribution to offer novel proofs of several classical polyhedral results with implications to exact algorithms, the thesis makes an even larger contribution by showing how the method can be extended to handle side constraints.

As an example, consider the classical Minimum Spanning Tree problem with upper bounds on the degrees of the various nodes in the tree. If the current fractional support of nonzero edges have degree at most one more than the degree bound at some node, the degree constraint for this node can be dropped since in the worst case, even if all these edges in the fractional support were chosen in the final solution, the degree constraint will only be violated by one. Singh's striking result (obtained jointly with Lau) shows that if there are no zero- or one-valued edges, there will always be such a degree constraint on some node that one can drop and continue iteratively looking for more zero- or one-edges (to delete or include) or more constraints to relax with low violation. This settles a long-standing conjecture for this problem due to Goemans affirmatively.

Singh's thesis carefully rounds out the various other classes of optimization problems where such side constraints can be handled approximately; He derives new approximation results for general connectivity problems (such as survivable network design) with side degree constraints, as well as for multicriteria spanning tree and matroid bases problems. The thesis also gives new short proofs of various constrained optimization problems such as the generalized assignment problem using the same relaxation framework.

Singh's thesis research has already attracted follow up work in several prestigious conferences such as STOC 2008, IPCO 2008 and FOCS 2008, and continues to generate a flurry of research activity around new applications of these techniques.

This is a very impressive dissertation, which by its breath and depth qualifies the work as the winner of the 2009 A.W. Tucker Prize.

The other two Tucker Prize finalists chosen by this year's Tucker Prize Committee are Tobias Achterberg and Jiawang Nie.

Tobias Achterberg studied at the Technical University of Berlin where he finished both his master and his doctoral studies. The title of his dissertation is: Constraint Integer Programming. It was supervised by Martin Grötschel, and finished during the summer of 2007. He is currently with IBM-CPLEX as a software developer.

In his thesis, Achterberg discusses the integration of techniques from mixed-integer programming (MIP), constraint programming (CP), and satisfiability (SAT) solving. All three areas deal with optimization or feasibility problems over integer variables, which can be solved by tree search algorithms. Numerous industrial applications can be modeled as MIP, CP, or SAT. In particular, MIP has drawn a lot of academic and commercial attention.

Achterberg introduces the concept of constraint integer programming (CIP), which generalizes mixed-integer programming in order to carry over the powerful modeling techniques from constraint programming to mixed-integer programming. He makes use of the entire theory of constraint and integer programming and compares their theoretical advantages and disadvantages. He analyzes the different techniques carefully by conducting practical experiments, and he implements all variants with outstanding program quality and remarkable attention to detail. This results in the software SCIP, which consists of more than 250,000 lines of code. Although CIP is a more general problem class than MIP, the performance of SCIP on pure MIP instances is comparable to the best commercial MIP codes.

By now, the code of Achterberg is well-known and recognized in the academic world. Independent researchers identified it as the best non-commercial code for MIP, and it is used in a variety of academic and industrial projects. The fact that the source code of the software is freely available opens up new research possibilities in the area of optimization.

Jiawang Nie did his undergraduate studies in China, finishing with a master of science in 2000 at the Chinese Academy of Sciences. He then moved to the University of California, Berkeley, where he wrote a dissertation entitled: Global Optimization of Polynomial Functions and Applications, supervised by James Demmel and Bernd Sturmfels. The thesis was finished in the fall of 2006. Jiawang Nie is currently assistant professor at the University of California in San Diego.

Nie's dissertation focusses on the interplay between optimization with polynomial functions and semidefinite programming (SDP). More precisely, he showed that quite general (and extremely difficult) problems in polynomial optimization could be solved by a converging sequence of approximations, each efficiently computable using recently developed techniques of SDP, and he formulated and solved engineering design optimization problems using these techniques.

One key ingredient lies in the observation that a polynomial is necessarily nonnegative if it has a "sums of square" (SOS) representation through other polynomials. In the dissertation he explores this idea applied both in the context of minimizing polynomials via Sum of Squares over the Gradient Ideal, and also through representations of positive polynomials on non-compact semialgebraic sets via Karush-Kuhn-Tucker ideals. His work improves on previous results of Lasserre, Jibetean, Laurent and Parrilo by removing assumptions such that the gradient variety must be finite. By exploiting the Kuhn-Karush-Tucker condition, he extends his results from unconstrained to constrained optimization. These are interesting and far reaching results, and make a significant improvement over the prior best results in this area.

These theoretical results are successfully applied in various areas of engineering, for instance shape optimization, perturbation analysis of polynomial systems of equations, or sensor network location.

Nie currently has more than a dozen publications in top quality journals on optimization, such as Mathematical Programming and SIOPT.