2009 Beale — OrchardHays Prize Citation
Tobias Achtergerg,
"SCIP: Solving constraint integer programs",
Mathematical Programming Computation, 1 (2009), pp. 141.
This Prize is sponsored by the Society in memory of Martin Beale and William OrchardHays,
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 highquality 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. 141, 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,
mixedinteger 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 branchandbound 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
coworkers, 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 mixedinteger 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
branchcutandprice applications by implementing "plugins" for the
problemspecific routines. Finally, the computational results in the paper show that the
approach developed by the author outperforms current stateoftheart techniques for
proving the validity of properties on circuits containing arithmetic.
