ICS Prize
ICS Prize
The INFORMS Computing Society (ICS) Prize is an annual award for the best English language paper or group of related papers dealing with the Operations Research/Computer Science interface. The award is accompanied by a certificate and a $1,000 honorarium. The 2015 award will be presented at the ICS Business Meeting that will take place during the INFORMS Annual Meeting in Philadelphia November 14, 2015.
The goals of the prize are:
 To promote the development of highquality work advancing the state of the art in the operations research/computer science interface;
 To publicize and reward the contributions of those authors/researchers who have advanced the state of the art; and
 To increase the visibility of excellent work in the field.
Conditions for eligibility:
 Published in the open literature;
 Pertinent to the interface of operations research and computer science;
 Written in English.
Application Process:
The nomination package should consist of a cover letter and a copy of each nominated work. The cover letter should provide the title, author's name, place and date of publication as well as a justification for the nomination. Selfnominations are allowed but discouraged. All nominations should be made electronically to
by the nomination deadline. All submissions will be acknowledged by the committee chair. Hardtoreproduce works, such as books, may be submitted in hard copy form to the mailing address below. In the case of hard copy submission, four copies of each item in the nomination packet should be submitted, and an email indicating a hardcopy submission should be sent to
2016 ICS Prize
Nominations will be accepted until midnight July 15, 2016. All submissions will be acknowledged by the committee chair. Hardtoreproduce works, such as books, may be submitted in hardcopy form to the mailing address below. In the case of hardcopy submission, three copies of each item in the nomination packet should be submitted to the committee chair and an email indicating a hardcopy submission should be sent to icsprize@mail.informs.org.
ICS Prize Awards Committee
 Jon Lee, University of Michigan
 Jeff Linderoth, University of WisconsinMadison

Nick Sahinidis, Carnegie Mellon University (Chair)John E. Swearingen Professor
Dept. of Chemical Engineering
Carnegie Mellon University
5000 Forbes Avenue
Pittsburgh PA 15213
http://archimedes.cheme.cmu.edu/
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 MixedInteger Programming: Set Convexification", Mathematical Programming, 104, pp. 120, 2005.
 Suvrajeet Sen, Hanif D. Sherali, "Decomposition with BranchandCut Approaches for TwoStage Stochastic MixedInteger Programming", Mathematical Programming, 106, pp. 203223, 2006.
 Lewis Ntaimo, Suvrajeet Sen, "The Million Variable 'March' for Stochastic Combinatorial Optimization", Journal of Global Optimization, 32, pp. 385400, 2005.
 Lewis Ntaimo, Suvrajeet Sen, "A Comparative Study of Decomposition Algorithms for Stochastic Combinatorial Optimization", Computational Optimization and Applications, 40, pp. 299319, 2008.
 Dinakar Gade, Simge Küçükyavuz, Suvrajeet Sen, "Decomposition Algorithms with Parametric Gomory Cuts for TwoStage Stochastic Integer Programs", Mathematical Programming, 144, pp. 3964, 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 stateoftheart 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 (University of Toronto), Chair
 Jeff Linderoth (University of WisconsinMadison)
 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:147178, 2011.
 Constraint Orbital Branching, IPCO 2008: Lecture Notes in Computer Science, Vol. 5035, Springer, 225239, 2008.
 Solving Large Steiner Triple Covering Problems, Operations Research Letters, 39:127131, 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 wellknown, produces large branchandbound 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 highthroughput 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 (Columbia University), Chair
 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 workload 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. NPhardness 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 sosconvex. 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 sosconvexity. 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 4degree polynomial is convex to be NPhard in the strong sense. The implication of this result is that unless P=NP, there cannot be a polynomial time or even pseudopolynomial 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 wellknown 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 Newtontype 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 NPhard.
Paper [2] shows the first known example of a convex polynomial that is not sosconvex. Such polynomials are generally not easy to construct. The authors resort to computational methods, involving semidefinite 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 sosconvexity 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 889898, 2010).
This paper presents an efficient, highly novel approach for solving a group of wellknown combinatorial optimization problems arising in computer vision and image analysis, including the ratioregions problem and a variant of the normalizedcut 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 NPhard and hence have proposed approximate, continuousbased algorithms for their solution.
The author recast each problem as a singleparameter parametric integer program with monotone inequality constraints. For a fixed parameter, this integer problem can in turn be solved as a minimumcut 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 tradeoff between the two conflicting objectives. Besides solving these specific problems, this paper also sheds light on the difficulty of other related NPhard 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), 197206,
 Expressing Combinatorial Optimization Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz Combinatorics, Probability and Computing, Volume 18, Issue 04, (2009), 551582.
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 kcoloring, 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 3coloring 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 InteriorPoint Filter lineSearch Algorithm for LargeScale Nonlinear Programming" (Mathematical Programming 106(1), pp. 2557, 2006).
Abstract: We present an algorithm for largescale nonlinear continuous optimization, together with reallife 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 Eﬃcient 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 agreedupon method for determining the allocation of goods to bidders in combinatorial auctions, thus limiting their practical use. The DayRaghavan paper developed an approach for determining winners of the auction as well as payments that satisfy two important properties:
 the payment method is incentivecompatible 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 VickreyClarkeGroves (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 paretooptimal 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. Award
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 KolmogorovSmirnov Statistic
 A Generalized Univariate ChangeofVariable 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 AlgorithmBased 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 MixedInteger Nonlinear Programming, and embodied in the BARON software package
The work embodied in this book and the BARON software package comprises a pathbreaking 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 nonconvex 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 logicbased 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 DingZhu 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