Constraint Programming (CP) solvers classically explore the solution space using tree-search based heuristics. Monte-Carlo Tree-Search (MCTS) is a tree-search method aimed at optimal sequential decision making under uncertainty. At the crossroads of CP and MCTS, this paper presents the Bandit Search for Constraint Programming (BASCOP)  algorithm, adapting MCTS to the specifics of CP search trees. Formally, MCTS simultaneously estimates the average node reward, and uses it to bias the exploration towards the most promising regions of the tree, borrowing the multi-armed bandit (MAB) decision rule. The two contributions in BASCOP concern i) a specific reward function, estimating the relative failure depth conditionally to a (variable, value) assignment; ii) a new  decision rule, hybridizing the MAB framework and the spirit of local neighborhood search. Specifically, BASCOP guides the CP search in the neighborhood of the previous best solution, by exploiting statistical estimates gathered across multiple restarts. BASCOP, using Gecode as the underlying constraint solver, shows significant improvements over the depth-first search baseline on some  CP benchmark suites. For hard job-shop scheduling problems, BASCOP matches the results of state-of-the-art scheduling-specific CP approaches. These results demonstrate the potential of BASCOP as a generic yet robust search method for CP.

Distributed Constraint Problem solving represents a fundamental research area in distributed artificial intelligence and multi-agent systems. The constraint density, or the ratio of the number of constraints to the number of variables, determines the difficulty of either finding a solution or minimizing the set of variable assignment conflicts. Reducing density typically reduces difficulty. We present a fully distributed technique for reducing the effective density of constraint graphs, called Virtual Structure Reduction (VSR). The VSR technique leverages the occurrence of variables that must be assigned the same value based on shared constraints and can improve solver performance using existing algorithms. We discuss our Distributed Constraint Optimization Problem (DCOP) solver, integrated with the Distributed Stochastic Algorithm (DSA), called VSR-DSA. The VSR-DSA algorithm demonstrates performance gains vs DSA in both solution quality and time on 3-coloring problems.

CSP solvers usually search a partial assignment search tree.We present a new formalization for CSP solvers, which spansa conceptually different search tree, where each node representssubsets of the original domains for the variables. We experimentwith a simple backtracking algorithm for this searchtree and show that it outperforms a simple backtracking algorithmon the traditional search tree in many cases.

The Web is currently shifting from data on linked Web pages towards less interlinked data in social networks on the Web. Therefore, rather than being based on the link structure between Web pages, the ranking of search results needs to be based on something new. We believe that it can be based on user preferences and ontological background knowledge, as a means to personalized access to information. There are many approaches to preference representation and reasoning in the literature. The most prominent qualitative ones are perhaps CP-nets. Their clear graphical structure unifies an easy representation of preferences with nice properties when computing the best outcome. In this paper, we introduce ontological CP-nets, where the knowledge domain has an ontological structure, i.e., the values of the variables are constrained relative to an underlying ontology. We show how the computation of Pareto optimal outcomes for such ontological CP-nets can be reduced to the solution of constraint satisfaction problems. We also provide several complexity and tractability results.

We describe a constraint-based timetabling system that was developed for the dental school based at Cork University Hospital in Ireland.This system has been deployed since 2010.Dental school timetabling differs from other university course scheduling in that certain clinic sessions can be used by multiple courses at the same time, provided a limit on room capacity is satisfied.Starting from a constraint programming solution using a web interface, we have moved to a mixed integer programming-based solver to deal with multiple objective functions, along with a dedicated Java application, which provides a rich user interface.Solutions for the years 2010, 2011 and 2012 have been used in the dental school, replacing a manual timetabling process, which could no longer cope with increasing student numbers and resulting resource bottlenecks.The use of the automated system allowed the dental school to increase student numbers to the maximum possible given the available resources.It also provides the school with a valuable "what-if" analysis tool.

