2023 ICS Prize Winners
The 2023 INFORMS Computing Society prize is awarded to Alberto del Pia and Aida Khajavirad for their path-breaking research on convexification of mixed-integer polynomial optimization problems, as detailed in the papers:
- A. Del Pia and A. Khajavirad, "A polyhedral study of binary polynomial programs", Mathematics of Operations Research, 42(2) 389‐410, 2017.
- A. Del Pia and A. Khajavirad, "On decomposability of multilinear sets", Mathematical Programming, 170(2) 387‐415, 2018.
- A. Del Pia and A. Khajavirad, "The multilinear polytope for acyclic hypergraphs", SIAM Journal on Optimization, 28(2) 1049–1076, 2018.
- A. Del Pia, A. Khajavirad, and N. V. Sahinidis, "On the impact of running intersection inequalities for globally solving polynomial optimization problems", Mathematical Programming Computation, 12 165‐191, 2020.
- A. Del Pia and A. Khajavirad, "The running intersection relaxation of the multilinear polytope", Mathematics of Operations Research, 46(3) 1008‐1037, 2021.
- A. Del Pia and A. Khajavirad, "Rank‐one Boolean tensor factorization and the multilinear polytope", arXiv:2202.07053, 2022.
- A. Del Pia and A. Khajavirad, "A polynomial‐size extended formulation for the multilinear polytope of beta‐acyclic hypergraphs", Mathematical Programming, 2023.
These papers make significant theoretical and computational advances for a wide range of mixed-integer nonlinear programming (MINLP) problems that contain a multilinear set as a substructure. Such problems arise in a range of settings, including computer vision, material design, and process systems in chemical engineering. A multilinear set is a set of binary points that must satisfy a collection of multilinear equations, and the focus of these works is the study of convexification of these sets by building strong and tractable relaxations. A special case of bilinear sets reduces to the important and well-studied Boolean Quadric Polytope (BQP). While some convexification results for BQP can be applied to multilinear sets, doing so requires working in a potentially much larger extended space, leading to weakening of the relaxations. In these papers, the authors instead directly study the multilinear set, leading to strong classes of valid inequalities, identification of cases when the convex hull of a set can be obtained from the convex hull of different components independently, and a thorough understanding of the complete convex hull for different notions of acyclic hypergraphs. The authors also demonstrated that these results can lead to significant computational improvements when incorporated within a state-of-the-art MINLP solver. Collectively, these papers make deep and insightful contributions to the field of mixed-integer nonlinear programming and the contributions are expected to have enduring impact from the standpoint of both theory and computation.
Honourable mentions:
- David Bergman (Connecticut), Andre Cire (Toronto), Willem-Jan van Hove (Carnegie Mellon), John Hooker (Carnegie Mellon), for laying the foundation for a fundamentally new research direction for discrete optimization based on decision diagrams.
- Hussein Hazimeh (MIT), Rahul Mazumder (MIT), Peter Radchenko (Sydney), for breakthroughs in the ability to compute sparse statistical estimators at scale in the big data era.
The 2023 ICS Prize Committee members are:
- Mirjam Dür (Augsburg)
- Yufeng Liu (UNC)
- Jim Luedtke (Wisconsin)
- Uday Shanbhag, Chair (Penn State)
2022 ICS Prize Winners
The 2022 INFORMS Computing Society prize is awarded to Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang, for their pioneering work on nonconvex stochastic optimization methods, as detailed in the papers:
- Saeed Ghadimi and Guanghui Lan, “Stochastic first- and zeroth-order methods for nonconvex stochastic programming”, SIAM Journal on Optimization 23(4), 2341-2368, 2013.
- Saeed Ghadimi, Guanghui Lan and Hongchao Zhang, “Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization”, Mathematical Programming 155(1-2), 267-305, 2016.
- Saeed Ghadimi and Guanghui Lan, “Accelerated gradient methods for nonconvex nonlinear and stochastic programming”, Mathematical Programming 156 (1-2), 59-99, 2016.
Nonconvex stochastic optimization comprises an important class of problems that are extremely challenging and have many applications. The three prize-winning papers contain several groundbreaking results in this area. In the first paper, the authors propose a novel randomized stochastic gradient descent method for unconstrained problems and establish, for the first time in the literature, complexity results for such types of algorithms. In the second paper, the authors adapt their methods to the constrained case by using a mini-batch of samples at each iteration. Their complexity results in such situations are shown to be near-optimal for the convex case. The third paper provides a generalization of Nesterov’s accelerated gradient (AG) method for nonconvex stochastic optimization problems and derives for the first time convergence results for these kinds of algorithms in the nonconvex case, showing optimal/best known rates of convergence when applied to some specific classes of problems. This work is based on solid, original, and innovative mathematical ideas and significantly advances the state-of-the-art in the field. In addition, given the amount of interest in these kinds of algorithms, the work is expected to have a significant impact in Operations Research, Computer Science, and other areas. Indeed, the three papers already have a total of over 1800 citations.
Runner-up: Dilek Gunnec (Ozyegin), S. Raghu Raghavan (Maryland), and Rui Zhang (CU Boulder) for their contributions on Influence Diffusion on Social Networks.
The 2022 ICS Prize Committee members are:
- Ricardo Fukasawa, Chair (Waterloo)
- Jonathan Eckstein (Rutgers)
- Ignacio Grossmann (Carnegie Mellon)