2021 ICS Prize Winners
The 2021 INFORMS Computing Society prize is awarded to
Adolfo R. Escobedo, Erick Moreno-Centeno, Christopher Lourenco, and Timothy Alden Davis for their pioneering work on roundoff-error-free matrix factorization, as detailed in the papers:
- Adolfo R. Escobedo and Erick Moreno-Centeno, "Roundoff-Error-Free Algorithms for Solving Linear Systems via Cholesky and LU Factorizations", INFORMS Journal on Computing, 27 (2015), pp. 677-689.
- Adolfo R. Escobedo and Erick Moreno-Centeno, "Roundoff-Error-Free Basis Updates of LU Factorizations for the Efficient Validation of Optimality Certificates", SIAM Journal on Matrix Analysis and Applications, 38 (2017), pp. 829-853.
- Adolfo R. Escobedo, Erick Moreno-Centeno, and Christopher Lourenco, "Solution of Dense Linear Systems via Roundoff-Error-Free Factorization Algorithms: Theoretical Connections and Computational Comparisons", ACM Transactions on Mathematical Software, 44 (2018), pp. 1-24.
- Christopher Lourenco, Adolfo R. Escobedo, Erick Moreno-Centeno, and Timothy Alden Davis, "Exact Solution of Sparse Linear Systems via Left-Looking Roundoff-Error-Free LU Factorization in Time Proportional to Arithmetic Work", SIAM Journal on Matrix Analysis and Applications, 40 (2019), pp. 609-638.
Linear Programming, the basis of operations research, is considered a solved problem by most researchers and practitioners. Yet, due to round-off errors in underlying linear algebra solvers, such as LU factorization, current algorithms and solvers are inadequate for large-scale problems requiring exact solutions. Such problems arise in a plethora of applications including computer-assisted mathematical proofs, healthcare, national defense, and generating stable MIR cuts. State-of-the-art algorithms present a dichotomy: inexact solutions obtained quickly or exact solutions with excessive run times. The nominated papers show that the currently-used rational-arithmetic approaches are inefficient, and propose a framework to exactly solve rational systems of linear equations (SLEs) via integer-preserving, roundoff-error-free (REF) LU factorizations. These papers form the new foundation of exact LP by modernizing integer-preserving Gaussian elimination (IPGE) and developing new theory.
The 2021 ICS Prize Committee members are:
- Ignacio Grossmann (CMU)
- Katya Scheinberg, Chair (Cornell)
- Suvrajeet Sen (USC)
2020 ICS Prize Winners
The 2020 INFORMS Computing Society prize is awarded to Samuel Burer and Renato D. C. Monteiro for their pioneering work on low-rank semidefinite programming, as detailed in the papers:
- A Nonlinear Programming Algorithm for Solving Semidefinite Programs via Low-Rank Factorization, Mathematical Programming Series B 95: 329–357, 2003.
- Local Minima and Convergence in Low-Rank Semidefinite Programming, Mathematical Programming Series A 103, 427–444, 2005.
This body of work focuses on semidefinite programs (SDPs) that are desired to have low-rank optimal solutions, and introduces the novel idea of reformulating such SDPs as nonconvex quadratically constrained quadratic programs to reduce the dimension of the problem for computational purposes. Their key idea – at first computational, but later was quickly supported by a rigorous theory – is that despite the nonconvexity of the reformulated problem, it can be solved reliably and with high efficiency using standard optimization techniques. This was a remarkable and unexpected insight at its time, but its significance became apparent more recently through the upsurge of very large-scale matrix optimization problems seeking low-rank optimal solutions to promote the distillation of essential simple structure in high dimensional data in machine learning. It is quite fair to say that the insights and theoretical developments in this awarded body of work have been not just fundamental but also foundational contributions in reshaping this exceptionally rich and growing research landscape in machine learning, inspiring many new developments in analyzing nonconvex problems that are provably easy to solve. Moreover, as a vital computational tool in solving large-scale SDPs, this work has been widely employed in a variety of other applications including network clustering, image analysis, quantum chemistry, robust PCA, and many others.
The 2020 ICS Prize Committee members are:
- Suvrajeet Sen, Chair (USC)
- Necdet Serhat Aybat (PSU)
- Fatma Kilinc-Karzan (CMU)
2019 ICS Prize Winners
The 2019 INFORMS Computing Society prize is awarded to William E. Hart, Carl D. Laird, Jean-Paul Watson, David L. Woodruff, Gabriel A. Hackebeil, Bethany L. Nicholson & John Siirola for spearheading the creation and advancement of Pyomo, an open-source software package for modeling and solving mathematical programs in Python.
The 2019 ICS Prize Committee members are:
- Fatma Kilinc-Karzan (CMU)
- Thomas Sharkey (RPI)
- Douglas Shier, Chair (Clemson)
2018 ICS Prize Winners
The 2018 INFORMS Computing Society prize is awarded to James V. Burke, Frank E. Curtis, Adrian S. Lewis, and Michael L. Overton for their pioneering work on gradient sampling methods for nonsmooth optimization, as detailed in the papers:
- "Approximating Subdifferentials by Random Sampling of Gradients.” Mathematics of Operations Research, 27:567-584, 2002.
- “A Sequential Quadratic Programming Algorithm for Nonconvex, Nonsmooth Constrained Optimization.” SIAM J. Optimization, 22(2):474-500, 2012.
- “A Robust Gradient Sampling Algorithm for Nonsmooth, Nonconvex Optimization.” SIAM J. Optimization, 15(3):751-779, 2005.
- “A BFGS-SQP method for Nonsmooth, Nonconvex, Constrained Optimization and its Evaluation using Relative Minimization Profiles.” Optimization Methods and Software, 32(1):148-181, 2017.
- “Gradient Sampling Methods for Nonsmooth Optimization.” arXiv:1804.11003, 2018.
The 2018 ICS Prize Committee members are:
- Fatma Kilinc-Karzan (CMU)
- Andreas Waechter, Chair (Northwestern)
- Douglas Shier (Clemson)
2017 ICS Prize Winners
The 2017 INFORMS Computing Society prize is awarded to Shabbir Ahmed, George Nemhauser, and Juan Pablo Vielma for their pioneering work on mixed integer linear programming formulations for piece-wise linear functions, as detailed in the papers:
- "Mixed-integer models for nonseparable piecewise linear optimization: unifying framework and extensions", Juan Pablo Vielma, Shabbir Ahmed and George Nemhauser, Operations Research, vol. 58, 303-315, 2010"
- "Modeling disjunctive constraints with a logarithmic number of binary variables and constraints", Juan Pablo Vielma and George Nemhauser, Mathematical Programming, vol. 128, 49-72, 2011.
- "Embedding Formulations and Complexity for Unions of Polyhedra", Juan Pablo Vielma, to appear in Management Science.
These papers develop advanced techniques to build mixed integer programming (MIP) formulations for disjunctive constraints with a special emphasis on piecewise linear (PWL) functions. The authors present comprehensive descriptions and comparisons of formulations for PWL functions and review in a unified manner the strength and quality measures of most known formulations. Before this body of work, the strongest-possible (ideal) formulations for PWL functions required many additional auxiliary variables. These papers introduce ideal formulations that are significantly smaller than previously known. In particular, the authors give an ideal formulation without continuous auxiliary variables whose size grows logarithmically with the size of the constraints. The final award-winning paper introduces a systematic geometric construction that generalizes the earlier work. In all cases, the authors give convincing evidence of the computational advantage given by the new formulations. The work has significant computational impact, especially in the area of non-convex optimization, where building piecewise linear approximations and relaxations of nonconvex functions is the state-of-the-art approach for solving this challenging class of problems.
2017 ICS Prize Selection Committee:
- Jon Lee (University of Michigan)
- Jeff Linderoth, Chair (University of Wisconsin-Madison)
- Jean-Paul Watson (Sandia National Laboratories)