I have moved to the University of British Columbia, please see my new homepage.
Lars Kotthoff

Lars Kotthoff

lars.kotthoff at insight-centre.org

INSIGHT Centre for Data Analytics
Cork Constraint Computation Centre
University College Cork
Western Gateway Building
Cork, Ireland


News

I gave an invited talk at the University of Münster (slides).

Our paper on algorithm selection for the TSP has been accepted at LION 9 (slides).

Our paper on our experiences with recomputation.org has been accepted at Recomputability 2014.

I gave an invited talk at the University of Bologna (slides).

I attended Dagstuhl seminar 14411 on Constraints, Optimization and Data (talk slides).

I was visiting Frank Hutter's group at the University of Freiburg.

I attended the COSEAL workshop 2014 (slides of talk with Bernd Bischl).

I was awarded a research grant from Microsoft Azure worth $40,000 (with Bernd Bischl and Marius Lindauer).

The slides for my talk at the ICON summer school are available here.

The slides for my invited talk at MetaSel 2014 are available here.

Our paper on a framework for large-scale eScience applications has been accepted at eScience 2014.

I am invited speaker at the ICON summer school.

I am invited speaker at the Summer School on Experimental Methodology in Computational Science Research.

I was visiting the University of Munich.

I was attending the Samos Summit on ICT-enabled Governance.

I was visting the University of British Columbia.

Our paper on discriminating instance generation for automated constraint model selection has been accepted at CP 2014.

Our paper on integrating optimisation and agent-based modelling has been accepted at ECMS 2014.

I have been awarded an Irish Research Council New Foundations award.

I am co-organizing (with Pavel Brazdil, Carlos Soares, and Joaquin Vanschoren) the MetaSel 2014 workshop at ECAI 2014.

I am on the programme committee for the CP 2014 doctoral consortium.

I am co-organizing (with Siegfried Nijssen) the master class for CPAIOR 2014.

