lars.kotthoff at insight-centre.org

INSIGHT Centre for Data Analytics

Cork Constraint
Computation Centre

University College Cork

Western Gateway Building

Cork, Ireland

I am a postdoctoral researcher on the EU FP7-funded ICON project. We are working on the intersection between Constraint Programming and Data Mining, trying to integrate the two fields. I am also working on the e-Policy project, also funded by an EU FP7 grant. The main aim is to support policy makers in their decision process across a multi-disciplinary effort aimed at engineering the policy making life-cycle.

I am spearheading (with Ian Gent) the recomputation project, which aims to make empirical computer science reproducible.

Have a look at my overview of the Algorithm Selection literature!

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.

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.

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

Improving the State of the Art in Inexact TSP Solving using Per-Instance Algorithm Selection

Learning and Intelligent OptimizatioN 9, Lille, France, January 2015

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

Recomputation.org: Experience of Its First Year and Lessons Learned

Recomputability 2014, London, UK, December 2014

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

Taking into Account Expected Future Bids in ePolicy Optimisation Problem

Technical report, Insight Centre for Data Analytics, University College Cork

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

Web-scale distributed eScience AI search across disconnected and heterogeneous infrastructures

10th IEEE International Conference on eScience, Guarujá, Brazil, October 2014

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

Discriminating Instance Generation for Automated Constraint Model Selection

20th International Conference on Principles and Practice of Constraint Programming, Lyon, France, September 2014

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

Integrating optimisation and agent-based modelling

28th European Conference on Modelling & Simulation, Brescia, Italy, May 2014

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)

Qualitative Modelling via Constraint Programming

Constraints, 2014 (to appear)

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

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

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

Algorithm Selection for Combinatorial Search Problems: A Survey

AI Magazine, 2014

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

Ranking Algorithms by Performance

Learning and Intelligent OptimizatioN 8, Gainesville, USA, February 2014

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

Algorithm Configuration in the Cloud: A Feasibility Study

Learning and Intelligent OptimizatioN 8, Gainesville, USA, February 2014

Lars Kotthoff

Ranking Algorithms by Performance, November 2013

Ranking Algorithms by Performance, November 2013

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

Lazy Branching for Constraint Satisfaction

IEEE International Conference on Tools with Artificial Intelligence, Washington DC, USA, November 2013

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

Automated Symmetry Breaking and Model Selection in Conjure

19th International Conference on Principles and Practice of Constraint Programming, Uppsala, Sweden, September 2013

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

Proteus: A Hierarchical Portfolio of Solvers and Transformations, June 2013

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

LLAMA: Leveraging Learning to Automatically Manage Algorithms, 2013

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

An Automated Constraint Modelling and Solving Toolchain

20th Automated Reasoning Workshop, April 2013

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

Constructing constraint solvers using Monte Carlo Tree Search

20th Automated Reasoning Workshop, April 2013

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)

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)

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.

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

Reliability of Computational Experiments on Virtualised Hardware

Journal of Experimental and Theoretical Artificial Intelligence, 2013

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.

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

Algorithm Selection for Combinatorial Search Problems: A survey, 2012

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)

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)

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

An Evaluation of Machine Learning in Algorithm Selection for Search Problems

AI Communications, 2012

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

The Semigroups of Order 10

18th International Conference on Principles and Practice of Constraint Programming, Québec, Canada, October 2012

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

Hybrid Regression-Classification Models for Algorithm Selection

20th European Conference on Artificial Intelligence, Montpellier, France, August 2012

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

An Automated Approach to Generating Efficient Constraint Solvers

34th International Conference on Software Engineering, Zurich, Switzerland, June 2012

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.

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

Ensemble classification for constraint solver configuration

16th International Conference on Principles and Practices of Constraint Programming, St Andrews, Scotland, September 2010

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

Learning When to Use Lazy Learning in Constraint Solving

19th European Conference on Artificial Intelligence, Lisbon, Portugal, August 2010

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.

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.

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.