ICS Prize

2018 ICS Prize

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)
• Jean-Paul Watson (Sandia National Laboratories)

2017 ICS Prize

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)

2016 ICS Prize

The 2016 INFORMS Computing Society prize is awarded to Iain Dunning, Joey Huchette, and Miles Lubin for their the 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

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

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

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

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)

2011 ICS Prize

The 2011 ICS Prize was awarded to Dorit Hochbaum for her paper, "Polynomial Time Algorithms for Ratio Regions and a Variant of Normalized Cut" (IEEE Transaction on Pattern Analysis and Machine Intelligence, vol. 32, no. 5, pp 889-898, 2010).

This paper presents an efficient, highly novel approach for solving a group of well-known combinatorial optimization problems arising in computer vision and image analysis, including the ratio-regions problem and a variant of the normalized-cut problem. Each problem expresses two conflicting objectives by a single nonlinear, ratio objective. Such conflicting objective could be, for example, the desire to cluster similar pixels together while limiting the total number of clusters.  Although studied for over a decade, researchers have suspected these problems to be NP-hard and hence have proposed approximate, continuous-based algorithms for their solution.

The author recast each problem as a single-parameter parametric integer program with monotone inequality constraints. For a fixed parameter, this integer problem can in turn be solved as a minimum-cut problem. Fortunately there are just a linear number of parameter break points to evaluate, and so the overall algorithm is fast in theory and effective in practice. In addition, the parametric approach provides information on the trade-off between the two conflicting objectives.  Besides solving these specific problems, this paper also sheds light on the difficulty of other related NP-hard problems.

In short, this paper provides a beautiful contribution to computer vision by taking a very innovative angle and demonstrating how to derive algorithms with strong performance guarantees and excellent experimental behavior.

2011 ICS Prize Committee:

• Sam Burer (chair)
• David Kelton
• Pascal Van Hentenryck

2010 ICS Prize

The 2010 ICS Prize was awarded to Jesús A. De Loera, Jon Lee, Peter N. Malkin, Susan Margulies, and Shmuel Onn for their papers:

• Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility Proceedings of the 21st International Symposium on Symbolic and Algebraic Computation (ISSAC 2008, Linz/Hagenberg, Austria), Association for Computing Machinery, (2008), 197-206,
• Expressing Combinatorial Optimization Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz Combinatorics, Probability and Computing, Volume 18, Issue 04, (2009), 551-582.

These two papers introduce a pioneering new approach for proving the optimality of solutions to combinatorial optimization problems. The approach begins by encoding the instance and an objective bound as a system of polynomial equations over a finite field. Then, using Hilbert's Nullstellensatz, the authors demonstrate the effectiveness of a computational method to certify the infeasibility of the polynomial system. The encoding is derived and analyzed for a number of problem classes, such as the k-coloring, stable set, longest cycle, largest planar subgraph, and minimum edge coloring problems. While the degree of the certifying polynomial could be exponentially large, the authors demonstrate that in many cases of interest the degree is low enough to allow for explicit, fast computations. The authors also develop a variety of computational enhancements, including computing over finite fields, exploiting symmetry, adding redundant equations, and applying alternative Nullstellensätze that allow them to solve 3-coloring problems significantly faster than existing methods.

 In this impressive work, the authors take up a mathematical machinery that seemed very unlikely to be useful in practice and turn it into a useful computational algorithm. This work is likely to stimulate additional research into computational polynomial methods, perhaps placing them on the same footing as polyhedral techniques for solving combinatorial optimization problems.

2010 ICS Prize Committee:

• Karen Aardal
• Sam Burer
• Jeff Linderoth
• Andreas Waechter (chair)

2009 ICS Prize

The 2009 ICS Prize was awarded to Andreas Waechter and Lorenz Biegler for their paper, "An Interior-Point Filter line-Search Algorithm for Large-Scale Nonlinear Programming" (Mathematical Programming 106(1), pp. 25--57, 2006).

