Algorithms for solving combinatorial optimisation problems often exhibit complementary strengths, motivating automated algorithm selection by training ML models that predict the best algorithm for a given instance. However, collecting training data for such models is computationally expensive, as it requires running all provided algorithms on all training instances. Recent work on frugal algorithm selection shows that the training data collection cost can be reduced substantially through active learning, but the interaction between model choices and data efficiency remains poorly understood. In this work, we empirically investigate how different learning formulations behave under limited training data using the ASLib benchmark. Our results reveal that multiclass classification (MC), despite weak performance when trained on full training data, improves dramatically with active learning. Remarkably, active MC matches strong passive learners while using only a fraction of the training data. This highlights an unexpected efficiency gain: algorithm selectors that underperform with full training data become highly effective when training data is selected actively.

Background: Algorithms to solve combinatorial search and optimisation problems typically exhibit complementary performance – on problem instances where one fails, another shines. Selecting the best algorithm for each problem instance, rather than relying on a single algorithm, is crucial for optimal performance. This is known as the Algorithm Selection Problem, which is usually solved by training Machine Learning models that predict the performance of available algorithms. However, the labelling cost, i.e., the cost of collecting the training data to build such models, can be extremely high, as it involves running algorithms on all training instances. Objectives: Rather than following the traditional approach of exhaustively running all algorithms on all training instances to train algorithm selection models, we propose a more frugal approach using active learning to intelligently decide which algorithms to run on which problem instances, thus reducing the labelling cost to build algorithm selection systems. Methods: We find that standard active learning strategies perform poorly in algorithm selection settings, where labelling costs are inherently non-uniform due to the highly variable runtimes of algorithms across problem instances. Therefore, we propose novel active learning strategies for algorithm selection that leverage a dynamic time limit mechanism, together with auxiliary models for predicting timeouts and algorithm runtimes, to decide which algorithm runs strike the best balance between cost and informativeness. Results: The proposed active learning strategies significantly outperform traditional approaches in terms of frugality, achieving competitive performance at substantially lower labelling cost. Our results demonstrate that we can save up to 90% of the labelling cost associated with generating training data for algorithm selection models without loss in algorithm selection performance. Conclusions: Our Frugal Algorithm Selection framework, which leverages a dynamic time limit mechanism, prediction uncertainty, and the auxiliary models for timeout and runtime prediction, can dramatically reduce labelling cost without compromising predictive performance. This allows the training of algorithm selection systems to be more efficient for combinatorial optimisation problems.

Large Language Models (LLMs) have demonstrated great promise in generating code, especially when used inside an evolutionary computation framework to iteratively optimize the generated algorithms. However, in some cases they fail to generate competitive algorithms or the code optimization stalls, and we are left with no recourse because of a lack of understanding of the generation process and generated codes. We present a novel approach to mitigate this problem by enabling users to analyze the generated codes inside the evolutionary process and how they evolve over repeated prompting of the LLM. We show results for three benchmark problem classes and demonstrate novel insights. In particular, LLMs tend to generate more complex code with repeated prompting, but additional complexity can hurt algorithmic performance in some cases. Different LLMs have different coding "styles" and generated code tends to be dissimilar to other LLMs. These two findings suggest that using different LLMs inside the code evolution frameworks might produce higher performing code than using only one LLM.

The design of machine learning systems often requires trading off different objectives, for example, prediction error and energy consumption for deep neural networks (DNNs). Typically, no single design performs well in all objectives; therefore, finding Pareto-optimal designs is of interest. The search for Pareto-optimal designs involves evaluating designs in an iterative process, and the measurements are used to evaluate an acquisition function that guides the search process. However, measuring different objectives incurs different costs. For example, the cost of measuring the prediction error of DNNs is orders of magnitude higher than that of measuring the energy consumption of a pre-trained DNN as it requires re-training the DNN. Current state-of-the-art methods do not consider this difference in objective evaluation cost, potentially incurring expensive evaluations of objective functions in the optimization process. In this paper, we develop a novel decoupled and cost-aware multi-objective optimization algorithm, which we call Flexible Multi-Objective Bayesian Optimization (FlexiBO) to address this issue. For evaluating each design, FlexiBO selects the objective with higher relative gain by weighting the improvement of the hypervolume of the Pareto region with the measurement cost of each objective. This strategy, therefore, balances the expense of collecting new information with the knowledge gained through objective evaluations, preventing FlexiBO from performing expensive measurements for little to no gain. We evaluate FlexiBO on seven state-of-the-art DNNs for image recognition, natural language processing (NLP), and speech-to-text translation. Our results indicate that, given the same total experimental budget, FlexiBO discovers designs with 4.8% to 12.4% lower hypervolume error than the best method in state-of-the-art multi-objective optimization.

