2006 Tucker Prize Citation
At the XIX. Mathematical Programming Symposium in Rio de Janeiro the Tucker Prize for an
outstanding paper authored by a student has been awarded to Uday V.
Shanbhag, University of Illinois at UrbanaChampaign, for his thesis
"Decomposition and Sampling Methods for Stochastic Equilibrium Problems".
Uday V. Shanbhag obtained his undergraduate degree in engineering at the
Indian Institute of Technology, Bombay(Mumbai) in 1993, and his Ph.D in the department of
Management Science and Engineering at Stanford University in 2006 under the direction of
Walter Murray. Currently, he is an Assistant Professor in the Department of Mechanical and
Industrial Engineering at the University of Illinois at UrbanaChampaign. Titled
"Decomposition and Sampling Methods for Stochastic Equilibrium Problems", Uday
Shanbhag's doctoral dissertation deals with a novel class of extremely difficult yet
practically very important optimization problems constrained by equilibrium conditions and
subject to uncertainty. Successive chapters deal with stochastic quadratic programs with
recourse (extending previous works on importancesamplingbased Lshape decomposition
methods), mathematical programs with complementarity constraints (MPCCs) (proposing an
interiorpoint based method that calculates stationary solutions satisfying an MPCC
secondorder condition, compared to prior methods that found only firstorder solutions),
twostage MPCCs with uncertainty (solving via a primaldual method that relies on sampling and
a scenariobased decomposition), and a twoperiod spotforward market under uncertainty
formulated as a stochastic NashStackelberg game (motivated by applications to electric power
markets with oligopolies). The research utilizes and advances the stateoftheart nonlinear
programming and Monte Carlo sampling methods for tackling such problems. Several new ideas and
formulations are introduced; great care is placed on the highly technical convergence
analysis; and the results from the implementation of the proposed methods on realistic
applications are interpreted with interesting insights. The end product is an outstanding
piece of work that combines theory, algorithms, applications, and implementations, bringing
together and significantly advancing several areas in continuous optimization, and enabling
the application of new optimization paradigms. Overall, this is a very impressive
dissertation, which by its breath and depth, qualifies the work as the winner of the 2006
A.W. Tucker Prize.
The other two Tucker Prize finalists chosen by this year's Tucker Prize Committee
consisting of Thomas McCormick (chair), Monique Laurent, JongShi Pang, and Rüdiger
Schultz are José Rafael Correa and Dion
Gijswijt.
José Rafael Correa graduated as a Mathematical Engineer from
Universidad de Chile in 1999. He completed his PhD in Operations Research at MIT under the
supervision of Michel Goemans and Andreas Schulz in June 2004. Currently Dr. Correa is an
Assistant Professor at the School of Business at Universidad Adolfo Ibáñez.
Dr. Correa was named as a Tucker Prize finalist for his Ph.D. thesis titled
"Approximation Algorithms for Packing and Covering Problems". This thesis develops
approximation algorithms for applied problems in three quite different areas. The first comes
from scheduling packets in an interconnection network, which gets abstracted into a problem of
coloring edges in bipartite graphs, and then further into a binpacking problem. The second
considers the natural problem of packing rectangles (or higherdimensional cubes) into
boxes. It extends previous results about 2dimensional binpacking to find an asymptotic
polynomial time approximation scheme for packing ddimensional cubes into unit cubes, and it
gets new results for packing rectangles into square bins. In both cases new tools are
developed to make the arguments work. The third considers the classic problem of scheduling
precedenceconstrained jobs on a single machine to minimize the average weighted completion
time. It significantly extends known results by using linear programming relaxations to show
that essentially all known 2approximation algorithms comply with the "Sidney
decomposition", and then shows that the sequencing problem can be seen as a special case
of vertex cover.
Dion Gijswijt completed his curriculum in Mathematics at the University of
Amsterdam, where he graduated in 2001, and received his PhD degree under the supervision of
Lex Schrijver in September 2005. He is currently a researcher at the Etvs University in
Budapest, and he will join the University of Amsterdam in September 2006. Dr. Gijswijt has
been selected as a Tucker Prize finalist for his Ph.D. thesis entitled "Matrix Algebras
and Semidefinite Programming Techniques for Codes". This thesis presents a novel method
for bounding the maximum cardinality of a nonbinary code with given minimum Hamming distance,
which is one of the most basic problems in coding theory and an instance of the stable set
problem in Hamming graphs. The method also applies to the dual problem of bounding the minimum
size of covering codes. The new bound he proposes improves the classical linear programming
bound of Delsarte, and gives sharper estimates than the stateofthe art methods on many
instances of codes up to length 12 on alphabets of sizes 3, 4, and 5. The method of
Dr. Gijswijt relies on deep insight from noncommutative algebra allied with the use of
semidefinite optimization. While the algebraic ingredient in the Delsarte method is the
commutative BoseMesner algebra of the Hamming scheme, the noncommutative Terwilliger algebra
plays a crucial role in Gijswijt's method. Extending earlier work of Schrijver for the binary
case, Gijswijt finds the explicit blockdiagonalization of the Terwilliger algebra, which
enables him to apply symmetry reduction and reformulate his new bound via a compact
semidefinite program of size O(n^3) for a code with word length n. Gijswijt also studies the
link to the matrixcut method of Lovasz and Schrijver. This work shows how sophisticated
algebraic techniques can be successfully used for exploiting symmetries and formulate compact
semidefinite relaxations for hard combinatorial optimization problems, thus adding a new
algebraic technique to the mathematical programming toolbox.
