2016 ICS Prize Winners
The 2016 INFORMS Computing Society prize is awarded to Iain Dunning, Joey Huchette, and Miles Lubin for their development of the JuMP optimization package. This package allows researchers to conveniently and quickly model optimization problems using Julia.
JuMP is a Julia-language based modeling language that allows users to express a wide variety of optimization problems (linear, mixed-integer, quadratic, conic-quadratic, semidefinite, and nonlinear) in a convenient algebraic syntax. JuMP’s design leverages advanced features of the Julia language to offer distinctive functionality while achieving performance in instance creation often similar to commercial modeling tools. Powerful features of JuMP that make it an attractive tool for optimization tasks include implementation of callbacks for modifying the branch-and-bound algorithm, automatic differentiation of user-defined nonlinear functions, and easy-to-develop add-ons for specialized problem classes. The modular design has enabled many third-party extensions for more specialized optimization problem classes. Specifically, JuMP can be easily used to embed optimization problems as part of a complex algorithmic control structure, such as in decomposition methods. In just two years since its creation, JuMP has had a significant impact in the computational optimization community. JuMP is used to teach optimization in more than a dozen courses around the world. JuMP has been embedded in packages for important applications in engineering, statistics, and data analysis.
2016 ICS Prize Selection Committee:
- Jon Lee (University of Michigan)
- Jeff Linderoth (University of Wisconsin-Madison)
- Nick Sahinidis, Chair (Carnegie Mellon University)
2015 ICS Prize Winners
The 2015 INFORMS Computing Society prize is awarded to Suvrajeet Sen, Dinakar Gade, Julia Higle, Simge Küçükyavuz, Lewis Ntaimo, and Hanif Sherali for their seminal work on stochastic mixed integer programming, published in:
- Suvrajeet Sen, Julia L Higle, "The C3 Theorem and a D2 Algorithm for Large Scale Stochastic Mixed-Integer Programming: Set Convexification", Mathematical Programming, 104, pp. 1-20, 2005.
- Suvrajeet Sen, Hanif D. Sherali, "Decomposition with Branch-and-Cut Approaches for Two-Stage Stochastic Mixed-Integer Programming", Mathematical Programming, 106, pp. 203-223, 2006.
- Lewis Ntaimo, Suvrajeet Sen, "The Million Variable 'March' for Stochastic Combinatorial Optimization", Journal of Global Optimization, 32, pp. 385-400, 2005.
- Lewis Ntaimo, Suvrajeet Sen, "A Comparative Study of Decomposition Algorithms for Stochastic Combinatorial Optimization", Computational Optimization and Applications, 40, pp. 299-319, 2008.
- Dinakar Gade, Simge Küçükyavuz, Suvrajeet Sen, "Decomposition Algorithms with Parametric Gomory Cuts for Two-Stage Stochastic Integer Programs", Mathematical Programming, 144, pp. 39-64, 2014.
The importance of optimization under uncertainty is widely recognized in Operations Research and Management Science, with interest in the problem dating back to the origins of the field. The inherent difficulty of such problems has spawned a number of formalizations with stochastic programming being one of the most prominent. Stochastic mixed integer programming, by combining uncertainty and integer decision variables, increases the challenge beyond what can be addressed, even with clever modeling, with state-of-the-art commercial solvers. The awarded body of work represents a significant step forward on these very difficult problems, through elegant theoretical and computational studies focusing on disjunctive decomposition techniques and the generation of cutting planes. Combined with further theoretical insights surrounding the approximation of mixed integer programming value functions, these advances have been computationally harnessed to solve problems of substantial size, pushing the practical ability of optimization techniques. This body of work is a sustained set of theoretical insights, careful analysis, and rigorous empirical investigations and justifications that together represent a worthy contribution to the study of optimization under uncertainty.
2015 ICS Prize Selection Committee:
- Chris Beck, Chair (University of Toronto)
- Jeff Linderoth (University of Wisconsin-Madison)
- Nick Sahinidis (Carnegie Mellon University)
2014 ICS Prize Winners
The 2014 Informs Computing Society prize is awarded to Jim Ostrowski, Jeff Linderoth, Fabrizio Rossi, and Stefano Smriglio for their work on dealing with symmetry in combinatorial optimization problems, as detailed in:
- Orbital Branching, Mathematical Programming, 126:147-178, 2011.
- Constraint Orbital Branching, IPCO 2008: Lecture Notes in Computer Science, Vol. 5035, Springer, 225-239, 2008.
- Solving Large Steiner Triple Covering Problems, Operations Research Letters, 39:127-131, 2011.
Symmetry constitutes one of the "last frontiers" of integer programming, as it is easily observed that even moderate size problem instances with a large amount of symmetry routinely defeat all general purpose solvers. Symmetry, as is well-known, produces large branch-and-bound trees. Furthermore, formulations of combinatorial problems with a high degree of symmetry also tend to yield very weak relaxations whose bounds do not improve much (or at all) even after a large amount of branching.The awarded work encompasses a family of elegant techniques which branch on combinatorial objects not directly obvious from a problem formulation. This careful enumeration not only avoids the direct cost of enumeration, but by capturing structure of the problem quickly leads to improved bounds. On the computational side, the work also incorporates innovative high-throughput computing techniques. These efforts proved successful at obtaining optimal solutions to previously unsolved instances as well as improved bounds, thus covering a nice span from theory to implementation. Finally, the work may prove influential in the development of commercial integer programming software.
2014 ICS Prize Committee:
- Chris Beck (University of Toronto)
- Daniel Bienstock, Chair (Columbia University)
- Nick Sahinidis (Carnegie Mellon University)
2013 ICS Prize Winner
The 2013 INFORMS ICS Prize was awarded to John Gunnar Carlsson for his papers
- John Gunnar Carlsson, "Dividing a territory among several vehicles", INFORMS Journal on Computing, Vol. 24, No. 4, Fall 2012, pp. 565–577.
- John Gunnar Carlsson and Erick Delage, "Robust partitioning for stochastic multivehicle routing", Operations Research (published online May 24, 2013);
- John Gunnar Carlsson and Raghuveer Devulapalli, "Dividing a territory among several facilities", INFORMS Journal on Computing (published online December 20, 2012).
The awarded set of papers comprise an elegant analysis of service problems in the plane, in the asymptotic limit of large numbers of customers whose location is stochastically distributed under fairly broad assumptions. The goal in one version is to identify a partition of the space such that the stochastic workload in each partition is asymptotically equal. In another version the partitioning will be into regions to be served by facilities, so as to minimize the maximum workload of a facility. In the third version, a robust partitioning problem is considered, where the customer distribution is not completely determined (an ambiguous distribution setting).
To solve these problems the research incorporates novel and elegant analytical and algorithmic tools in order to simultaneously reason about the shape of the partitions and the stochastic work-load allocation objectives. The papers combine rigorous mathematical analysis, detailed empirical/algorithmic work, and an exceptionally clear exposition. In blending fundamental, modern methodology as well as practical considerations, the work should stimulate continued interest in the problems and methodologies investigated.
2013 ICS Prize Committee:
- Chris Beck (University of Toronto)
- Daniel Bienstock (Columbia University)
- Dorit Hochbaum, Chair (University of California, Berkeley)
2012 ICS Prize Winners
The 2012 INFORMS ICS Prize was awarded to A.A. Ahmadi, A. Olshevsky, P. A. Parrilo, and J. N. Tsitsiklis for their papers
[1] A. A. Ahmadi, A. Olshevsky, P. A. Parrilo, and J. N. Tsitsiklis. NP-hardness of deciding convexity of quartic polynomials and related problems. Mathematical Programming, 2011. Online version available at http://arxiv.org/abs/1012.1908,
[2] A. A. Ahmadi and P. A. Parrilo. A convex polynomial that is not sos-convex. Mathematical Programming, 2011. Online version available at http://arxiv.org/abs/0903.1287, and
[3] A. A. Ahmadi and P. A. Parrilo. A complete characterization of the gap between convexity and sos-convexity. SIAM Journal on Optimization, 2012. To appear. Online version available at http://arxiv.org/abs/1111.4587.
A common approach to solving optimization problems is to leverageconvexity; linear and convex quadratic programming provide classical examples of polynomially solvable problems. The awarded papers explore the complexity frontier of optimization problems and its relationship to convexity.
In paper [1], the authors show that the problem of deciding whether a 4-degree polynomial is convex to be NP-hard in the strong sense. The implication of this result is that unless P=NP, there cannot be a polynomial time or even pseudo-polynomial time algorithm for checking polynomial convexity. Although in many applications of convex optimization we design problems that are by construction convex, the result suggests that in general we cannot characterize convexity in optimization problems. These hardness results are extended to the respective problems of deciding strict convexity, strong convexity, pseudoconvexity, and quasiconvexity of polynomials. Each of these well-known variants of convexity have their own special role in optimization theory. For example, strict convexity is useful for guaranteeing uniqueness of optimal solutions, strong convexity is a common assumption in convergence analysis of many iterative Newton-type algorithms, and quasiconvexity appears in the problem of deciding convexity of sets, and in many applications in economics and statistics. An interesting dichotomy here is that quasiconvexity and pseudoconvexity of odd degree polynomials can be decided in polynomial time, whereas the same questions for polynomials of even degree larger than two are strongly NP-hard.
Paper [2] shows the first known example of a convex polynomial that is not sos-convex. Such polynomials are generally not easy to construct. The authors resort to computational methods, involving semi-definite programming, to find their polynomial. Their computer assisted proof demonstrates the power of sum of squares certificates and SDP in automated theorem proving.
In [3], the authors give a complete characterization of all the degrees and dimensions for which convexity and sos-convexity are equivalent.
2012 ICS Prize Committee:
- Daniel Bienstock (Columbia University)
- Dorit Hochbaum (University of California, Berkeley)
- Pascal Van Hentenryck, Chair (NICTA)