This paper outlines the design of a scheduling algorithm that allocates outstabling locations to railway trains. From time to time railway trains may need to be outstabled to temporary locations, such as stations, sidings, depots, etc., until they are needed for regular operations. This is common for urban rail transit, and especially so for those that do not operate 24 hours. During non-traffic hours (NTH), trains are outstabled to various locations along the rail network so that when operations start again next day, the trains will be nearby their originating station or conveniently located so that they can be put into service whenever needed. However, this is complicated by the fact that engineering works, such as rail testing, installation, regular maintenance, etc. are done during the NTH. Therefore, passenger trains must be outstabled in such a way that they do not interfere with night-time engineering works or the movements of associated engineering trains. Since the engineering works scheduling is done separate to outstabling, this is a mixed-system problem. This paper shows how we modeled this as a constraint-satisfaction problem (CSP) and implemented into an “Outstabling System” (OSS) for the Hong Kong Mass Transit Railway (MTR) using a two-stage search algorithm.

A Constraint Satisfaction Problem (CSP) with n variables ranging over a domain of d values can be solved by brute-force in d^n steps (omitting a polynomial factor). With a more careful approach, this trivial upper bound can be improved for certain natural restrictions of the CSP. In this paper we establish theoretical limits to such improvements, and draw a detailed landscape of the subexponential-time complexity of CSP. We first establish relations between the subexponential-time complexity of CSP and that of other problems, including CNF-Sat. We exploit this connection to provide tight characterizations of the subexponential-time complexity of CSP under common assumptions in complexity theory. For several natural CSP parameters, we obtain threshold functions that precisely dictate the subexponential-time complexity of CSP with respect to the parameters under consideration. Our analysis provides fundamental results indicating whether and when one can significantly improve on the brute-force search approach for solving CSP.

Markov processes are increasingly used to generate finite-length sequences that imitate a given style. However, Markov processes are notoriously difficult to control. Recently, Markov constraints have been introduced to give users some control on generated sequences. Markov constraints reformulate finite-length Markov sequence generation in the framework of constraint satisfaction (CSP). However, in practice, this approach is limited to local constraints and its performance is low for global constraints, such as cardinality or arithmetic constraints. This limitation prevents generated sequences to follow structural properties which are independent of the style, but inherent to the domain, such as meter. In this article, we introduce meter, a constraint that ensures a sequence is 1) Markovian with regards to a given corpus and 2) follows metrical rules expressed as cumulative cost functions. Additionally, meter can simultaneously enforce cardinality constraints. We propose a domain consistency algorithm whose complexity is pseudo-polynomial. This result is obtained thanks to a theorem on the growth of sumsets by Khovanskii. We illustrate our constraint on meter-constrained music generation problems that were so far not solvable by any other technique.

One of the most widely studied classes of constraints in constraint programming (CP) is that of table constraints. Numerousspecialized filtering algorithms, enforcing the wellknown property called generalized arc consistency (GAC),have been developed for such constraints. Among the most successful GAC algorithms for table constraints, we find variants of simple tabular reduction (STR), like STR2. In this paper,we propose an extension of STR-based algorithms that achieves full pairwise consistency (FPWC), a consistency stronger than GAC and max restricted pairwise consistency (maxRPWC). Our approach involves counting the number of occurrences of specific combinations of values in constraint intersections. Importantly, the worst-case time complexity of one call to the basic filtering procedure at the heart of our new algorithm is quite close to that of STR algorithms. Experiments demonstrate that our method can outperform STR2 in many classes of problems, being significantly faster in some cases. Also, it is clearly superior to maxRPWC+, an algorithm that has been recently proposed.

The complexity and tight integration of electromechanical systems often makes them "brittle" and hard to modify in response to changing requirements. We aim to remedy this by capturing expert knowledge as functional blueprints, an idea inspired by regulatory processes that occur in natural morphogenesis. We then apply this knowledge in an intelligent design variation tool. When a user modifies a design, our tool uses functional blueprints to modify other components in response, thereby maintaining integration and reducing the need for costly search or constraint solving. In this paper, we refine the functional blueprint concept and discuss practical issues in applying it to electromechanical systems. We then validate our approach with a case study applying our prototype tool to create variants of a miniDroid robot and by empirical evaluation of convergence dynamics of networks of functional blueprints.