Abstract: We present an algorithm for large-scale nonlinear continuous optimization, together with real-life applications, such as the tuning of transistors in digital circuits, modeling and design of chemical processes and optimal control of nonlinear dynamic systems. We will also present some recent developments of the algorithm, including parametric sensitivity of NLP solutions and the use of iterative linear solvers. An implementation of this algorithm ("Ipopt") is available as open source.

2009 ICS Prize Committee:

• S. Raghavan (Chair)
• Karen Aardal
• Michael Trick
• Stefan Voss

2008 ICS Prize

The 2008 ICS Prize was awarded to Robert W. Day and S. Raghavan for their paper, "Fair Payments for Efficient Allocations in Public Sector Combinatorial Auctions" [Management Science 53:9 (2007), 1389–1406].

This paper presents a new practical approach for combinatorial auctions, auctions in which bidders specify bids on bundles of items rather than on individual items. Combinatorial auctions have been applied when the value of a bundle of goods to a bidder is not merely the sum of the values of the individual items, such as in airplane slot allocations and spectrum allocations.

There is no universally agreed-upon method for determining the allocation of goods to bidders in combinatorial auctions, thus limiting their practical use. The Day-Raghavan paper developed an approach for determining winners of the auction as well as payments that satisfy two important properties:

• the payment method is incentive-compatible for bidders to bid their true values for bundles of goods, thus avoiding a need for extensive knowledge of the bidding of their competitors, and avoiding substantial underbidding.
• the payments are in the core; that is, there is no coalition of bidders that would be willing to pay more for any bundle of goods than the prices charged to the winning bidders.

This paper overcomes some key weaknesses Vickrey-Clarke-Groves (VCG) auction mechanism, which is an alternative mechanism that is compatible with bidders bidding their true values. First, the VCG mechanism can result in very low payments, thus making auctions impractical. Second, the VCG mechanism can result in payments that are not in the core, which would be perceived as unfair by any coalition who has bid more on items than they are sold for.

The authors present a model that achieves the two properties given above. They also provide a practical solution approach, using column generation, for finding pareto-optimal solutions. Their approach is practical for governmental combinatorial auctions and has already been used in the United Kingdom in auctions for allocating spectrum.

2007 ICS Prize Winners

The 2007 ICS Prize was awarded to J. Csirik, D. S. Johnson, C. Kenyon, J.B. Orlin, P.W. Shor, and R.R. Weber. 

2006 ICS Prize Winners

The 2006 ICS Prize was awarded to John Drew, Diane L. Evans, Andrew G. Glen, and Lawrence Leemis.

The winning team was awarded the Prize for their body of work in five papers:

• APPL: A Probability Programming Language
• The Distribution of Order Statistics for Discrete Random Variables with Applications to Bootstrapping
• Computing the Distribution of the Product of Two Continuous Random Variables
• Computing the Cumulative Distribution Function of the Kolmogorov-Smirnov Statistic
• A Generalized Univariate Change-of-Variable Transformation Technique

In awarding the prize the committee gave the following citation: "These papers form the core of an innovative body of work on computation in applied probability with operations research applications. The authors have introduced a probability programming language and demonstrated how to use it with applications at several corporations, government agencies, and academic institutions. These publications contribute significantly to computational probability and its practice at the interface of operations research and computer science."

2006 ICS Prize Committee:

• Gerald Brown (Chair)
• Michael Ball
• Pierre L'Ecuyer

2005 ICS Prize Winners

The 2005 ICS Prize was awarded to Zhiwei Fu (Fannie Mae and previously, University of Maryland), Bruce L. Golden, Shreevardhan Lele, S. Raghavan (all from the University of Maryland) and Edward A. Wasil (American University).

The winning team was awarded the Prize for their body of work in three papers:

