Simge Küçükyavuz (left), Diego Morán, and Jon Lee.
The 2012 recipient of the Student Paper Prize of the INFORMS Optimization Society is Diego Morán of Georgia Tech, for his paper "A Strong Dual for Conic Mixed-Integer Programs (SIAM Journal on Optimization. Co-Authored with Santanu S. Dey and Juan Pablo Vielma).
Duality is a cornerstone of optimization theory and is often as essential for algorithmic developments as for theoretical foundations. While duality relations of linear and conic continuous optimization problems are well understood and are widely used, the duality in integer programming is much more elusive. However certain concepts carry over from linear programming duality to the linear mixed integer programming (MIP) case. The essential property that one seeks is the existence of a (subadditive) strong dual, that is a problem which is finite whenever the primal is finite and whose optimal value coincides with that of the primal when both problems have a finite solution. The dual is typically used in an algorithm to construct bounds on the optimal primal value. In the winning paper, Diego Morán and his co-authors develop a much anticipated strong dual for conic MIP. Even though the extension from LP duality to conic duality is well known, the MIP case is not straightforward. The authors establish a collection of results for conic mixed-integer problems that cleanly and elegantly lead to the existence of the subadditive strong dual under a simple condition. This paper clearly provides a significant step forward in the theory of mixed-integer nonlinear programming.
Simge Küçükyavuz, Katya Scheinberg (Chair), Renata Sotirov.