2009 Beale — Orchard-Hays Prize Citation

Tobias Achtergerg,
"SCIP: Solving constraint integer programs",
Mathematical Programming Computation, 1 (2009), pp. 1-41.

This Prize is sponsored by the Society in memory of Martin Beale and William Orchard-Hays, pioneers in computational mathematical programming. The Prize is given for excellence in any aspect of computational mathematical programming. "Computational mathematical programming" includes the development of high-quality mathematical programming algorithms and software, the experimental evaluation of mathematical programming algorithms, and the development of new methods for the empirical testing of mathematical programming techniques.

Selecting a prize winner for 2009 was challenging since we received thirteen exceptional nominations. The nominated works spanned a broad spectrum of areas, including linear programming, semidefinite programming, nonlinear programming, integer programming, stochastic programming, and global optimization. In reflection of the Mathematical Programming Society's international character, these nominations originated from ten different countries.

The 2009 Prize was awarded to Tobias Achterberg for his paper "SCIP: Solving constrained integer programs", Mathematical Programming Computation, 1 (2009), pp. 1-41, which is the first paper to appear in the Society's new journal Mathematical Programming Computation. This paper describes an innovative paradigm to integrate modeling capabilities and solution techniques from constraint programming, mixed-integer programming, and satisfiability. These techniques are carefully integrated after extensive computational experimentation that resulted in the software SCIP, which consists of more than 250,000 lines of code, all written by the author himself, and which is the focus of the paper. The source code of SCIP is available free for academic use. Compared to previous branch-and-bound systems, SCIP achieves a tighter integration of the aforementioned modeling and solution paradigms. In addition, it implements several novel algorithmic constructs that have been developed in recent papers by the author and co-workers, including branching rule scores, cutting plane handling, and conflict analysis. It is truly remarkable that SCIP has performed with times that are within a modest factor of those for the best commercial codes for mixed-integer programs. This fact alone is one of the best confirmations of the quality of the work done by the author. An additional strength of SCIP is the ease with which researchers can create branch-cut-and-price applications by implementing "plug-ins" for the problem-specific routines. Finally, the computational results in the paper show that the approach developed by the author outperforms current state-of-the-art techniques for proving the validity of properties on circuits containing arithmetic.