2016

• Fréchette, Alexandre, Lars Kotthoff, Talal Rahwan, Holger H. Hoos, Kevin Leyton-Brown, and Tomasz P. Michalak. “Using the Shapley Value to Analyze Algorithm Portfolios.” In 30th AAAI Conference on Artificial Intelligence, 3397–3403, 2016. preprint PDF bibTeX abstract

  Algorithms for NP-complete problems often have different strengths and weaknesses, and thus algorithm portfolios often outperform individual algorithms. It is surprisingly difficult to quantify an component algorithm's contribution to such a portfolio. Reporting a component's standalone performance wrongly rewards near-clones while penalizing algorithms that have small but distinct areas of strength. Measuring a component's marginal contribution to an existing portfolio is better, but penalizes sets of strongly correlated algorithms, thereby obscuring situations in which it is essential to have at least one algorithm from such a set. This paper argues for analyzing component algorithm contributions via a measure drawn from coalitional game theory---the Shapley value---and yields insight into a research community's progress over time. We conclude with an application of the analysis we advocate to SAT competitions, yielding novel insights into the behaviour of algorithm portfolios, their components, and the state of SAT solving technology.

• Bischl, Bernd, Pascal Kerschke, Lars Kotthoff, Marius Lindauer, Yuri Malitsky, Alexandre Fréchette, Holger H. Hoos, et al. “ASlib: A Benchmark Library for Algorithm Selection.” Artificial Intelligence Journal (AIJ), no. 237 (2016): 41–58. preprint PDF bibTeX abstract

  The task of algorithm selection involves choosing an algorithm from a set of algorithms on a per-instance basis in order to exploit the varying performance of algorithms over a set of instances. The algorithm selection problem is attracting increasing attention from researchers and practitioners in AI. Years of fruitful applications in a number of domains have resulted in a large amount of data, but the community lacks a standard format or repository for this data. This situation makes it difficult to share and compare different approaches effectively, as is done in other, more established fields. It also unnecessarily hinders new researchers who want to work in this area. To address this problem, we introduce a standardized format for representing algorithm selection scenarios and a repository that contains a growing number of data sets from the literature. Our format has been designed to be able to express a wide variety of different scenarios. To demonstrate the breadth and power of our platform, we describe a study that builds and evaluates algorithm selection models through a common interface. The results display the potential of algorithm selection to achieve significant performance improvements across a broad range of problems and algorithms.

• Kotthoff, Lars, Ciaran McCreesh, and Christine Solnon. “Portfolios of Subgraph Isomorphism Algorithms.” In LION 10, 2016. preprint PDF bibTeX abstract

  Subgraph isomorphism is a computationally challenging problem with important practical applications, for example in computer vision, biochemistry, and model checking. There are a number of state-of-the-art algorithms for solving the problem, each of which has its own performance characteristics. As with many other hard problems, the single best choice of algorithm overall is rarely the best algorithm on an instance-by-instance. We develop an algorithm selection approach which leverages novel features to characterise subgraph isomorphism problems and dynamically decides which algorithm to use on a per-instance basis. We demonstrate substantial performance improvements on a large set of hard benchmark problems. In addition, we show how algorithm selection models can be leveraged to gain new insights into what affects the performance of an algorithm.

• Bischl, Bernd, Michel Lang, Lars Kotthoff, Julia Schiffner, Jakob Richter, Erich Studerus, Giuseppe Casalicchio, and Zachary M. Jones. “Mlr: Machine Learning in R.” Journal of Machine Learning Research 17, no. 170 (2016): 1–5. preprint PDF bibTeX abstract

  The mlr package provides a generic, object- oriented, and extensible framework for classification, regression, survival analysis and clustering for the R language. It provides a unified interface to more than 160 basic learners and includes meta-algorithms and model selection techniques to improve and extend the functionality of basic learners with, e.g., hyperparameter tuning, feature selection, and ensemble construction. Parallel high-performance computing is natively supported. The package targets practitioners who want to quickly apply machine learning algorithms, as well as researchers who want to implement, benchmark, and compare their new methods in a structured environment.

