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.

The problem of computing similar and dissimilar solutions to a given one has received much attention in constraint satisfaction and answer set programming (ASP). In many practical applications involving product configuration or planning, it is often the case that there are many valid solutions. To help the user see a small but representative sample, one needs algorithms that compute sets of dissimilar solutions. Once the user "zooms" in on one or two that she likes the most, it still makes sense to present several alternatives that are similar to the selected ones so that the user can find one that truly corresponds to her needs.

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 tractability of a Constraint Satisfaction Problem (CSP)is guaranteed by a direct relationship between its consistencylevel and a structural parameter of its constraint network suchas the treewidth. This result is not widely exploited in practicebecause enforcing higher-level consistencies can be costlyand can change the structure of the constraint network andincrease its width. Recently, R(*,m)C was proposed as a relational consistency property that does not modify the structureof the graph and, thus, does not affect its width. In this paper,we explore two main strategies, based on a tree decomposition of the CSP, for improving the performance of enforcingR(*,m)C and getting closer to the above tractability condition. Those strategies are: a) localizing the application ofthe consistency algorithm to the clusters of the tree decomposition, and b) bolstering constraint propagation betweenclusters by adding redundant constraints at their separators,for which we propose three new schemes. We characterizethe resulting consistency properties by comparing them, theoretically and empirically, to the original R(*,m)C and thepopular GAC and maxRPWC, and establish the benefits ofour approach for solving difficult 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.

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.

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.

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.

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.

The existing complete methods for solving Constraint Satisfaction Problems (CSPs) are usually based on a combination of exhaustive search and constraint propagation techniques for the reduction of the search space. Such propagation techniques are the local consistency algorithms. Arc Consistency (AC) and Generalized Arc Consistency (GAC) are the most widely studied local consistencies that are predominantly used in constraint solvers. However, many stronger local consistencies than (G)AC have been proposed, even recently, but have been rather overlooked due to their prohibitive cost. This research proposes efficient algorithms for strong consistencies for both binary and non-binary constraints that can be easily adopted by standard CP solvers. Experimental results have so far demonstrated that the proposed algorithms are quite competitive and often more efficient than state-of-the-art methods, being orders of magnitude faster on various problem classes.