Call for Nominations: 2012 ICS Prize

Deadline for nominations: July 31, 2012

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 award will be presented at the ICS Business Meeting that will take place during the INFORMS Annual Meeting in Phoenix, October 14--17, 2012.

The goals of the prize are:

• To promote the development of high-quality 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. Self-nominations are allowed but discouraged. All nominations should be made electronically to

 icsprize@mail.informs.org

All submissions will be acknowledged by the committee chair.

Hard-to-reproduce 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 e-mail indicating a hardcopy submission should be sent to
icsprize@mail.informs.org.

INFORMS Computing Society:

The ICS exists to support research and practice activity on the interface of operations research and computer science. The congenial and active organization of over 500 members welcomes members and their involvement in all aspects of the organization. See http://www.informs.org/Community/ICS for more information.

2012 ICS Prize Committee:

• Daniel Bienstock (Columbia University)
• Dorit Hochbaum (University of California, Berkeley)
• Pascal Van Hentenryck, Chair (NICTA)

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. 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 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