• Degroote, Hans, Bernd Bischl, Lars Kotthoff, and Patrick de Causmacker. “Reinforcement Learning for Automatic Online Algorithm Selection - an Empirical Study.” In ITAT, 1649:93–101. CEUR Workshop Proceedings, 2016. preprint PDF bibTeX abstract

  In this paper a reinforcement learning methodology for automatic online algorithm selection is introduced and empirically tested. It is applicable to automatic algorithm selection methods that predict the performance of each available algorithm and then pick the best one. The experiments confirm the usefulness of the methodology: using online data results in better performance. As in many online learning settings an exploration vs. exploitation trade-off, synonymously learning vs. earning trade-off, is incurred. Empirically investigating the quality of classic solution strategies for handling this trade-off in the automatic online algorithm selection setting is the secondary goal of this paper. The automatic online algorithm selection problem can be modelled as a contextual multi-armed bandit problem. Two classic strategies for solving this problem are tested in the context of automatic online algorithm selection: epsilon-greedy and lower confidence bound. The experiments show that a simple purely exploitative greedy strategy outperforms strategies explicitly performing exploration.

• Bessière, Christian, Luc De Raedt, Lars Kotthoff, Siegfried Nijssen, Barry O’Sullivan, and Dino Pedreschi, eds. Data Mining and Constraint Programming: Foundations of a Cross-Disciplinary Approach. 1st ed. Vol. 10101. Lecture Notes in Artificial Intelligence. Springer, 2016. preprint PDF bibTeX abstract

  A successful integration of constraint programming and data mining has the potential to lead to a new ICT paradigm with far reaching implications. It could change the face of data mining and machine learning, as well as constraint programming technology. It would not only allow one to use data mining techniques in constraint programming to identify and update constraints and optimization criteria, but also to employ constraints and criteria in data mining and machine learning in order to discover models compatible with prior knowledge. This book reports on some key results obtained on this integrated and cross- disciplinary approach within the European FP7 FET Open project no. 284715 on “Inductive Constraint Programming” and a number of associated workshops and Dagstuhl seminars. The book is structured in five parts: background; learning to model; learning to solve; constraint programming for data mining; and showcases.

• Kotthoff, Lars. “Algorithm Selection for Combinatorial Search Problems: A Survey.” In Data Mining and Constraint Programming: Foundations of a Cross-Disciplinary Approach, edited by Christian Bessiere, Luc De Raedt, Lars Kotthoff, Siegfried Nijssen, Barry O’Sullivan, and Dino Pedreschi, 149–90. Cham: Springer International Publishing, 2016. doi:10.1007/978-3-319-50137-6_7. 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 chapter contrasts and compares different methods for solving the problem as well as ways of using these solutions.

• Hurley, Barry, Lars Kotthoff, Barry O’Sullivan, and Helmut Simonis. “ICON Loop Health Show Case.” In Data Mining and Constraint Programming: Foundations of a Cross-Disciplinary Approach, edited by Christian Bessiere, Luc De Raedt, Lars Kotthoff, Siegfried Nijssen, Barry O’Sullivan, and Dino Pedreschi, 325–33. Cham: Springer International Publishing, 2016. doi:10.1007/978-3-319-50137-6_14. bibTeX abstract

  In this document we describe the health show case for the ICON project. This corresponds to Task 6.2 in WP 6 of the Description of Work for the project. The description provides a high-level abstraction, detailed description of the interfaces between modules, and a description of sample data.

