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.
