Institution: Brown University
The dawn of the new century casts light on three dramatic economic challenges that will determine our future as a society: demography, globalization, and shortage of natural resources. Today we need to develop the technology that will allow our children to maintain our standard of living. Therefore, we need to find ways to increase our economical efficiency. Computer science can play a decisive role when facing this challenge. After more than 60 years of research, algorithmic computer science can offer a lot to help saving. However, the main impact of computational optimization support is currently limited to large companies in few core application areas such as the transportation industry. Specialized algorithmic solutions have shown to be extremely successful in these domains. While the algorithmic technologies that were developed are by no means specific to the current areas of application, the main obstacle for a broader realization of their vast potential is largely due to the lacking ease of use. Therefore, the main goal of the Cornflower Project is to develop techniques that allow inexperienced users to exploit optimization power efficiently.
Intellectual Merits: Optimization techniques have been developed in three historically separate research areas: constraint programming, operations research, and algorithm theory. While the main focus of the project is to provide a high level of automization and algorithms that can be hooked to intuitive modeling primitives that facilitate the use of intelligent optimization support, we do not stop at the boundaries of traditional research areas. Instead, we integrate and hybridize ideas developed in different communities in order to provide easily accessible high performance optimization technology. Particularly, we focus on the development of high-level constraints that allow users to model their problems as conjunctions of intuitive substructures and provide hybrid methods for their efficient combination. Moreover, we develop automization techniques for the handling of symmetries that can be the cause of severe inefficiencies when handled poorly.
Broader Impact: The main goal of the Cornflower project is to solve the algorithmic problems that arise in the context of optimization driven decision support systems that are intuitive to use and that provide a high level of automization. By making algorithms and methods publicly available in the Cornflower Library, the project contributes to widening the access to computational decision support. Our goal to broaden the accessibility of computational decision support while breaking the barriers between theoretical and practical computer science goes hand in hand with the educational goals of the project. Optimization techniques play an ever more important role for many other CS disciplines. By developing optimization courses that integrate methods from various research areas, Cornflower helps to educate the next generation of experts in combinatorial algorithms, while students moving on to other disciplines take away a sound understanding how to tackle combinatorial problems and how to utilize standard solvers for their own purposes. Attracting both students who are mainly interested in technical methodology as well as those who are primarily attracted to specific applications is also a promising approach to broadening participation in science at large. Through the outreach program Artemis, a five-week summer program for high-school girls, young are encouraged women to pursue careers in science and engineering.
The Cornflower Project "A frugal, undemanding plant that thrives under modest circumstances" In 2008, IBM announced its Smarter Planet initiative, and NSF funded the Institute for Computational Sustainability through its Exhibitions in Computing program. Two years earlier, in 2006, NSF granted a career grant that shares the same vision as those two high-profile initiatives: To exploit computational power for intelligent decision support to help an aging society sustain its standard of living while facing global competition and limited economic and natural resources. The symbol for this effort became a frugal, undemanding plant that thrives under modest circumstances, and the project was coined the Cornflower Project. "The computer needs to be told what the problem actually is" The focus of the Cornflower Project is to make it easier for non-experts to exploit computers to make smarter decisions. There are established tools that can provide descriptive, predictive, and prescriptive analytics. The first obstacle that users of these systems face is that any real-world problem needs to be modeled before the tools can be invoked. That is, the computer needs to be told what the problem actually is, and the way how a problem is formulated has tremendous effect on the computer's ability to provide solutions efficiently. The second obstacle is that decision support systems have parameters that also greatly affect solution efficiency. These parameters need to be tuned before a system performs well. Cornflower addressed these two issues on multiple levels: By designing provably efficient algorithms that allow the computer to reason about models that are intuitive to formulate for non-experts. By developing algorithms that search more efficiently for solutions, even when the given model is not perfect. By introducing new methods to cope with problem symmetry which can otherwise cause an analytics tool to perform very poorly. And by proposing a new tool for tuning parameters of analytics tools automatically. "A simple, provably optimal formula for binary search" Most results of this four year long research project, published in over 30 peer-reviewed research papers at international conferences and journals, are beyond the scope of a short summary. To give a flavor of this research, however, consider the children's game "Guess my number:" One child thinks of a number between 1 and 100. The other must guess the number in as few trials as possible. When the guess is off, the first child must tell the guesser whether the number is higher or lower. Computers frequently play this game when tackling optimization problems by repeatedly considering the question: "Is there a feasible solution that has at most cost 'X'?" The optimal strategy for the guesser is, of course, to split the search interval in the middle. This way, with each guess the remaining search interval is guaranteed to halve. In our game, the guesser should guess 50. No matter what the correct number is, the remaining search interval contains at most 50 numbers (1 to 49 or 51 to 100). The problem for the computer is that proving that there is no solution with cost lower or equal 'X' is usually much harder than finding one, if it exists. Serdar Kadioglu and Meinolf Sellmann have found a simple, provably optimal formula for binary search for the case where a trial, when it comes back negative, incurs a 'c'-times higher costs than positive trials. Namely, the interval should be split at balance 'a' where 'a' solves the equation ac + a = 1. In classic binary search where 'c' is one, the formula tells us to set a=0.5: we split the interval exactly in the middle. As the cost for negative trials becomes larger and 'c' grows, however, according to the formula 'a' gets closer and closer to one and trials become more and more defensive as guesses are made further and further to the higher end of the search interval. Kadioglu and Sellmann prove rigorously that their formula leads to minimal search costs both in the worst and the average-case. Moreover, they demonstrate significant performance gains in practice. The technique was quickly picked up by industrial analytics providers such as IBM who use these "skewed" binary searches to faster provide optimal solutions for their clients. "They continue working together" The Cornflower team has dissolved after the three researchers have moved on to take positions at Oracle, the Cork Constraint Computation Centre, and IBM Research. They continue working together, however. In collaboration with Ashish Sabharwal and Horst Samulowitz at IBM, Yuri Malitsky and Sellmann recently demonstrated the effectiveness of their algorithm tuning and portfolio methodology by winning two gold medals at the international SAT Competition. It is still a long way before the vision of the Cornflower, Computational Sustainability, and Smarter Planet initiatives are realized. The quest for providing analytics solutions for non-experts continues.