• Nanni, Mirco, Lars Kotthoff, Riccardo Guidotti, Barry O’Sullivan, and Dino Pedreschi. “ICON Loop Carpooling Show Case.” In Data Mining and Constraint Programming: Foundations of a Cross-Disciplinary Approach, edited by Christian Bessiere, Luc De Raedt, Lars Kotthoff, Siegfried Nijssen, Barry O’Sullivan, and Dino Pedreschi, 310–24. Cham: Springer International Publishing, 2016. doi:10.1007/978-3-319-50137-6_13. bibTeX abstract

  In this chapter we describe a proactive carpooling service that combines induction and optimization mechanisms to maximize the impact of carpooling within a community. The approach autonomously infers the mobility demand of the users through the analysis of their mobility traces (i.e. Data Mining of GPS trajectories) and builds the network of all possible ride sharing opportunities among the users. Then, the maximal set of carpooling matches that satisfy some standard requirements (maximal capacity of vehicles, etc.) is computed through Constraint Programming models, and the resulting matches are proactively proposed to the users. Finally, in order to maximize the expected impact of the service, the probability that each carpooling match is accepted by the users involved is inferred through Machine Learning mechanisms and put in the CP model. The whole process is reiterated at regular intervals, thus forming an instance of the general ICON loop.

• Bessiere, Christian, Luc De Raedt, Tias Guns, Lars Kotthoff, Mirco Nanni, Siegfried Nijssen, Barry O’Sullivan, Anastasia Paparrizou, Dino Pedreschi, and Helmut Simonis. “The Inductive Constraint Programming Loop.” In Data Mining and Constraint Programming: Foundations of a Cross-Disciplinary Approach, edited by Christian Bessiere, Luc De Raedt, Lars Kotthoff, Siegfried Nijssen, Barry O’Sullivan, and Dino Pedreschi, 303–9. Cham: Springer International Publishing, 2016. doi:10.1007/978-3-319-50137-6_12. bibTeX abstract

  Constraint programming is used for a variety of real-world optimization problems, such as planning, scheduling and resource allocation problems. At the same time, one continuously gathers vast amounts of data about these problems. Current constraint programming software does not exploit such data to update schedules, resources and plans. We propose a new framework, that we call the Inductive Constraint Programming (ICON) loop. In this approach data is gathered and analyzed systematically in order to dynamically revise and adapt constraints and optimization criteria. Inductive Constraint Programming aims at bridging the gap between the areas of data mining and machine learning on the one hand, and constraint programming on the other hand.

• Hurley, Barry, Lars Kotthoff, Yuri Malitsky, Deepak Mehta, and Barry O’Sullivan. “Advanced Portfolio Techniques.” In Data Mining and Constraint Programming: Foundations of a Cross-Disciplinary Approach, edited by Christian Bessiere, Luc De Raedt, Lars Kotthoff, Siegfried Nijssen, Barry O’Sullivan, and Dino Pedreschi, 191–225. Cham: Springer International Publishing, 2016. doi:10.1007/978-3-319-50137-6_8. bibTeX abstract

  There exists a proliferation of different approaches to using portfolios and algorithm selection to make solving combinatorial search and optimisation problems more efficient, as surveyed in the previous chapter. In this chapter, we take a look at a detailed case study that leverages transformations between problem representations to make portfolios more effective, followed by extensions to the state of the art that make algorithm selection more robust in practice.

2015

• Kotthoff, Lars, Pascal Kerschke, Holger Hoos, and Heike Trautmann. “Improving the State of the Art in Inexact TSP Solving Using Per-Instance Algorithm Selection.” In LION 9, 202–17, 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.

• Kotthoff, Lars, Mirco Nanni, Riccardo Guidotti, and Barry O’Sullivan. “Find Your Way Back: Mobility Profile Mining with Constraints.” In CP, 638–53. Cork, Ireland, 2015. preprint PDF bibTeX abstract

  Mobility profile mining is a data mining task that can be formulated as clustering over movement trajectory data. The main challenge is to separate the signal from the noise, i.e.{\textbackslash} one-off trips. We show that standard data mining approaches suffer the important drawback that they cannot take the symmetry of non-noise trajectories into account. That is, if a trajectory has a symmetric equivalent that covers the same trip in the reverse direction, it should become more likely that neither of them is labelled as noise. We present a constraint model that takes this knowledge into account to produce better clusters. We show the efficacy of our approach on real-world data that was previously processed using standard data mining techniques.

