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
postdoctoral 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 NPhard 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 oneelement 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
onevalued edges, there will always be such a degree constraint on some node that one can
drop and continue iteratively looking for more zero or oneedges (to delete or include) or
more constraints to relax with low violation. This settles a longstanding 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 IBMCPLEX as a software developer.
In his thesis, Achterberg discusses the integration of techniques from mixedinteger
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
mixedinteger programming in order to carry over the powerful modeling techniques from
constraint programming to mixedinteger 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 wellknown and recognized in the academic
world. Independent researchers identified it as the best noncommercial 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 noncompact semialgebraic sets via KarushKuhnTucker 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
KuhnKarushTucker 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.