Abstract The TPTP World is a well established infrastructure that supports research, development, and deployment of Automated Theorem Proving (ATP) systems. This work uses data in the TPTP World to assess progress in ATP from 2015 to 2023.

Algorithms to solve hard combinatorial problems often exhibit complementary performance, i.e. where one algorithm fails, another shines. Algorithm portfolios and algorithm selection take advantage of this by running all algorithms in parallel or choosing the best one to run on a problem instance. In this paper, we show that neither of these approaches gives the best possible performance and propose the happy medium of running a subset of all algorithms in parallel. We propose a method to choose this subset automatically for each problem instance, and demonstrate empirical improvements of up to 19% in terms of runtime, 81% in terms of misclassification penalty, and 26% in terms of penalized averaged runtime on scenarios from the ASlib benchmark library. Unlike all other algorithm selection and scheduling approaches in the literature, our performance measures are based on the actual performance for algorithms running in parallel rather than assuming overhead-free parallelization based on sequential performance. Our approach is easy to apply in practice and does not require to solve hard problems to obtain a schedule, unlike other techniques in the literature, while still delivering superior performance.

The design of machine learning systems often requires trading off different objectives, for example, prediction error and energy consumption for deep neural networks (DNNs). Typically, no single design performs well in all objectives; therefore, finding Pareto-optimal designs is of interest. The search for Pareto-optimal designs involves evaluating designs in an iterative process, and the measurements are used to evaluate an acquisition function that guides the search process. However, measuring different objectives incurs different costs. For example, the cost of measuring the prediction error of DNNs is orders of magnitude higher than that of measuring the energy consumption of a pre-trained DNN as it requires re-training the DNN. Current state-of-the-art methods do not consider this difference in objective evaluation cost, potentially incurring expensive evaluations of objective functions in the optimization process. In this paper, we develop a novel decoupled and cost-aware multi-objective optimization algorithm, which we call Flexible Multi-Objective Bayesian Optimization (FlexiBO) to address this issue. For evaluating each design, FlexiBO selects the objective with higher relative gain by weighting the improvement of the hypervolume of the Pareto region with the measurement cost of each objective. This strategy, therefore, balances the expense of collecting new information with the knowledge gained through objective evaluations, preventing FlexiBO from performing expensive measurements for little to no gain. We evaluate FlexiBO on seven state-of-the-art DNNs for image recognition, natural language processing (NLP), and speech-to-text translation. Our results indicate that, given the same total experimental budget, FlexiBO discovers designs with 4.8% to 12.4% lower hypervolume error than the best method in state-of-the-art multi-objective optimization.

Automated hyperparameter optimization (HPO) has gained great popularity and is an important component of most automated machine learning frameworks. However, the process of designing HPO algorithms is still an unsystematic and manual process: new algorithms are often built on top of prior work, where limitations are identified and improvements are proposed. Even though this approach is guided by expert knowledge, it is still somewhat arbitrary. The process rarely allows for gaining a holistic understanding of which algorithmic components drive performance and carries the risk of overlooking good algorithmic design choices. We present a principled approach to automated benchmark-driven algorithm design applied to multifidelity HPO (MF-HPO). First, we formalize a rich space of MF-HPO candidates that includes, but is not limited to, common existing HPO algorithms and then present a configurable framework covering this space. To find the best candidate automatically and systematically, we follow a programming-by-optimization approach and search over the space of algorithm candidates via Bayesian optimization. We challenge whether the found design choices are necessary or could be replaced by more naive and simpler ones by performing an ablation analysis. We observe that using a relatively simple configuration (in some ways, simpler than established methods) performs very well as long as some critical configuration parameters are set to the right value.

Recent years have seen a proliferation of ML frameworks. Such systems make ML accessible to non-experts, especially when combined with powerful parameter tuning and AutoML techniques. Modern, applied ML extends beyond direct learning on clean data, however, and needs an expressive language for the construction of complex ML workflows beyond simple pre- and post-processing. We present mlr3pipelines, an R framework which can be used to define linear and complex non-linear ML workflows as directed acyclic graphs. The framework is part of the mlr3 ecosystem, leveraging convenient resampling, benchmarking, and tuning components.

