In this paper, we present a reinforcement learning approach for resolving inconsistencies in qualitative constraint networks ( QCN s). QCN s are typically used in constraint programming to represent and reason about intuitive spatial or temporal relations like x { is inside of ∨ overlaps } y . Naturally, QCN s are not immune to uncertainty, noise, or imperfect data that may be present in information, and thus, more often than not, they are hampered by inconsistencies. We propose a multi-armed bandit approach that defines a well-suited ordering of constraints for finding a maximal satisfiable subset of them. Specifically, our learning approach interacts with a solver, and after each trial a reward is returned to measure the performance of the selected action (constraint addition). The reward function is based on the reduction of the solution space of a consistent reconstruction of the input QCN . Experimental results with different bandit policies and various rewards that are obtained by our algorithm suggest that we can do better than the state of the art in terms of both effectiveness, viz., lower number of repairs obtained for an inconsistent QCN , and efficiency, viz., faster runtime.

The presented work concerns the automatic detection of legend texts inside maps. After extracting the texts from the images using OCR tools, we use an iterative clustering process on the extracted texts. We consider five main criteria, with different levels of importance: text alignment, distance between text boxes, background color of the text, font color, and font size. For each criterion, we define appropriate similarity measures. We propose a method that combines, incrementally, the partitions obtained by each criterion. The experimental study reveals two important results. First, combining several criteria gives better results than considering a single distance metric (e.g., Euclidean distance) between text boxes. Secondly, the overall effectiveness of the priority relation, which we intuitively defined among the criteria for detecting caption texts, is confirmed.

In constraint satisfaction problems, the variable ordering heuristic takes a central place by selecting the variables to branch on during backtrack search. As many hand-crafted branching heuristics have been proposed in the literature, a key issue is to identify, from a pool of candidate heuristics, which one is the best for solving a given constraint satisfaction task. Based on the observation that modern constraint solvers are using restart sequences, the best heuristic identification problem can be cast in the context of multi-armed bandits as a non-stochastic best arm identification problem. Namely, during each run of some given restart sequence, the bandit algorithm selects a branching heuristic and receives a reward for this heuristic before proceeding to the next run. The goal is to identify the best heuristic using few runs, and without any stochastic assumption about the constraint solver. In this study, we propose an adaptive variant of Successive Halving that exploits Luby's universal restart sequence. We analyze the convergence of this bandit algorithm in the non-stochastic setting, and we demonstrate its empirical effectiveness on various constraint satisfaction benchmarks.

In constraint-based applications, the user is often required to be an expert as, for a given problem instance, many parameters of the used solver must be manually tuned to improve its efficiency. Clearly, this background knowledge burdens the spread of constraint programming technology to non-expert users. In order to alleviate this issue, the idea of "autonomous" constraint solving is to adjust the solver parameters and to efficiently handle any problem instance without manual tuning. Notably, the choice of the variable ordering heuristic can lead to drastically different performances. A key question arises then: how can we find the best variable ordering heuristic for a problem instance, given a set of available heuristics provided by the solver? To answer this question, we propose an algorithmic framework that combines multi-armed bandits and restarts. Each candidate heuristic is viewed as an arm, and the framework learns to estimate the best heuristic using a multi-armed bandit algorithm. The common mechanism of restarts is used to provide feedback for reinforcing the bandit algorithm. Based on a thorough experimental evaluation, we demonstrate that this framework is able to find the best heuristic for most problem instances; notably, it outperforms the state-of-the-art in terms of time and solved instances.

Backtracking search is a complete approach that is traditionally used to solve instances modeled as constraint satisfaction problems. The space explored during search depends dramatically on the order that variables are instantiated. Considering that a perfect variable ordering might result to a backtrack-free search (i.e., finding backdoors, cycle cutsets), finding heuristics for variable ordering has always attracted research interest. For fifteen years, constraint weighting has been shown to be a successful approach for guiding backtrack search. In this paper, we show how the popular generic variable ordering heuristic dom/wdeg can be made more robust by taking finer information at each conflict: the "current" arity of the failing constraint as well as the size of the current domains of the variables involved in that constraint. Our experimental results show the practical interest of this refined variant of constraint weighting.

A singleton-style consistency is a local consistency that verifies if each base relation (atom) of each constraint of a qualitative constraint network (QCN) can serve as a support with respect to the closure of that network under a (naturally) weaker local consistency. This local consistency is essential for tackling fundamental reasoning problems associated with QCNs, such as the satisfiability checking or the minimal labeling problem, but can suffer from redundant constraint checks, especially when those checks occur far from where the pruning usually takes place. In this paper, we propose singleton-style consistencies that are applied just on the neighbourhood of a singleton-checked constraint instead of the whole network. We make a theoretical comparison with existing consistencies and consequently prove some properties of the new ones. In addition, we propose algorithms to enforce our consistencies, as well as parsimonious variants thereof, that are more efficient in practice than the state of the art. We make an experimental evaluation with random and structured QCNs of Interval Algebra in the phase transition region to demonstrate the potential of our approach.

