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 Urbana-Champaign, 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 Urbana-Champaign.

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 importance-sampling-based L-shape decomposition methods), mathematical programs with complementarity constraints (MPCCs) (proposing an interior-point based method that calculates stationary solutions satisfying an MPCC second-order condition, compared to prior methods that found only first-order solutions), two-stage MPCCs with uncertainty (solving via a primal-dual method that relies on sampling and a scenario-based decomposition), and a two-period spot-forward market under uncertainty formulated as a stochastic Nash-Stackelberg game (motivated by applications to electric power markets with oligopolies). The research utilizes and advances the state-of-the-art 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, Jong-Shi 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 bin-packing problem. The second considers the natural problem of packing rectangles (or higher-dimensional cubes) into boxes. It extends previous results about 2-dimensional bin-packing to find an asymptotic polynomial time approximation scheme for packing d-dimensional 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 precedence-constrained 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 2-approximation 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 state-of-the 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 Bose-Mesner 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 block-diagonalization 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 matrix-cut 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.

  top of page      close this window