Programming by Optimisation (PbO)

Premature commitment to design choices during software development often leads to loss of performance and limited flexibility. Programming by Optimization (PbO) is a design paradigm that aims to avoid such premature design choices and to actively develop promising alternatives for parts of the design. Rather than build a single program for a given purpose, software developers specify a rich and potentially large design space of programs. From this specification, programs that perform well in a given use context are generated automatically through powerful optimization techniques. PbO allows human experts to focus on the creative task of imagining possible mechanisms for solving given problems or subproblems, while the tedious job of determining what works best in a given use context is performed automatically, substituting human labor with computation. Furthermore, using PbO, per-instance algorithm selectors and parallel algorithm portfolios can be obtained from the same sequential source.

PbO can be adopted to varying degrees, which can be roughly grouped into 5 levels of PbO. To learn more about PbO, you may want to read the 2012 article by Holger H. Hoos. If you have difficulties accessing this, you could look at an earlier technical report, which is superseded by the CACM article.

The team working on various aspects of PbO at UBC includes Holger H. Hoos, Kevin Leyton-Brown, Frank Hutter, Lin Xu, Chris Fawcett, James Styles, Sam Bayless, Quinn Hsu and Steve Ramage. Former team members include Dave Tompkins, Chris Nell, Ashiqur KudaBukhsh and Rui Zhao. Important contributions have been made by many of our collaborators at UBC and elsewhere, and many other groups have published related work (see publications below).

Programming by Optimization.
Holger H. Hoos - Communications of the ACM 55(2), pp. 70-80, February 2012.
[comprehensive introduction to the PbO paradigm; the appendix contains the current description of the generic PbO programming language extension]
[access online version] [access online appendix] (This article supersedes the earlier technical report, in which PbO was first introduced).
Automated Algorithm Configuration and Parameter Tuning.
Holger H. Hoos - Autonomous Search (edited by Y. Hamadi, E. Monfroy and F. Saubion), Chapter 3, pp. 37-71, Springer Verlag, 2012.
[computer-aided algorithm design, empirical algorithmics]
(PDF file - 236k; preprint)
Automatically Configuring Algorithms for Scaling Performance.
James Styles, Holger Hoos, and Martin Müller - Proceedings of the 6th International Conference on Learning and Intelligent Optimization (LION 6), 2012.
[automated algorithm configurators, configurator protocols, travelling salesman problem, TSP, Go, mixed integer programming, MIP]
(get PDF file - 328k)
[View Full List]

C Examples
- Hello World
- starT
- MinElement
- D-ary Heap
- Discount
C++ Examples
- Hello World
- starT
- MinElement
- D-ary Heap
- Discount
Java Examples
- Hello World
- StarT
- MinElement
- D-ary Heap
- Discount

Note: Further examples will be released soon.

ParamILS (automated algorithm configurator)
SMAC (automated algorithm configurator)
irace (automated algorithm configurator)
PbO-C weaver (prototype, version 1.0.00, under active development)
PbO-C++ weaver (prototype, version 1.0.00, under active development)
PbO-Java weaver (prototype, version 1.0.00, under active development)

PbO Eclipse Plugin install instructions (this plugin provides syntax highlighting, code folding and PbO construct outlining, as well as support for building and debugging PbO C/C++ projects)
Sources for the plugin can be found here

Note: Configurators are reasonably stable research software; weavers and the Eclipse plugin are early-stage, limited functionality prototypes (expect frequent updates)

Q: Does PbO actually work?

A: Absolutely. The Literature section of this page provides many references to work clearly demonstrating the viability and benefits of the approach. The 2012 CACM article by Holger Hoos summarises several of the most successful applications, but there are many more. For example, using IBM's commercial CPLEX optimizer and depending on the type of mixed integer programming problem to be solved, we have achieved speedups of between factors of 2 and 500.
Q: Which citation should I use when referring in my scientific work to PbO?

A: We kindly ask you to cite the 2012 CACM article by Holger Hoos, a bib file for which can be found here. You should also include an appropriate citation for the design optimiser you have used.
Q: Is PbO restricted to certain programming languages?

A: No. In principle, PbO can be adopted in any programming language. Design optimization can be performed by means of an algorithm configurator, which can work with any executable. We believe that generic PbO language extensions (as described here are useful to support design space specifications (exposing parameters and declaring choices), and we are working on weavers, which analyse PbO-enriched sources and translate them into a base language, for C, C++ and Java. Prototypes are under active development and can be accessed from this web page (see Tools section). Examples illustrating the use of the generic PbO language constructs can also be found on this page (see Examples section).
Q: What tools do I need to conduct PbO-based software development?

A: Minimally, all that is needed, in addition to an existing development environment, is an automated algorithm configurator, of which several are available in the form of research software (see Tools section of this web page). We are actively developing support for PbO-enriched programming languages, specifically PbO-C, PbO-C++ and PbO-Java. Preliminary versions of these tools, with limited functionality, are available from this web page (see Tools section). We are also working on support for the Eclipse IDE.
Q: Which design optimiser (algorithm configurator) should I use?

A: Currently, we recommend you use the FocusedILS variant of ParamILS, but this recommendation may change in the near future, as other development of other configurators progresses. We recommend you use at least 10 independent runs of ParamILS (these can, but do not have to be performed in parallel), and select from these the one with the best performance as measured on a validation set of inputs. When you use ParamILS to optimise running time, we recommend to use a training set I of inputs, cutoff time t and overall configuration time (per independent run) T, such that
1. for at least 75% of the inputs in I, the default configuration of your software when run on a single input, completes within time t;
2. the overall time budget T is at least 200, better 1000, times t.
Q: What is the PbO C/C++ Eclipse plugin?

A: The PbO C/C++ Eclipse plugin is an Eclipse plugin built based on the Eclipse CDT tools. It supports developers of PbO C and PbO C++ projects by providing syntax highlighting and code folding for PbO constructs, as well as providing a view for all defined PbO constructs in a project. The plugin also supports weaving and debugging PbO C/C++ projects from with the Eclipse IDE. Check out information on the plugin here.
Q: I'd like to help develop tools for PbO and have them listed on this page - whom should I contact about this?

A: Contributors are always welcome! To avoid duplication of effort, please contact Holger Hoos, ideally, before you invest substantial development time into anything.
Q: PbO is the molecular formula for lead(II) oxide - is this a coincidence?

A: Great that someone noticed! No, that is quite deliberate. Lead(II) oxide has important industrial (and artistic) applications; in particular, it is used in the production of so-called lead crystal, a type of glass with attractive optical properties: it has a higher refractive index and dispersion than normal glass, and therefore more "sparkle". It is also makes it easier for glass makers to manufacture perfectly clear, flawless glass objects. If you have ever enjoyed wine from a (higher end) Riedel glass, or admired the sparkle of a piece of Swarovski jewelry (or, perhaps, that of the infamous chandelier from Phantom of the Opera), you already have an appreciation for lead oxide. If such things hold no attraction for you, the computing science version of PbO might still add some sparkle to your software.