Partial singleton (weak) path consistency, or partial -consistency, for a qualitative constraint network, ensures that the process of instantiating any constraint of that network with any of its base relations b and enforcing partial (weak) path consistency, or partial -consistency, in the updated network, yields a partially -consistent subnetwork where the respective constraint is still defined by b. This local consistency is essential for helping to decide the satisfiability of challenging qualitative constraint networks and has been shown to play a crucial role in tackling more demanding problems associated with a given qualitative constraint network, such as the problem of minimal labeling. One of the main downsides to using partial -consistency, is that it is computationally expensive to enforce in a given qualitative constraint network, as, despite being a local consistency in principle, it retains a global scope of the network at hand. In this paper, we propose a lazy algorithm that restricts the singleton checks associated with partial -consistency to constraints that are likely to lead to the removal of a base relation upon their propagation. A key feature of this algorithm is that it collectively eliminates certain unfeasible base relations by exploiting singleton checks. Further, we show that the closure that is obtained by our algorithm is incomparable to the one that is entailed by partial -consistency and non-unique in general. We demonstrate the efficiency of our algorithm via an experimental evaluation with random Interval Algebra networks from the phase transition region of two separate models and, moreover, show that it can exhibit very similar pruning capability for such networks to the one of an algorithm for enforcing partial -consistency.

CP solvers predominantly use arc consistency (AC) as the default propagation method. Many stronger consistencies, such as triangle consistencies (e.g. RPC and maxRPC) exist, but their use is limited despite results showing that they outperform AC on many problems. This is due to the intricacies involved in incorporating them into solvers. On the other hand, singleton consistencies such as SAC can be easily crafted into solvers but they are too expensive. We seek a balance between the efficiency of triangle consistencies and the ease of implementation of singleton ones. Using the recently proposed variant of SAC called Neighborhood SAC as basis, we propose a family of weaker singleton consistencies. We study them theoretically, comparing their pruning power to existing consistencies. We make a detailed experimental study using a very simple algorithm for their implementation. Results demonstrate that they outperform the existing propagation techniques, often by orders of magnitude, on a wide range of problems.

Partial singleton closure under weak composition, or partial singleton (weak) path-consistency for short, is essential for approximating satisfiability of qualitative constraints networks. Briefly put, partial singleton path-consistency ensures that each base relation of each of the constraints of a qualitative constraint network can define a singleton relation in the corresponding partial closure of that network under weak composition, or in its corresponding partially (weak) path-consistent subnetwork for short. In particular, partial singleton path-consistency has been shown to play a crucial role in tackling the minimal labeling problem of a qualitative constraint network, which is the problem of finding the strongest implied constraints of that network. In this paper, we propose a stronger local consistency that couples partial singleton path-consistency with the idea of collectively deleting certain unfeasible base relations by exploiting singleton checks. We then propose an efficient algorithm for enforcing this consistency that, given a qualitative constraint network, performs fewer constraint checks than the respective algorithm for enforcing partial singleton path-consistency in that network. We formally prove certain properties of our new local consistency, and motivate its usefulness through demonstrative examples and a preliminary experimental evaluation with qualitative constraint networks of Interval Algebra.

Preference reasoning is a central problem in decision support. There exist various ways to interpret a set of qualitative preferences. Conditional preference logics allow to deal with semantics such as optimistic, pessimistic, strong or not. In this paper, we study the complexity of the main problems in optimistic/pessimistic preference logic: undominated, consistency and dominance. We show that they are all NP-hard in general, with some becoming polynomial under specific semantics. Our second contribution is to show that the dominance problem, which has an online component in its definition, is compilable to polynomial time.

We propose two local consistencies that extend bounds consistency (BC) by simultaneously considering combinations of constraints as opposed to single constraints. We prove that these two local consistencies are both stronger than BC, but are NP-hard to enforce even when constraints are linear. Hence, we propose two polynomial-time techniques to enforce approximations of these two consistencies on linear constraints. One is a reformulation of the constraints on which we enforce BC whereas the other is a polynomial time algorithm. Both achieve stronger pruning than BC. Our experiments show large differences in favor of our approaches.

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

Table constraints are very important in constraint programming as they are present in many real problems from areas such as configuration and databases. As a result, numerous specialized algorithms that achieve generalized arc consistency (GAC) on table constraints have been proposed. Since these algorithms achieve GAC, they operate on one constraint at a time. In this paper we propose an efficient algorithm for table constraints that achieves a stronger local consistency than GAC. This algorithm, called maxRPWC+, is based on the local consistency maxRPWC and allows the efficient handling of intersecting table constraints. Experimental results from benchmark problems demonstrate that maxRPWC+ is clearly more robust than a state-of-the-art GAC algorithm in classes of problems with interleaved table constraints, being orders of magnitude faster in some of these classes.

Despite the advancements in constraint propagation methods, most CP solvers still apply fixed predetermined propagators on each constraint of the problem. However, selecting the appropriate propagator for a constraint can be a difficult task that requires expertise. One way to overcome this is through the use of machine learning. A different approach uses heuristics to dynamically adapt the propagation method during search. The heuristics of this category proposed in [1] displayed promising results, but their evaluation and application suffered from two important drawbacks: They were only defined and tested on binary constraints and they required calibration of their input parameters. In this paper we follow this line of work by describing and evaluating simple, fully automated heuristics that are applicable on constraints of any arity. Experimental results from various problems show that the proposed heuristics can outperform a standard approach that applies a preselected propagator on each constraint resulting in an efficient and robust solver.