• Kotthoff, Lars, Barry O’Sullivan, S. S. Ravi, and Ian Davidson. “Complex Clustering Using Constraint Programming: Modelling Electoral Map Creation.” In 14th International Workshop on Constraint Modelling and Reformulation, 2015. preprint PDF bibTeX abstract

  Traditional clustering is limited to a single collection of objects, described by a set of features under simple objectives and constraints. Though this setting can scale to huge data sets, many real world problems do not fit it. Consider the problem motivating this work: creating electoral district maps. Not only are two sets of objects (electoral districts and elected officials) separately clustered simultaneously under complex constraints, the clusters must be matched and it is required to find a global optimum. Existing formulations of clustering such as those using procedural languages or convex programming cannot handle such complex settings. In this paper we explore clustering this complex setting using constraint programming. We implement our methods in the Numberjack language and make use of large-scale solvers such as Gurobi which exploit multi-core architectures.

• Chue Hong, Neil P., Tom Crick, Ian P. Gent, Lars Kotthoff, and Kenji Takeda. “Top Tips to Make Your Research Irreproducible.” CoRR abs/1504.00062 (2015). preprint PDF bibTeX abstract

  It is an unfortunate convention of science that research should pretend to be reproducible; our top tips will help you mitigate this fussy conventionality, enabling you to enthusiastically showcase your irreproducible work.

• Kotthoff, Lars. “ICON Challenge on Algorithm Selection.” CoRR abs/1511.04326 (2015). preprint PDF bibTeX

2014

• ———. “Reliability of Computational Experiments on Virtualised Hardware.” Journal of Experimental and Theoretical Artificial Intelligence 26, no. 1 (2014): 33–49. 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.

• ———. “Algorithm Selection for Combinatorial Search Problems: A Survey.” AI Magazine 35, no. 3 (2014): 48–60. 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.

• ———. “Ranking Algorithms by Performance.” In LION 8, 16–19, 2014. preprint PDF bibTeX

• Geschwender, Daniel, Frank Hutter, Lars Kotthoff, Yuri Malitsky, Holger H. Hoos, and Kevin Leyton-Brown. “Algorithm Configuration in the Cloud: A Feasibility Study.” In LION 8, 41–44, 2014. preprint PDF bibTeX

• Hurley, Barry, Lars Kotthoff, Yuri Malitsky, and Barry O’Sullivan. “Proteus: A Hierarchical Portfolio of Solvers and Transformations.” In CPAIOR, 301–17, 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.

• Kelsey, Thomas W., Lars Kotthoff, Christopher A. Jefferson, Stephen A. Linton, Ian Miguel, Peter Nightingale, and Ian P. Gent. “Qualitative Modelling via Constraint Programming.” Constraints 19, no. 2 (2014): 163–73. 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.

• Johnson, Peter George, Tina Balke, and Lars Kotthoff. “Integrating Optimisation and Agent-Based Modelling.” In 28th European Conference on Modelling & Simulation. Brescia, Italy, 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.

• Hussain, Bilal, Ian P. Gent, Christopher A. Jefferson, Lars Kotthoff, Ian Miguel, Glenna F. Nightingale, and Peter Nightingale. “Discriminating Instance Generation for Automated Constraint Model Selection.” In 20th International Conference on Principles and Practice of Constraint Programming, 356–65. Lyon, France, 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.

• Kelsey, Thomas W., Martin McCaffery, and Lars Kotthoff. “Web-Scale Distributed EScience AI Search across Disconnected and Heterogeneous Infrastructures.” In 10th IEEE International Conference on EScience, 39–46. Guarujá, Brazil, 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.

• Gent, Ian P., and Lars Kotthoff. “Recomputation.org: Experience of Its First Year and Lessons Learned.” In Recomputability 2014. London, UK, 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.

