Gonzalo Muñoz (left) and Jim Luedtke.
Citation
Gonzalo Muñoz (Columbia University) is selected as the winner of the 2016 INFORMS Optimization Society Student Paper Prize for his paper with Daniel Bienstock, "LP Formulations for Mixed-Integer Polynomial Optimization Problems”.
This paper considers the construction of linear programming (LP) approximations of mixed-integer polynomial optimization problems that exploit the sparsity structure of the constraints, where sparsity is measured by tree-width of an associated graph. A key contribution of the paper is the introduction of a broad class of problems, termed network mixed-integer polynomial optimization problems (NPO’s), and the construction of LP approximations of such problems whose size depends on the underlying graph in the problem (as opposed to the intersection graph derived from a particular formulation). This NPO class of problems includes important applied problems that have been extensively studied in recent literature, including mixed-integer non-convex optimization models associated with AC optimal flow and gas transmission networks. In addition to providing directly usable LP formulations for instances that are suitably sparse (i.e., having low tree-width in the associated graph), the paper provides insight into how the sparsity structure impacts the complexity of (approximately) solving such problems.
Hamza Fawzi (left) and Jim Luedtke.
Honorable Mention
Hamza Fawzi (MIT), for his paper with Pablo A. Parrilo, "Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank".
Selection committee
Jim Luedtke (chair), Güzin Bayraksan, Shiqian Ma, Mohit Tawarmalani