About me

I am a PhD student in the Computer Science Department at the University of British Columbia, jointly supervised by Kevin Leyton-Brown and Holger Hoos. I am affiliated with the Laboratory for Computational Intelligence (LCI) and the Bioinformatics and Empirical & Theoretical Algorithmics (BETA) Laboratory. I hold a BSc from Queen's University (2012). I study problems in empirical algorithms, with a focus on applying machine learning techniques towards solving NP-hard problems. More specifically, I study the generation of algorithm portfolios through algorithm configuration and algorithm selection. Two areas which have produced significant performance gains on computationally hard problems.

Recent News

Research

My research area is Empirical Algorithmics. This field has arisen out of the inadequency of theoretical analysis for important algorithmic problems. Often, practical algorithm problems are "messy" and difficult to clearly specify, making current theoretical tools difficult to apply. Empirical algorithmics can be used as an alternative in such cases through running computational experiments and observing algorithm behaviour, facilitating algorithm design and understanding. Some "computer scientists" have an identity crisis with being considered a "scientist". Empirical algorithms is certainly one subfield that puts the "science" in "computer science".

One area of practical importance where theoretical tools are very "immature" is NP-hard problems, despite being well studied. My main research focus is using machine learning techniques to improve empirical performance for solving NP-hard problems for important benchmarks. My work is divided between two subfields: Algorithm Selection and Algorithm Configuration.

Algorithm Selection

For many prominent NP-hard problems (i.e. SAT), practitioners often have access to many solvers for their particular problem and must make decisions about which solver(s) to run. The notion of portfolio-based algorithm selection was introduced as a way to exploit multiple uncorrelated algorithms in practice by combining their strengths. In the model-based algorithm selection approach, a model is learned to map informative instance features to choices of algorithms and the model is queried online to select solvers for execution on a per-instance basis. There has been much research on portfolio-based algorithm selectors, and state-of-the art approaches achieve notable performance gains over their component solvers.

I have contributed to our lab's portfolio-based algorithm selector: SATzilla, which has been the recipient of several awards from past SAT competitions. Since I joined the project, we won the 2015 ICON challenge. Recently we pointed out potential bias in analyzing performance of algorithm selectors. Currently, I am thinking about what properties allow algorithm selection to be useful (i.e. machine learning models, features, instance, solvers, etc.) and the deeper question about why algorithm algorithm selection works at all. While the practical benefits are clear, there is little work on understanding why algorithm selection is as successful as it is.

Algorithm Configuration for Portfolios

Algorithms in practice are often built with a set of parameters that can be tuned to change behaviour. In algorithm configuration, these parameters are automatically tuned to optimize some objective (i.e. aggregate running time over set of problem instances). But with access to parallel resources, many sets of parameters can be run in parallel or selected amongst using portfolio-based algorithm selectors. I am working on improving configuration of "sets" of complementary configurations for use in portfolios. Specifically, I am working to improve upon the already well-known Hydra project.

Publications

  • Chris Cameron, Holger H. Hoos, Kevin Leyton-Brown
    Bias in Algorithm Portfolio Performance Evaluation
    International Joint Conference on Artificial Intelligence (IJCAI), 2016.
    To appear. [pdf]

Education

2008-2012 BSc. Mining Engineering, Queen's University
2012-2014 BSc. (Incomplete) Computer Science, University of British Columbia
2014-2019 (expected) PhD Computer Science, University of British Columbia

Recent Employment

2014-Present, Graduate Research Assistant , University of British Columbia
See Research above.
2014, Undergraduate Research Assistant (NSERC USRA), University of British Columbia
Auction simulation for upcoming FCC auction.
Software development on SATzilla project.

2013-2014, Undergraduate Teaching Assistant , University of British Columbia
APSC-160: Introduction to Computation in Engineering Design, CPSC-261: Basics of Computer Systems
2013, Undergraduate Research Assistant , University of British Columbia
User interface to facilitate communication between robotic arms in bilateral teleoperation.
2012, Undergraduate Research Assistant , Queen's University
Computer simulation study of impact of travel-time variability on dispatch efficiency in open-pit mines.