• Kotthoff, Lars. “Algorithm Selection in Practice.” AISB Quarterly, no. 138 (2014): 4–8. preprint PDF bibTeX

• Wilson, Nic, and Lars Kotthoff. “Taking into Account Expected Future Bids in EPolicy Optimisation Problem.” Insight Centre for Data Analytics, July 2014. preprint PDF bibTeX

2013

• Kotthoff, Lars, and Barry O’Sullivan. “Constraint-Based Clustering.” In 10th International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming, 2013. 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.

• Akgun, Ozgur, Alan M. Frisch, Bilal Hussain, Christopher A. Jefferson, Lars Kotthoff, Ian Miguel, and Peter Nightingale. “An Automated Constraint Modelling and Solving Toolchain.” In 20th Automated Reasoning Workshop, 2013. preprint PDF bibTeX

• Prokopas, Arunas, Alan M. Frisch, Ian P. Gent, Christopher A. Jefferson, Lars Kotthoff, Ian Miguel, and Peter Nightingale. “Constructing Constraint Solvers Using Monte Carlo Tree Search.” In 20th Automated Reasoning Workshop, 2013. preprint 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.

• Kotthoff, Lars. “LLAMA: Leveraging Learning to Automatically Manage Algorithms.” arXiv, June 2013. preprint 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.

• Hurley, Barry, Lars Kotthoff, Yuri Malitsky, and Barry O’Sullivan. “Proteus: A Hierarchical Portfolio of Solvers and Transformations.” arXiv, June 2013. 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 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.

• Akgun, Ozgur, Alan M. Frisch, Ian P. Gent, Bilal Hussain, Christopher A. Jefferson, Lars Kotthoff, Ian Miguel, and Peter Nightingale. “Automated Symmetry Breaking and Model Selection in Conjure.” In 19th International Conference on Principles and Practice of Constraint Programming, 107–16. Uppsala, Sweden, 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.

• Mehta, Deepak, Barry O’Sullivan, Lars Kotthoff, and Yuri Malitsky. “Lazy Branching for Constraint Satisfaction.” In ICTAI, 1012–19, 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.

• Kotthoff, Lars. “Ranking Algorithms by Performance,” November 2013. preprint 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.

2012

• Kelsey, Thomas W., Lars Kotthoff, Christopher A. Jefferson, Stephen A. Linton, Ian Miguel, Peter Nightingale, and Ian P. Gent. “Qualitative Modelling via Constraint Programming: Past, Present and Future.” In 18th International Conference on Principles and Practice of Constraint Programming (Position Paper), 2012. 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.

• Distler, Andreas, Christopher A. Jefferson, Tom Kelsey, and Lars Kotthoff. “The Semigroups of Order 10.” In 18th International Conference on Principles and Practice of Constraint Programming, 883–99, 2012. preprint PDF 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.

• Kotthoff, Lars, Ian P. Gent, and Ian Miguel. “An Evaluation of Machine Learning in Algorithm Selection for Search Problems.” AI Communications 25, no. 3 (2012): 257–70. 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.

• Hammond, Gail, Samantha Krause, Lars Kotthoff, and Thomas H. Guderjan. “Continuing Research Using Landscape Archaeology and GIS at Nojol Nah, Belize.” In 77th Annual Meeting of the Society for American Archaeology. Memphis, TN, 2012. preprint PDF bibTeX abstract

  We present preliminary results of interdisciplinary efforts in determining the use and management of ancient Maya rural landscapes in northwestern Belize. Through our comprehensive data set combining archaeology, GIS, land survey and soil science, we provide a singular insight into the strategies used by the people that inhabited this site on the periphery of the Maya world. Georeferenced maps - the results of intensive pedestrian survey - have been combined with a NASA digital elevation model as well as hydrological and soil data into a regional geodatabase, which includes the results of ongoing test units, and larger excavations.