I am co-organizing (with Georgiana Ifrim and Barry O'Sullivan) the CoCoMiLe 2014 workshop at ECAI 2014.

Lecture materials for CS6405 are here.

I'll be presenting (with Ian Gent) a tutorial on recomputation at ECAI 2014.

Our Proteus paper has been accepted at CPAIOR 2014.

My survey paper on algorithm selection was accepted by AI Magazine, the flagship publication of AAAI.

Two of my papers (on Ranking Algorithms by Performance and Algorithm Configuration in the Cloud) were accepted at the Learning and Intelligent OptimizatioN Conference.

I am co-teaching CS6405 this semester (with Yuri Malitsky).

Ian Gent and I have been awarded a Windows Azure grant worth $40,000 for our efforts to make experiments recomputable (see http://recomputation.org/).

I was visting the University of Surrey.

The slides for our tutorial on recomputation are now online. Also check out the experiments we made recomputable for this here.

I am workshop chair for CPAIOR 2014.

I have secured a travel grant worth €1,500 from Enterprise Ireland to attend ICT 2013.

Our paper on Lazy Branching for Constraint Satisfaction was accepted for publication at ICTAI 2013.

The slides for our tutorial on algorithm selection and configuration at IJCAI 2013 are now available here.

Our paper on Automated Symmetry Breaking and Model Selection in Conjure was accepted at CP 2013.

I am co-presenting (with Ian Gent) a tutorial on replication and recomputation in scientific experiments at CP 2013.

I have released the LLAMA R package to simplify common algorithm selection tasks. Please check it out and let me know what you think!

I have proposed a QA site for combinatorial search and optimization on the stackexchange network.

I was visiting the University of Pisa.

I am attending the ICON project review meeting in Leuven.

I am on the programme committee for the IJCAI 2013 doctoral consortium.

I was co-presenting a tutorial on algorithm selection and configuration at IJCAI 2013. The tutorial slides are available here.

I was co-presenting a tutorial on algorithm selection and configuration at AAAI 2013.

I am on the programme committee for SARA 2013.

I am a co-organizer for the Second workshop on COmbining COnstraint solving with MIning and LEarning (COCOMILE).

I am on the programme committee for CP 2013.

I am on the programme committee for IJCAI 2013.

I reviewed for CPAIOR 2013.

I am attending the ICON project meeting in Pisa.

I am attending CP 2012 where I will be presenting our semigroups paper (PDF slides) and two posters.

Awards

I have won an EPSRC Doctoral Prize fellowship.

I have given invited talks at IJCAI 11, the Oxford configuration workshop 2012, the Summer School on Experimental Methodology in Computational Science Research, MetaSel 2014, the ICON summer school, Dagstuhl seminar 14411, and the University of Bologna.

I have won the Best Student Paper Prize at the Symposium on Combinatorial Search 2011.

I have secured research grants from Amazon Web Services and Rackspace totalling approximately $23,000. In addition, I have been awarded a research grant from Microsoft Azure worth $40,000.

I have secured a travel grant worth €1,500 from Enterprise Ireland and a "New Foundations" award from the Irish Research Council.

Recent and selected publications

Lars Kotthoff, Pascal Kerschke, Holger Hoos, Heike Trautmann
Improving the State of the Art in Inexact TSP Solving using Per-Instance Algorithm Selection
Learning and Intelligent OptimizatioN 9, Lille, France, January 2015
preprint PDF, bibtex, abstract
We investigate per-instance algorithm selection techniques for solving the Travelling Salesman Problem (TSP), based on the two state-of-the-art inexact TSP solvers, LKH and EAX. Our comprehensive experiments demonstrate that the solvers exhibit complementary performance across a diverse set of instances, and the potential for improving the state of the art by selecting between them is significant. Using TSP features from the literature as well as a set of novel features, we show that we can capitalise on this potential by building an efficient selector that achieves significant performance improvements in practice. Our selectors represent a significant improvement in the state-of-the-art in inexact TSP solving, and hence in the ability to find optimal solutions (without proof of optimality) for challenging TSP instances in practice.
Ian P. Gent, Lars Kotthoff
Recomputation.org: Experience of Its First Year and Lessons Learned
Recomputability 2014, London, UK, December 2014
preprint PDF, bibtex, abstract
We founded recomputation.org about 18 months ago as we write. The site is intended to serve as a repository for computational experiments, embodied in virtual machines so that they can be recomputed at will by other researchers. We reflect in this paper on those aspects of recomputation.org that have worked well, those that have worked less well, and to what extent our views have changed on reproducibility in computational science.
Nic Wilson, Lars Kotthoff
Taking into Account Expected Future Bids in ePolicy Optimisation Problem
Technical report, Insight Centre for Data Analytics, University College Cork
PDF
Thomas W. Kelsey, Martin McCaffery, Lars Kotthoff
Web-scale distributed eScience AI search across disconnected and heterogeneous infrastructures
10th IEEE International Conference on eScience, Guarujá, Brazil, October 2014
preprint PDF, bibtex, abstract
We present a robust and generic framework for web-scale distributed e-Science Artificial Intelligence search. Our validation approach is to distribute constraint satisfaction problems that require perfect accuracy to 10, 12 and 15 digits. By checking solutions obtained using the framework against known results, we can ensure that no errors, duplications nor omissions are introduced. Unlike other approaches, we do not require dedicated machines, homogeneous infrastructure or the ability to communicate between nodes. We give special consideration to the robustness of the framework, minimising the loss of effort even after a total loss of infrastructure, and allowing easy verification of every step of the distribution process. The unique challenges our framework tackles are related to the combinatorial explosion of the space that contains the possible solutions, and the robustness of long-running computations. Not only is the time required to finish the computations unknown, but also the resource requirements may change during the course of the computation. We demonstrate the applicability of our framework by using it to solve challenging problems using two separate large-scale distribution paradigms. The results show that our approach scales to e-Science computations of a size that would have been impossible to tackle just a decade ago.
Bilal Hussain, Ian P. Gent, Christopher Jefferson, Lars Kotthoff, Ian Miguel, Glenna F. Nightingale, Peter Nightingale
Discriminating Instance Generation for Automated Constraint Model Selection
20th International Conference on Principles and Practice of Constraint Programming, Lyon, France, September 2014
preprint PDF, bibtex, abstract
One approach to automated constraint modelling is to generate, and then select from, a set of candidate models. This method is used by the automated modelling system CONJURE. To select a preferred model or set of models for a problem class from the candidates, CONJURE uses a set of training instances drawn from the target class. It is important that the training instances are discriminating. If all models solve a given instance in a trivial amount of time, or if no models solve it in the time available, then the instance is not useful for model selection. This paper addresses the task of generating small sets of discriminating training instances automatically. The instance space is determined by the parameters of the associated problem class. We develop a number of methods of finding parameter configurations that give discriminating training instances, some of them leveraging existing parameter-tuning techniques. Our experimental results confirm the success of our approach in reducing a large set of input models to a small set that we can expect to perform well for the given problem class.
Peter George Johnson, Tina Balke, Lars Kotthoff
Integrating optimisation and agent-based modelling
28th European Conference on Modelling & Simulation, Brescia, Italy, May 2014
preprint PDF, bibtex, abstract
A key strength of agent-based modelling is the ability to explore the upward-causation of micro-dynamics on the macro-level behaviour of a system. However, in policy contexts, it is also important to be able to represent downward-causation from the macro and meso-levels to the micro, and to represent decision-making at the macro level (i.e., by governments) in a sensible way. Though we cannot model political processes easily, we can try to optimise decisions given certain stated goals (e.g., minimum cost, or maximum impact). Optimisation offers one potential method to model macro-level decisions in this way. This paper presents the implementation of an integration of optimisation with agent-based modelling for the example of an auction scenario of government support for the installation of photovoltaic solar panels by households. Auction type scenarios of this kind, in which large groups of individuals or organisations make bids for subsidies or contracts from government, are common in many policy domains.
Thomas W. Kelsey, Lars Kotthoff, Christopher A. Jefferson, Stephen A. Linton, Ian Miguel, Peter Nightingale, Ian P. Gent
Qualitative Modelling via Constraint Programming
Constraints, 2014 (to appear)
preprint PDF, bibtex, abstract
Qualitative modelling is a technique integrating the fields of theoretical computer science, artificial intelligence and the physical and biological sciences. The aim is to be able to model the behaviour of systems without estimating parameter values and fixing the exact quantitative dynamics. Traditional applications are the study of the dynamics of physical and biological systems at a higher level of abstraction than that obtained by estimation of numerical parameter values for a fixed quantitative model. Qualitative modelling has been studied and implemented to varying degrees of sophistication in Petri nets, process calculi and constraint programming. In this paper we reflect on the strengths and weaknesses of existing frameworks, we demonstrate how recent advances in constraint programming can be leveraged to produce high quality qualitative models, and we describe the advances in theory and technology that would be needed to make constraint programming the best option for scientific investigation in the broadest sense.
Barry Hurley, Lars Kotthoff, Yuri Malitsky, Barry O'Sullivan
Proteus: A Hierarchical Portfolio of Solvers and Transformations
Eleventh International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) techniques in Constraint Programming, Cork, Ireland, May 2014
preprint PDF, bibtex, abstract
In recent years, portfolio approaches to solving SAT problems and CSPs have become increasingly common. There are also a number of different encodings for representing CSPs as SAT instances. In this paper, we leverage advances in both SAT and CSP solving to present a novel hierarchical portfolio-based approach to CSP solving, which we call Proteus, that does not rely purely on CSP solvers. Instead, it may decide that it is best to encode a CSP problem instance into SAT, selecting an appropriate encoding and a corresponding SAT solver. Our experimental evaluation uses an instance of Proteus that involved four CSP solvers, three SAT encodings, and six SAT solvers, evaluated on the most challenging problem instances from the CSP solver competitions, involving global and intensional constraints. We demonstrate that significant performance improvements can be achieved by Proteus obtained by exploiting alternative view-point and solvers for combinatorial problem-solving.
Lars Kotthoff
Algorithm Selection for Combinatorial Search Problems: A Survey
AI Magazine, 2014
preprint PDF, bibtex, abstract
The Algorithm Selection Problem is concerned with selecting the best algorithm to solve a given problem instance on a case-by-case basis. It has become especially relevant in the last decade, with researchers increasingly investigating how to identify the most suitable existing algorithm for solving a problem instance instead of developing new algorithms. This survey presents an overview of this work focusing on the contributions made in the area of combinatorial search problems, where algorithm selection techniques have achieved significant performance improvements. We unify and organise the vast literature according to criteria that determine algorithm selection systems in practice. The comprehensive classification of approaches identifies and analyses the different directions from which algorithm selection has been approached. This paper contrasts and compares different methods for solving the problem as well as ways of using these solutions.
Lars Kotthoff
Ranking Algorithms by Performance
Learning and Intelligent OptimizatioN 8, Gainesville, USA, February 2014
PDF, slides, bibtex
Daniel Geschwender, Frank Hutter, Lars Kotthoff, Yuri Malitsky, Holger H. Hoos, Kevin Leyton-Brown
Algorithm Configuration in the Cloud: A Feasibility Study
Learning and Intelligent OptimizatioN 8, Gainesville, USA, February 2014
PDF, slides, bibtex
Lars Kotthoff
Ranking Algorithms by Performance, November 2013
PDF, bibtex, abstract
A common way of doing algorithm selection is to train a machine learning model and predict the best algorithm from a portfolio to solve a particular problem. While this method has been highly successful, choosing only a single algorithm has inherent limitations — if the choice was bad, no remedial action can be taken and parallelism cannot be exploited, to name but a few problems. In this paper, we investigate how to predict the ranking of the portfolio algorithms on a particular problem. This information can be used to choose the single best algorithm, but also to allocate resources to the algorithms according to their rank. We evaluate a range of approaches to predict the ranking of a set of algorithms on a problem. We furthermore introduce a framework for categorizing ranking predictions that allows to judge the expressiveness of the predictive output. Our experimental evaluation demonstrates on a range of data sets from the literature that it is beneficial to consider the relationship between algorithms when predicting rankings. We furthermore show that relatively naive approaches deliver rankings of good quality already.
Deepak Mehta, Barry O'Sullivan, Lars Kotthoff, Yuri Malitsky
Lazy Branching for Constraint Satisfaction
IEEE International Conference on Tools with Artificial Intelligence, Washington DC, USA, November 2013
preprint PDF, bibtex, abstract
When solving a constraint satisfaction problem using a systematic backtracking method, the branching scheme normally selects a variable to which a value is assigned. In this paper we refer to such strategies as eager branching schemes. These contrast with the alternative class of novel branching schemes considered in this paper whereby having selected a variable we proceed by removing values from its domain. In this paper we study such lazy branching schemes in depth. We define three lazy branching schemes based on k-way, binary and split branching. We show how each can be incorporated into MAC, and define a novel value ordering heuristic that is suitable in this setting. Our results show that lazy branching can significantly out-perform traditional branching schemes across a variety of problem classes. While, in general, neither lazy nor eager branching dominates the other, our results clearly show that choosing the correct branching scheme for a given problem instance can significantly reduce search effort. Therefore, we implemented a variety of branching portfolios for choosing amongst all of the branching strategies studied in this paper. The results demonstrate that a good branching scheme can be automatically selected for a given problem instances and that including lazy branching schemes in the portfolio significantly reduces runtime.
Ozgur Akgun, Alan M. Frisch, Ian P. Gent, Bilal Hussain, Christopher A. Jefferson, Lars Kotthoff, Ian Miguel, Peter Nightingale
Automated Symmetry Breaking and Model Selection in Conjure
19th International Conference on Principles and Practice of Constraint Programming, Uppsala, Sweden, September 2013
preprint PDF, bibtex, abstract
Constraint modelling is widely recognised as a key bottleneck in applying constraint solving to a problem of interest. The Conjure automated constraint modelling system addresses this problem by automatically refining constraint models from problem specifications written in the Essence language. Essence provides familiar mathematical concepts like sets, functions and relations nested to any depth. To date, Conjure has been able to produce a set of alternative model kernels (i.e. without advanced features such as symmetry breaking or implied constraints) for a given specification. The first contribution of this paper is a method by which Conjure can break symmetry in a model as it is introduced by the modelling process. This works at the problem class level, rather than just individual instances, and does not require an expensive detection step after the model has been formulated. This allows Conjure to produce a higher quality set of models. A further limitation of Conjure has been the lack of a mechanism to select among the models it produces. The second contribution of this paper is to present two such mechanisms, allowing effective models to be chosen automatically.
Barry Hurley, Lars Kotthoff, Yuri Malitsky, Barry O'Sullivan
Proteus: A Hierarchical Portfolio of Solvers and Transformations, June 2013
PDF, bibtex, abstract
In recent years, portfolio approaches to solving SAT problems and CSPs have become increasingly common. There are also a number of different techniques for converting SAT problems into CSPs. In this paper, we leverage advances in both areas and present a novel hierarchical portfolio-based approach to CSP solving that does not rely purely on CSP solvers, but may convert a problem to SAT choosing a conversion technique and the accommodating SAT solver. Our experimental evaluation relies on competition CSP instances and uses eight CSP solvers, three SAT encodings and eighteen SAT solvers. We demonstrate that significant performance improvements can be obtained by considering alternative view-points of a combinatorial problem.
Lars Kotthoff
LLAMA: Leveraging Learning to Automatically Manage Algorithms, 2013
PDF, bibtex, abstract
Algorithm portfolio approaches have achieved remarkable improvements over single solvers. However, the implementation of such systems is often highly specialized and specific to the problem domain. This makes it difficult for researchers to explore different techniques for their specific problems. We present LLAMA, a modular and extensible toolkit that facilitates the exploration of a range of different portfolio techniques on any problem domain. We describe the current capabilities and limitations of the toolkit and illustrate its usage on a set of example SAT problems.
Ozgur Akgun, Alan Frisch, Bilal Hussain, Christopher Jefferson, Lars Kotthoff, Ian Miguel, Peter Nightingale
An Automated Constraint Modelling and Solving Toolchain
20th Automated Reasoning Workshop, April 2013
PDF, bibtex
Arunas Prokopas, Alan Frisch, Ian P. Gent, Christopher Jefferson, Lars Kotthoff, Ian Miguel, Peter Nightingale
Constructing constraint solvers using Monte Carlo Tree Search
20th Automated Reasoning Workshop, April 2013
PDF, bibtex, abstract
Constraint solvers are complex pieces of software that are capable of solving a wide variety of problems. Customisation and specialisation opportunities are usually very limited and require specialist knowledge. The Dominion constraint solver synthesizer automatically creates problem-specific solvers. The configuration of a constraint solver is highly complex, especially if the aim is to achieve high performance. We demonstrate how Monte Carlo Tree Search can be employed to tackle this problem.
Lars Kotthoff, Barry O'Sullivan
Constraint-based Clustering
10th International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) techniques in Constraint Programming, May 2013 (presentation-only abstract)
bibtex, abstract
Machine learning and constraint programming are almost completely independent research fields. However, there are significant opportunities for synergy between them. In this presentation, we introduce a constraint programming approach to the classification problem in machine learning. Specifically, we treat classification as a clustering problem.
Previous approaches have used constraints as a means of representing background knowledge to improve the quality of the resulting clustering. We show how to use such constraints to not only guide the machine learning algorithms, but replace them entirely. Our approach uses an off-the-shelf constraint solver to find the clustering that reflects as much background knowledge as possible. A second formulation allows us to optimise for the objectives commonly used in machine learning algorithms, such as maximising the inter-cluster distances.
We present an evaluation results of our approaches on a variety of well-known benchmarks covering a range of different application domains. Our approaches can significantly outperform standard clustering methods used in machine learning in terms of the quality of the resulting clustering and classification. In addition, the constraint programming formulation provides much more flexibility and customisation opportunities than standard machine learning approaches.
Lars Kotthoff
Reliability of Computational Experiments on Virtualised Hardware
Journal of Experimental and Theoretical Artificial Intelligence, 2013
preprint PDF, bibtex, abstract
We present a large-scale investigation of the variability of run times on physical and virtualised hardware. The aim of our investigation is to establish whether cloud infrastructures are suitable for running computational experiments where the results rely on reported run times. Our application is the use of the Minion constraint solver as an example of an Artificial Intelligence experiment. We include two major providers of public cloud infrastructure, Amazon and Rackspace, as well as a private Eucalyptus cloud. While there are many studies in the literature that investigate the performance of cloud environments, the problem of whether this performance is consistent and run time measurements are reliable has been largely ignored.
Our comprehensive experiments and detailed analysis of the results show that there is no intrinsic disadvantage of virtualised hardware over physical hardware and that in general cloud environments are suitable for running computational experiments. Our meticulous investigation reveals several interesting patterns in the variability of run times that researchers using a cloud for this purpose should be aware of. We close by giving recommendations as to which type of virtual machine with which cloud provider should be used to achieve reproducible results.
Lars Kotthoff
Algorithm Selection for Combinatorial Search Problems: A survey, 2012
PDF, bibtex, abstract
The Algorithm Selection Problem is concerned with selecting the best algorithm to solve a given problem on a case-by-case basis. It has become especially relevant in the last decade, as researchers are increasingly investigating how to identify the most suitable existing algorithm for solving a problem instead of developing new algorithms. This survey presents an overview of this work focusing on the contributions made in the area of combinatorial search problems, where Algorithm Selection techniques have achieved significant performance improvements. We unify and organise the vast literature according to criteria that determine Algorithm Selection systems in practice. The comprehensive classification of approaches identifies and analyses the different directions from which Algorithm Selection has been approached. This paper contrasts and compares different methods for solving the problem as well as ways of using these solutions. It closes by identifying directions of current and future research.
Thomas W. Kelsey, Lars Kotthoff, Christopher A. Jefferson, Stephen A. Linton, Ian Miguel, Peter Nightingale, Ian P. Gent
Qualitative Modelling via Constraint Programming: Past, Present and Future
18th International Conference on Principles and Practice of Constraint Programming, Québec, Canada, October 2012 (Position Paper)
preprint PDF, poster, bibtex, abstract
Qualitative modelling is a technique integrating the fields of theoretical computer science, artificial intelligence and the physical and biological sciences. The aim is to be able to model the behaviour of systems without estimating parameter values and fixing the exact quantitative dynamics. Traditional applications are the study of the dynamics of physical and biological systems at a higher level of abstraction than that obtained by estimation of numerical parameter values for a fixed quantitative model. Qualitative modelling has been studied and implemented to varying degrees of sophistication in Petri nets, process calculi and constraint programming. In this paper we reflect on the strengths and weaknesses of existing frameworks, we demonstrate how recent advances in constraint programming can be leveraged to produce high quality qualitative models, and we describe the advances in theory and technology that would be needed to make constraint programming the best option for scientific investigation in the broadest sense.
Lars Kotthoff, Ian Gent, Ian Miguel
An Evaluation of Machine Learning in Algorithm Selection for Search Problems
AI Communications, 2012
preprint PDF, bibtex, abstract
Machine learning is an established method of selecting algorithms to solve hard search problems. Despite this, to date no systematic comparison and evaluation of the different techniques has been performed and the performance of existing systems has not been critically compared with other approaches. We compare the performance of a large number of different machine learning techniques from different machine learning methodologies on five data sets of hard algorithm selection problems from the literature. In addition to well-established approaches, for the first time we also apply statistical relational learning to this problem. We demonstrate that there is significant scope for improvement both compared with existing systems and in general. To guide practitioners, we close by giving clear recommendations as to which machine learning techniques are likely to achieve good performance in the context of algorithm selection problems. In particular, we show that linear regression and alternating decision trees have a very high probability of achieving better performance than always selecting the single best algorithm.
Andreas Distler, Christopher Jefferson, Tom Kelsey, Lars Kotthoff
The Semigroups of Order 10
18th International Conference on Principles and Practice of Constraint Programming, Québec, Canada, October 2012
preprint PDF, presentation slides, poster, bibtex, abstract
The number of finite semigroups increases rapidly with the number of elements. Since existing enumeration formulae do not give the complete number of semigroups of given order up to symmetric equivalence, the remainder can only be found by careful search. We describe the use of mathematical results combined with distributed Constraint Satisfaction to show that the number of non-equivalent semigroups of order 10 is 12,418,001,077,381,302,684. This solves a previously open problem in Mathematics, and has directly led to improvements in Constraint Satisfaction technology.
Lars Kotthoff
Hybrid Regression-Classification Models for Algorithm Selection
20th European Conference on Artificial Intelligence, Montpellier, France, August 2012
preprint PDF, bibtex, abstract
Many state of the art Algorithm Selection systems use Machine Learning to either predict the run time or a similar performance measure of each of a set of algorithms and choose the algorithm with the best predicted performance or predict the best algorithm directly. We present a technique based on the well-established Machine Learning technique of stacking that combines the two approaches into a new hybrid approach and predicts the best algorithm based on predicted run times. We demonstrate significant performance improvements of up to a factor of six compared to the previous state of the art. Our approach is widely applicable and does not place any restrictions on the performance measure used, the way to predict it or the Machine Learning used to predict the best algorithm. We investigate different ways of deriving new Machine Learning features from the predicted performance measures and evaluate their effectiveness in increasing performance further. We use five different regression algorithms for performance prediction on five data sets from the literature and present strong empirical evidence that shows the effectiveness of our approach.
Dharini Balasubramaniam, Christopher Jefferson, Lars Kotthoff, Ian Miguel, Peter Nightingale
An Automated Approach to Generating Efficient Constraint Solvers
34th International Conference on Software Engineering, Zurich, Switzerland, June 2012
preprint PDF, bibtex, abstract
Combinatorial problems appear in numerous settings, from timetabling to industrial design. Constraint solving aims to find solutions to such problems efficiently and automatically. Current constraint solvers are monolithic in design, accepting a broad range of problems. The cost of this convenience is a complex architecture, inhibiting efficiency, extensibility and scalability. Solver components are also tightly coupled with complex restrictions on their configuration, making automated generation of solvers difficult.
We describe a novel, automated, model-driven approach to generating efficient solvers tailored to individual problems and present some results from applying the approach. The main contribution of this work is a solver generation framework called Dominion, which analyses a problem and, based on its characteristics, generates a solver using components chosen from a library. The key benefit of this approach is the ability to solve larger and more difficult problems as a result of applying finer-grained optimisations and using specialised techniques as required.
Lars Kotthoff, Ian Miguel, Peter Nightingale
Ensemble classification for constraint solver configuration
16th International Conference on Principles and Practices of Constraint Programming, St Andrews, Scotland, September 2010
preprint PDF, bibtex, abstract
The automatic tuning of the parameters of algorithms and automatic selection of algorithms has received a lot of attention recently. One possible approach is the use of machine learning techniques to learn classifiers which, given the characteristics of a particular problem, make a decision as to which algorithm or what parameters to use. Little research has been done into which machine learning algorithms are suitable and the impact of picking the "right" over the "wrong" technique. This paper investigates the differences in performance of several techniques on different data sets. It furthermore provides evidence that by using a meta-technique which combines several machine learning algorithms, we can avoid the problem of having to pick the "best" one and still achieve good performance.
Ian Gent, Chris Jefferson, Lars Kotthoff, Ian Miguel, Neil Moore, Peter Nightingale, Karen Petrie
Learning When to Use Lazy Learning in Constraint Solving
19th European Conference on Artificial Intelligence, Lisbon, Portugal, August 2010
preprint PDF, bibtex, abstract
Learning in the context of constraint solving is a technique by which previously unknown constraints are uncovered during search and used to speed up subsequent search. Recently, lazy learning, similar to a successful idea from satisfiability modulo theories solvers, has been shown to be an effective means of incorporating constraint learning into a solver. Although a powerful technique to reduce search in some circumstances, lazy learning introduces a substantial overhead, which can outweigh its benefits. Hence, it is desirable to know beforehand whether or not it is expected to be useful. We approach this problem using machine learning (ML). We show that, in the context of a large benchmark set, standard ML approaches can be used to learn a simple, cheap classifier which performs well in identifying instances on which lazy learning should or should not be used. Furthermore, we demonstrate significant performance improvements of a system using our classifier and the lazy learning and standard constraint solvers over a standard solver. Through rigorous cross-validation across the different problem classes in our benchmark set, we show the general applicability of our learned classifier.

Software

I have written a patch for RWeka to allow instance weights to be specified. It adds the new parameter "weight", which takes a list of weights for the instances as an argument, to the existing methods. I have tried contacting the package maintainer, but failed. Patch against version 0.4-12.

I am maintainer of the FSelector R package.

I am author and maintainer of LLAMA, an R package to simplify common algorithm selection tasks such as training a classifier as portfolio selector.

Other

If I'm not in the office, it's possible that you can find me in the jungle of Belize excavating and/or mapping Maya ruins. Check out the interactive map. Failing that, I might be making fancy drinks while fighting spider monkeys.