It is well established that in many scenarios there is no single solver that will provide optimal performance across a wide range of problem instances. Taking advantage of this observation, research into algorithm selection is designed to help identify the best approach for each problem at hand. This segregation is usually based on carefully constructed features, designed to quickly present the overall structure of the instance as a constant size numeric vector. Based on these features, a plethora of machine learning techniques can be utilized to predict the appropriate solver to execute, leading to significant improvements over relying solely on any one solver. However, being manually constructed, the creation of good features is an arduous task requiring a great deal of knowledge of the problem domain of interest. To alleviate this costly yet crucial step, this paper presents an automated methodology for producing an informative set of features utilizing a deep neural network. We show that the presented approach completely automates the algorithm selection pipeline and is able to achieve significantly better performance than a single best solver across multiple problem domains.

A Data Scientist typically performs a number of tedious and time-consuming steps to derive insight from a raw data set. The process usually starts with data ingestion, cleaning, and transformation (e.g. outlier removal, missing value imputation), then proceeds to model building, and finally a presentation of predictions that align with the end-users objectives and preferences. It is a long, complex, and sometimes artful process requiring substantial time and effort, especially because of the combinatorial explosion in choices of algorithms (and platforms), their parameters, and their compositions. Tools that can help automate steps in this process have the potential to accelerate the time-to-delivery of useful results, expand the reach of data science to non-experts, and offer a more systematic exploration of the available options. This work presents a step towards this goal.

Our objective is to boost the state-of-the-art performance in MaxSATsolving. To this end, we employ the instance-specific algorithmconfigurator ISAC, and improve it with the latest inportfolio technology. Experimental results on SAT show that thiscombination marks a significant step forward in our ability to tunealgorithms instance-specifically. We then apply the new methodology toa number of MaxSAT problem domains and show that the resulting solversconsistently outperform the best existing solvers on the respectiveproblem families. In fact, the solvers presented here were independentlyevaluated at the 2013 MaxSAT Evaluation where they won six of the elevencategories.

This paper outlines an online approach for algorithm configuration which uses the power of modern multicore system to evaluate multiple parameters configurations in parallel.

The success or failure of a solver is oftentimes closely tied to the proper configuration of the solver's parameters. However, tuning such parameters by hand requires expert knowledge, is time consuming, and is error-prone. In recent years, automatic algorithm configuration tools have made significant advances and can nearly always find better parameters than those found through hand tuning. However, current approaches require significant offline computational resources, and follow a train-once methodology that is unable to later adapt to changes in the type of problem solved. To this end, this paper presents Real-time Algorithm Configuration through Tournaments (ReACT), a method that does not require any offline training to perform algorithm configuration. ReACT exploits the multi-core infrastructure available on most modern machines to create a system that continuously searches for improving parameterizations, while guaranteeing a particular level of performance. The experimental results show that, despite the simplicity of the approach, ReACT quickly finds a set of parameters that is better than the default parameters and is competitive with state-of-the-art algorithm configurators.

The success and power of algorithm selection techniques has been empirically demonstrated on numerous occasions, most noticeably in the competition settings like those for SAT, CSP, MaxSAT, QBF, etc. Yet while there is now a plethora of competing approaches, all of them are dependent on the quality of a set of structural features they use to distinguish amongst the instances. Over the years, each domain has defined and refined its own set of features, yet at their core they are mostly a collection of everything that was considered useful in the past. As an alternative to this shotgun generation of features, this paper instead proposes a more systematic approach. Specifically, the paper shows how latent features gathered from matrix decomposition are enough for a linear model to achieve a level of performance comparable to a perfect Oracle portfolio. This information can, in turn, help guide researchers to the kinds of structural features they should be looking for, or even just identifying when such features are missing.

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 are ubiquitous in artificial intelligence and related areas. While there has been a significant amount of research into the design and implementation of solvers for combinatorial problems, it is well-known that there is still no single solver that performs best across a broad set of problem types and domains.This has motivated the development of portfolios of solvers. A portfolio typically comprises either many different solvers, instances of the same solver tuned in different ways, or some combination of these. However, current approaches to portfolio design take a static view of the process.Specifically, the design of the portfolio is determined offline, and then deployed in some setting.In this paper we propose an approach to evolving the portfolio over time based on the problems instances that it encounters.We study several challenges raised by such a dynamic approach, such as how to re-tune the portfolio over time.Our empirical results demonstrate that our evolving portfolio approach significantly out-performed the standard static approach in the case when the type of instances observed change over time.

We present a dynamic branching scheme for set partitioning problems. The idea is to trace features of the underlying MIP model and to base search decisions on the features of the current subproblem to be solved. We show how such a system can be trained efficiently by introducing minimal learning bias that traditional model-based machine learning approaches rely on. Experiments on a highly heterogeneous collection of set partitioning instances show significant gains over dynamic search guidance in Cplex as well as instance-specifically tuned pure search heuristics.

Instance-Specific Algorithm Configuration (ISAC) is a novel general technique for automatically generating and tuning algorithm portfolios. The approach has been very successful in practice, but up to now it has been committed to using all the features it was provided. However, traditional feature filtering techniques are not applicable, requiring multiple computationally expensive tuning steps during the evaluation stage. To this end, we show three new evaluation functions that use precomputed runtimes of a collection of untuned solvers to quickly evaluate subsets of features. One of our proposed functions even shows how to generate such an effective collection of solvers when only one highly parameterized solver is available. Using these new functions, we show that the number of features used by ISAC can be reduced to less than a quarter of the original number while often providing significant performance gains. We present numerical results on both SAT and CP domains.

We present a new method for instance-specific algorithm configuration (ISAC). It is based on the integration of the algorithm configuration system GGA and the recently proposed stochastic offline programming paradigm. ISAC is provided a solver with categorical, ordinal, and/or continuous parameters, a training benchmark set of input instances for that solver, and an algorithm that computes a feature vector that characterizes any given instance. ISAC then provides high quality parameter settings for any new input instance. Experiments on a variety of different constrained optimization and constraint satisfaction solvers show that automatic algorithm configuration vastly outperforms manual tuning. Moreover, we show that instance-specific tuning frequently leads to significant speed-ups over instance-oblivious configurations.

We propose a framework which we call stochastic off-line programming (SOP). The idea is to embed the development of combinatorial algorithms in an off-line learning environment which helps the developer choose heuristic advisors that guide the search for satisfying or optimal solutions. In particular, we consider the case where the developer has several heuristic advisors available. Rather than selecting a single heuristics, we propose that one of the heuristics is chosen randomly whenever the heuristic guidance is sought. The task of SOP is to learn favorable instance-specific distributions of the heuristic advisors in order to boost the average-case performance of the resulting combinatorial algorithm.