• Kotthoff, Lars, and Thomas H. Guderjan. “An Interactive Atlas of Maya Sites.” In 77th Annual Meeting of the Society for American Archaeology. Memphis, TN, 2012. preprint PDF bibTeX abstract

  Every year, a large amount of geographical data on Maya settlements is generated in the course of excavations, surveys and similar operations. Only some of those data are published in reports and most of it is not used more than once. We present a new effort that aims to make publicly available such data as the location of individual sites as well as detailed maps, excavation pictures and contextual information. All this is available through an easy-to-use web interface at www.mayamap.org that brings the power of traditional GIS systems to the layman user.

• Kotthoff, Lars. “On Algorithm Selection, with an Application to Combinatorial Search Problems.” Ph.D., University of St Andrews, 2012. preprint PDF bibTeX abstract

  The Algorithm Selection Problem is to select the most appropriate way for solving a problem given a choice of different ways. Some of the most prominent and successful applications come from Artificial Intelligence and in particular combinatorial search problems. Machine Learning has established itself as the de facto way of tackling the Algorithm Selection Problem. Yet even after a decade of intensive research, there are no established guidelines as to what kind of Machine Learning to use and how. This dissertation presents an overview of the field of Algorithm Selection and associated research and highlights the fundamental questions left open and problems facing practitioners. In a series of case studies, it underlines the difficulty of doing Algorithm Selection in practice and tackles issues related to this. The case studies apply Algorithm Selection techniques to new problem domains and show how to achieve significant performance improvements. Lazy learning in constraint solving and the implementation of the alldifferent constraint are the areas in which we improve on the performance of current state of the art systems. The case studies furthermore provide empirical evidence for the effectiveness of using the misclassification penalty as an input to Machine Learning. After having established the difficulty, we present an effective technique for reducing it. Machine Learning ensembles are a way of reducing the background knowledge and experimentation required from the researcher while increasing the robustness of the system. Ensembles do not only decrease the difficulty, but can also increase the performance of Algorithm Selection systems. They are used to much the same ends in Machine Learning itself. We finally tackle one of the great remaining challenges of Algorithm Selection — which Machine Learning technique to use in practice. Through a large-scale empirical evaluation on diverse data taken from Algorithm Selection applications in the literature, we establish recommendations for Machine Learning algorithms that are likely to perform well in Algorithm Selection for combinatorial search problems. The recommendations are based on strong empirical evidence and additional statistical simulations. The research presented in this dissertation significantly reduces the knowledge threshold for researchers who want to perform Algorithm Selection in practice. It makes major contributions to the field of Algorithm Selection by investigating fundamental issues that have been largely ignored by the research community so far.

• Balasubramaniam, Dharini, Christopher Jefferson, Lars Kotthoff, Ian Miguel, and Peter Nightingale. “An Automated Approach to Generating Efficient Constraint Solvers.” In 34th International Conference on Software Engineering, 661–71, 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.

• Kotthoff, Lars. “Hybrid Regression-Classification Models for Algorithm Selection.” In 20th European Conference on Artificial Intelligence, 480–85, 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.

• ———. “Algorithm Selection for Combinatorial Search Problems: A Survey.” University College Cork, 2012. preprint 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.

2011

• Kelsey, Tom, and Lars Kotthoff. “Exact Closest String as a Constraint Satisfaction Problem.” In Proceedings of the International Conference on Computational Science, 1062–71, 2011. preprint PDF bibTeX abstract

  We report the first evaluation of Constraint Satisfaction as a computational framework for solving closest string problems. We show that careful consideration of symbol occurrences can provide search heuristics that provide several orders of magnitude speedup at and above the optimal distance. We also report the first analysis and evaluation – using any technique – of the computational difficulties involved in the identification of all closest strings for a given input set. We describe algorithms for web-scale distributed solution of closest string problems, both purely based on AI backtrack search and also hybrid numeric-AI methods.

