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 article contrasts and compares different methods for solving the problem as well as ways of using these solutions.

Maximum Satisfiability (MaxSAT) is an optimization variant of the Boolean Satisfiability (SAT) problem. In general, MaxSAT algorithms perform a succession of SAT solver calls to reach an optimum solution making extensive use of cardinality constraints. Many of these algorithms are non-incremental in nature, i.e. at each iteration the formula is rebuilt and no knowledge is reused from one iteration to another. In this paper, we exploit the knowledge acquired across iterations using novel schemes to use cardinality constraints in an incremental fashion. We integrate these schemes with several MaxSAT algorithms. Our experimental results show a significant performance boost for these algo- rithms as compared to their non-incremental counterparts. These results suggest that incremental cardinality constraints could be beneficial for other constraint solving domains.

We introduce statistical constraints, a declarative modelling tool that links statistics and constraint programming. We discuss two statistical constraints and some associated filtering algorithms. Finally, we illustrate applications to standard problems encountered in statistics and to a novel inspection scheduling problem in which the aim is to find inspection plans with desirable statistical properties.

This paper proposes an analysis of the effects of consensus and preference aggregation on the consistency of pairwise comparisons. We define some boundary properties for the inconsistency of group preferences and investigate their relation with different inconsistency indices. Some results are presented on more general dependencies between properties of inconsistency indices and the satisfaction of boundary properties. In the end, given three boundary properties and nine indices among the most relevant ones, we will be able to present a complete analysis of what indices satisfy what properties and offer a reflection on the interpretation of the inconsistency of group preferences.

We study propagation for the Sequence constraint in the context of constraint programming based on limited-width MDDs. Our first contribution is proving that establishing MDD-consistency for Sequence is NP-hard. Yet, we also show that this task is fixed parameter tractable with respect to the length of the sub-sequences. In addition, we propose a partial filtering algorithm that relies on a specific decomposition of the constraint and a novel extension of MDD filtering to node domains. We experimentally evaluate the performance of our proposed filtering algorithm, and demonstrate that the strength of the MDD propagation increases as the maximum width is increased. In particular, MDD propagation can outperform conventional domain propagation for Sequence by reducing the search tree size and solving time by several orders of magnitude. Similar improvements are observed with respect to the current best MDD approach that applies the decomposition of Sequence into Among constraints.

We present a variation of the classical Distributed Stochastic Algorithm (DSA), a local iterative best-response algorithm for Distributed Constraint Optimization Problems (DCOPs). We introduce weights for the agents, which influence their behaviour. We model DCOPs as graph processing problems, where the variables are represented as vertices and the constraints as edges.This enables us to create the Ranked DSA (RDSA), where the choice of the new state is influenced by the vertex rank as computed by a modified Page Rank algorithm. We experimentally show that this leads to a better speed of convergence to Nash Equilibria. Furthermore, we explore the trade-off space between average utility and convergence to Nash Equilibria, by using algorithms that switch between the DSA and RDSA strategies and by using heterogeneous graphs, with vertices using strategies in different proportions.

Manipulation and bribery have received much attention from the social choice community. We consider these concepts in the setting of preference formalisms, where the Pareto principle is used to assign to preference theories collections of optimal outcomes, rather than a single winning outcome as is common in social choice. We adapt the concepts of manipulation and bribery to this setting. We provide characterizations of situations when manipulation and bribery are possible. Assuming a particular logical formalism for expressing preferences, we establish the complexity of determining a possibility for manipulation or bribery. In all cases that do not in principle preclude a possibility of manipulation or bribery, our complexity results show that deciding whether manipulation or bribery are actually possible is computationally hard.

We introduce a novel qualitative preference representation language, preference trees , or P-trees . We show that the lan- guage is intuitive to specify preferences over combinatorial domains and it extends existing preference formalisms such as LP-trees , ASO-rules and possibilistic logic . We study rea- soning problems with P-trees and obtain computational com- plexity results.

Real-world decisions involve preferences that are nonlinear and often defined over multiple and interdependent issues. Such scenarios are known to be challenging, especially in strategic encounters between agents having distinct constraints and preferences. In this case, reaching an agreement becomes more difficult as the search space and the complexity of the problem grow. In this paper, we propose a new representation for constraint-based utility spaces that can tackle the scalability problem by efficiently finding the optimal contracts. Particularly, the constraint-based utility space is mapped into an issue-constraint hyper-graph. Exploring the utility space reduces then to a message passing mechanism along the hyper-edges by means of utility propagation. We experimentally evaluate the model using parameterized random nonlinear utility spaces. We show that it can handle a large family of complex utility spaces by finding the optimal contract(s), outperforming previous sampling-based approaches.

Markov processes are widely used to generate sequences that imitate a given style, using random walk. Random walk generates sequences by iteratively concatenating states to prefixes of length equal or less than the given Markov order}. However, at higher orders, Markov chains tend to replicate chunks of the corpus with a size possibly higher than the order, a primary form of plagiarism. The Markov order defines a maximum length for training but not for generation. In the framework of constraint satisfaction (CSP), we introduce MaxOrder. This global constraint ensures that generated sequences do not include chunks larger than a given maximum order. We exhibit an automaton that recognises the solution set, with a size linear in the size of the corpus. We propose a linear-time procedure to generate this automaton from a corpus and a given max order. We then use this automaton to achieve generalised arc consistency for the MaxOrder constraint, holding on a sequence of size n, in O(n.T) time, where T is the size of the automaton. We illustrate our approach by generating text sequences from text corpora with a maximum order guarantee, effectively controlling plagiarism.