• A Genetic Algorithm-Based Approach for Building Accurate Decision Trees, INFORMS Journal on Computing 15 (2003) 322.
• Genetically Engineered Decision Trees: Population Diversity Produces Smarter Trees, Operations Research 51 (2003) 894907.
• Diversification for Better Classification Trees, Computers & Operations Research (2005) in press.

In awarding the prize the committee gave the following citation: "This work describes innovative methods for constructing classification trees in very large data sets. Ideas from statistics and heuristic search are combined to produce methods that are fast, accurate, and of high quality as measured by several newly proposed performance measures. These methods are applicable to a variety of data mining problems of practical size, and represent a significant contribution to knowledge and practice at the interface of operations research and computer science."

2005 ICS Prize Committee:

• Robert Fourer (Chair)
• Gerald Brown
• Hanif Sherali

2004 ICS Prize Winners

Nikolaos V. Sahinidis and Mohit Tawarmalani for their contributions to the field of Nonlinear global optimization summarized in their book Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming, and embodied in the BARON software package

The work embodied in this book and the BARON software package comprises a path-breaking advance in the theory and computational practice of optimizing nonconvex nonlinear models. Mathematical programming methods have traditionally only been able to compute local optima of such models, and practitioners seeking global optima had to resort to a variety of heuristic and ad hoc techniques. This work, drawing on original contributions of the authors and the work of many other researchers, addresses the computation of provably global optima by bringing together a variety of mathematical programming techniques ranging from branch and bound to convex analysis. It thus unites a number of traditionally separate research areas in creating an enabling technology for new application fields. The book also includes interesting engineering applications, with computational results giving persuasive proof of the work's usefulness. Given the challenging nature of the models it addresses, the success of BARON is remarkable. Work of this nature opens up new applications for the future of mathematical programming.

2003 ICS Prize Winner

Ignacio Grossmann for his many contributions to Nonlinear Mixed Integer Programming and Process Design

Ignacio Grossmann has made fundamental contributions to the theory and practice of mixed integer nonlinear programming (MINLP). His pioneering paper with Marco Duran on the Outer Approximation (OA) decomposition algorithm showed that it dominated Generalized Benders Decomposition for a large and important class of MINLP's. He was instrumental in developing the DICOPT implementation of OA, coupling it to the GAMS modeling language, and extending its logic to deal with problems that are non-convex in the continuous variables. DICOPT is now one of the most widely used MINLP solvers, and is largely responsible for making MINLP a viable tool for practical problem solving.

Professor Grossmann has also made fundamental contributions in formulating industrially significant engineering design problems as optimization problems, with emphasis on the incorporation of logic-based modeling and algorithms. He has proposed useful measures of flexibility, and shown how to optimize flexible processes. He and his students developed ways to incorporate logical constraints into branch and bound logic which greatly speeded solution. His recent work on disjunctive programming and constraint programming maintains his high standards. In addition, he is widely recognized for his skills in recognizing and encouraging PhD students

2002 ICS Prize Winner

Pascal Van Hentenryck, Brown University, was awarded "The 2002 INFORMS Computing Society Prize for Research Excellence In The Interface Between Operations Research And Computer Science" for for his many contributions to The field of Constraint Programming and its integration into Operations Research. The prize was awarded at the National Meeting of INFORMS (Institute for Operations Research and the Management Sciences), held in San Jose, CA, USA.

Earlier

2001 Renato D.C. Monteiro, Yin Zhang
2000 Janos Pinter
1999 Yair Censor, Stavros A. Zenios
1998 Ding-Zhu Du, Frank K. Hwang
1997 Dmitri P. Bertsekas, John N. Tsitsiklis
1996 Warren Adams, Hanif Sherali
1995 John Forrest, Donald Goldfarb
1994 Fred Glover
1993 Robert Fourer, David Gay, Brian Kernighan
1992 Irvin Lustig, Roy Marsten, Nimrod Megiddo, David Shanno
1991 John Hooker
1988 Alex Meeraus
1987 Fred Glover, Darwin Klingman, Marcel Neuts
1986 Harvey Greenberg