• Kotthoff, Lars, Ian P. Gent, and Ian Miguel. “A Preliminary Evaluation of Machine Learning in Algorithm Selection for Search Problems.” In Fourth Annual Symposium on Combinatorial Search, 84–91, 2011. 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 to other approaches. We compare machine learning techniques for algorithm selection on real-world data sets of hard search problems. In addition to well-established approaches, for the first time we also apply statistical relational learning to this problem. We demonstrate that most machine learning techniques and existing systems perform less well than one might expect. To guide practitioners, we close by giving clear recommendations as to which machine learning techniques are likely to perform well based on our experiments.

• Gent, Ian P., Christopher A. Jefferson, Lars Kotthoff, and Ian Miguel. “Modelling Constraint Solver Architecture Design as a Constraint Problem.” In Annual ERCIM Workshop on Constraint Solving and Constraint Logic Programming, 87–96, 2011. preprint PDF bibTeX abstract

  Designing component-based constraint solvers is a complex problem. Some components are required, some are optional and there are interdependencies between the components. Because of this, previous approaches to solver design and modification have been ad-hoc and limited. We present a system that transforms a description of the components and the characteristics of the target constraint solver into a constraint problem. Solving this problem yields the description of a valid solver. Our approach represents a significant step towards the automated design and synthesis of constraint solvers that are specialised for individual constraint problem classes or instances.

• Gent, Ian P., and Lars Kotthoff. “Reliability of Computational Experiments on Virtualised Hardware.” In AAAI Workshop AI for Data Center Management and Cloud Computing, 2011. preprint PDF bibTeX abstract

  We present preliminary results of an investigation into the suitability of virtualised hardware -- in particular clouds -- for running computational experiments. Our main concern was that the reported CPU time would not be reliable and reproducible. The results demonstrate that while this is true in cases where many virtual machines are running on the same physical hardware, there is no inherent variation introduced by using virtualised hardware compared to non-virtualised hardware.

• Balasubramaniam, Dharini, Lakshitha de Silva, Christopher A. Jefferson, Lars Kotthoff, Ian Miguel, and Peter Nightingale. “Dominion: An Architecture-Driven Approach to Generating Efficient Constraint Solvers.” In 9th Working IEEE/IFIP Conference on Software Architecture, 228–31, 2011. preprint PDF bibTeX abstract

  Constraints are used to solve combinatorial problems in a variety of industrial and academic disciplines. However most constraint solvers are designed to be general and monolithic, leading to problems with efficiency, scalability and extensibility. We propose a novel, architecture-driven constraint solver generation framework called Dominion to tackle these issues. For any given problem, Dominion generates a lean and efficient solver tailored to that problem. In this paper, we outline the Dominion approach and its implications for software architecture specification of the solver.

2010

• Kotthoff, Lars, and Neil C.A. Moore. “Distributed Solving through Model Splitting.” In 3rd Workshop on Techniques for Implementing Constraint Programming Systems (TRICS), 26–34, 2010. preprint PDF bibTeX abstract

  Constraint problems can be trivially solved in parallel by exploring different branches of the search tree concurrently. Previous approaches have focused on implementing this functionality in the solver, more or less transparently to the user. We propose a new approach, which modifies the constraint model of the problem. An existing model is split into new models with added constraints that partition the search space. Optionally, additional constraints are imposed that rule out the search already done. The advantages of our approach are that it can be implemented easily, computations can be stopped and restarted, moved to different machines and indeed solved on machines which are not able to communicate with each other at all.

• Gent, Ian P., Lars Kotthoff, Ian Miguel, and Peter Nightingale. “Machine Learning for Constraint Solver Design – a Case Study for the Alldifferent Constraint.” In 3rd Workshop on Techniques for Implementing Constraint Programming Systems (TRICS), 13–25, 2010. preprint PDF bibTeX abstract

  Constraint solvers are complex pieces of software which require many design decisions to be made by the implementer based on limited information. These decisions affect the performance of the finished solver significantly. Once a design decision has been made, it cannot easily be reversed, although a different decision may be more appropriate for a particular problem. We investigate using machine learning to make these decisions automatically depending on the problem to solve. We use the alldifferent constraint as a case study. Our system is capable of making non-trivial, multi-level decisions that improve over always making a default choice and can be implemented as part of a general-purpose constraint solver.