Meta-algorithmics, the field of leveraging machine learning to use algorithms more efficiently, has achieved impressive performance improvements in many areas of AI. It treats the algorithms to improve on as black boxes – nothing is known about their inner workings. This allows meta-algorithmic techniques to be deployed in many applications, but leaves potential performance improvements untapped by ignoring information that the algorithms could provide. In this paper, we open the black box without sacrificing the universal applicability of meta-algorithmic techniques by automatically analyzing the source code of the algorithms under consideration and show how to use it to improve algorithm selection performance. We demonstrate improvements of up to 82% on the standard ASlib benchmark library.

Assessing the progress made in AI and contributions to the state of the art is of major concern to the community. Recently, Frechette et al. [2016] advocated performing such analysis via the Shapley value, a concept from coalitional game theory. In this paper, we argue that while this general idea is sound, it unfairly penalizes older algorithms that advanced the state of the art when introduced, but were then outperformed by modern counterparts. Driven by this observation, we introduce the temporal Shapley value, a measure that addresses this problem while maintaining the desirable properties of the (classical) Shapley value. We use the tempo- ral Shapley value to analyze the progress made in (i) the different versions of the Quicksort algorithm; (ii) the annual SAT competitions 2007–2014; (iii) an annual competition of Constraint Programming, namely the MiniZinc challenge 2014–2016. Our analysis reveals novel insights into the development made in these important areas of research over time.

Algorithm selection approaches have achieved impressive performance improvements in many areas of AI. Most of the literature considers the offline algorithm selection problem, where the initial selection model is never updated after training. However, new data from running algorithms on instances becomes available when algorithms are selected and run. We investigate how this online data can be used to improve the selection model over time. This is especially relevant when insufficient training instances were used, but potentially improves the performance of algorithm selection in all cases. We formally define the online algorithm selection problem and model it as a contextual multi-armed bandit problem, propose a methodology for solving it, and empirically demonstrate performance improvements. We also show that our online algorithm selection method can be used when no training data whatsoever is available, a setting where offline algorithm selection cannot be used. Our experiments indicate that a simple greedy approach achieves the best performance.

The Travelling Salesperson Problem (TSP) is one of the best-studied NP-hard problems. Over the years, many different solution approaches and solvers have been developed. For the first time, we directly compare five state-of-the-art inexact solvers-namely, LKH, EAX, restart variants of those, and MAOS-on a large set of well-known benchmark instances and demonstrate complementary performance, in that different instances may be solved most effectively by different algorithms. We leverage this complementarity to build an algorithm selector, which selects the best TSP solver on a per-instance basis and thus achieves significantly improved performance compared to the single best solver, representing an advance in the state of the art in solving the Euclidean TSP. Our in-depth analysis of the selectors provides insight into what drives this performance improvement.

WEKA is a widely used, open-source machine learning platform. Due to its intuitive interface, it is particularly popular with novice users. However, such users often find it hard to identify the best approach for their particular dataset among the many available. We describe the new version of Auto-WEKA, a system designed to help such users by automatically searching through the joint space of WEKA's learning algorithms and their respective hyperparameter settings to maximize performance, using a state-of-the-art Bayesian optimization method. Our new package is tightly integrated with WEKA, making it just as accessible to end users as any other learning algorithm.

Algorithms for NP-complete problems often have different strengths andweaknesses, and thus algorithm portfolios often outperform individualalgorithms. It is surprisingly difficult to quantify a component algorithm's contributionto such a portfolio. Reporting a component's standalone performance wronglyrewards near-clones while penalizing algorithms that have small but distinctareas of strength. Measuring a component's marginal contribution to an existingportfolio is better, but penalizes sets of strongly correlated algorithms,thereby obscuring situations in which it is essential to have at least onealgorithm from such a set. This paper argues for analyzing component algorithmcontributions via a measure drawn from coalitional game theory---the Shapleyvalue---and yields insight into a research community's progress over time. Weconclude with an application of the analysis we advocate to SAT competitions,yielding novel insights into the behaviour of algorithm portfolios, theircomponents, and the state of SAT solving technology.

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.

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.

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. Proceedings 28th European Conference on Modelling and Simulation © ECMS Flaminio Squazzoni, Fabio Baronio, Claudia Archetti, Marco Castellani (Editors).

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 in which 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. Although 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.

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 branchings 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 branchings 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 instances 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.

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.

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.

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.

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.