• Kotthoff, Lars, Ian Miguel, and Peter Nightingale. “Ensemble Classification for Constraint Solver Configuration.” In 16th International Conference on Principles and Practices of Constraint Programming, 321–29, 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.

• Gent, Ian P., Christopher A. Jefferson, Lars Kotthoff, Ian Miguel, Neil Moore, Peter Nightingale, and Karen E. Petrie. “Learning When to Use Lazy Learning in Constraint Solving.” In 19th European Conference on Artificial Intelligence, 873–78, 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.

• Kotthoff, Lars, Ian P. Gent, and Ian Miguel. “Using Machine Learning to Make Constraint Solver Implementation Decisions.” In SICSA PhD Conference, 2010. preprint PDF bibTeX abstract

  Programs to solve so-called constraint problems are complex pieces of software which require many design decisions to be made more or less arbitrarily by the implementer. These decisions affect the performance of the finished solver significantly. Once a design decision has been made, it cannot easily be reversed, although a different decision may be more appropriate for a particular problem. We investigate using machine learning to make these decisions automatically depending on the problem to solve with the alldifferent constraint as an example. Our system is capable of making non-trivial, multi-level decisions that improve over always making a default choice.

2009

• Kotthoff, Lars. “Constraint Solvers: An Empirical Evaluation of Design Decisions.” CIRCA preprint. University of St Andrews, Centre for Interdisciplinary Research in Computational Algebra, 2009. preprint PDF bibTeX abstract

  This paper presents an evaluation of the design decisions made in four state-of-the-art constraint solvers; Choco, ECLiPSe, Gecode, and Minion. To assess the impact of design decisions, instances of the five problem classes n-Queens, Golomb Ruler, Magic Square, Social Golfers, and Balanced Incomplete Block Design are modelled and solved with each solver. The results of the experiments are not meant to give an indication of the performance of a solver, but rather investigate what influence the choice of algorithms and data structures has. The analysis of the impact of the design decisions focuses on the different ways of memory management, behaviour with increasing problem size, and specialised algorithms for specific types of variables. It also briefly considers other, less significant decisions.

• Gent, Ian P., Christopher A. Jefferson, Lars Kotthoff, Ian Miguel, and Peter Nightingale. “Specification of the Dominion Input Language Version 0.1.” University of St Andrews, 2009. preprint PDF bibTeX

• Kotthoff, Lars. “Dominion – A Constraint Solver Generator.” In Doctoral Program of CP, 2009. preprint PDF bibTeX abstract

  This paper proposes a design for a system to generate constraint solvers that are specialised for specific problem models. It describes the design in detail and gives preliminary experimental results showing the feasibility and effectiveness of the approach.

2007

• ———. “Using Constraints to Render Websites — Applications of Artificial Intelligence in E-Commerce Environments.” Diplom, University of Leipzig, 2007. preprint PDF bibTeX abstract

  Constraint programming is an area of Artificial Intelligence which has many applica- tions. This thesis applies its techniques to a new kind of problem – the rendering of online retailer websites. First, in-depth introductions to constraint programming and the problem of rendering a shop website will be given. A prototypical implementation of a constraint problem solver and a system to solve and illustrate the problem will be described. The architecture of the prototypical implementation and specific features, algo- rithms, and design decisions will be detailed, analysed, and illustrated. An overview of related work both in the fields of constraint programming and website generation will be presented and existing technologies evaluated. Features and concepts unique to this thesis, like real-time constraint satisfaction, will be introduced and discussed. Finally, a comprehensive example will illustrate the problem, means of modelling it, and possible solutions. An outlook to future work and a summary conclude the thesis.