Search

This paper proposes a new hybrid encoding of finite linear CSP to SAT which integrates order and log encodings. The former maintains bound consistency by unit propagation and works well for constraints consisting of small/middle sized arity and variable domains. The latter generates smaller CNF and works well for constraints consisting of larger sized arity and variable domains but its performance is not good in general because more inference steps are required to ripple carries. This paper describes the first attempt of hybridizing the order and log encodings without channeling constraints. Each variable is encoded by either the order encoding or the log encoding, and each constraint can contain both types of variables. Using the CSP solver competition benchmark consisting of 1458 instances, we made a comparison between the order, log and proposed hybrid encodings. As a result, the hybrid encoding solves the largest number of instances with the shortest CPU time. We also made a comparison with the four state-of-the-art CSP and SMT solvers Mistral, Opturion CPX, Yices, and z3. In this comparison, the hybrid encoding also shows the best performance. Furthermore, we found that the hybrid encoding is especially superior than other solvers for instances containing disjunctive constraints and global constraints - it indeed solves more instances than the virtual best solver consisting of those four state-of-the-art systems. [ABSTRACT FROM AUTHOR]

A constraint satisfaction problem (CSP) is, in its most general form, an NP-complete problem. One of the several classes of tractable problems that exist contains all the problems with a restricted structure of the constraint scopes. This paper studies community structure, a particular type of restricted structure underpinning a class of tractable SAT problems with potentially similar relevance to CSPs. Using the modularity, it explores the community structure of a wide variety of problems with both academic and industrial relevance. Its impact on the search times of several general solvers, as well as one that uses tree-decomposition, is also analysed to determine whether constraint solvers exploit this type of structure. Nearly all CSP instances have a strong community structure, and those belonging to the same class have comparable modularity values. For the general solvers, strong correlations between the community structure and the search times are not apparent. A more definite correlation exists between the modularity and the search times of the tree-decomposition, suggesting that it might, in part, be able to take advantage of the community structure. However, combined with the relatively strong correlation between the modularity and the tree-width, it could also indicate a similarity between these two measures. [ABSTRACT FROM AUTHOR]

Maintaining local consistencies can improve the efficiencies of the search algorithms solving constraint satisfaction problems (CSPs). Comparing with arc consistency which is the most widely used local consistency, stronger local consistencies can make the search space smaller while they require higher computational cost. In this paper, we make an attempt on the compromise between the pruning ability and the computational cost. A new local consistency called singleton strong bound consistency (SSBC) and its light version, light SSBC, are proposed. The search algorithm maintaining light SSBC can outperform MAC on a considerable number of problems. [ABSTRACT FROM AUTHOR]

Mining frequent tree patterns from tree databases has practical importance in domains like Web mining, Bioinformatics, and so on. Although there have been algorithms on efficient tree mining, these algorithms are often lack of the interpretability in that they often produce a huge number of patterns, most of which are meaningless to users. This paper aims at both demands, one with respect to computational cost, which is efficient generation of tree patterns, and another one with respect to the interpretability. This task requires an efficient method to incorporate the users' needs into mining process. We propose a new top-down method for mining unordered closed tree patterns from a database of trees such that every mined pattern must contain a common piece of information in the form of a tree specified by the user. This type of mining is called mining with subtree constraint which would be useful, for example, inWeb mining and Bioinformatics, where users want to extract common patterns around some given information from original data. The proposed algorithm is tested and compared with a state-of-the-art tree mining algorithm on real and artificial datasets with very good results. [ABSTRACT FROM AUTHOR]

When interacting with constraint-based recommender applications, users describe their preferences with the goal of identifying the products that fit their wishes and needs. In such a scenario, users are repeatedly adapting and changing their requirements. As a consequence, situations occur where none of the products completely fulfils the given set of requirements and users need a support in terms of an indicator of minimal sets of requirements that need to be changed in order to be able to find a recommendation. The identification of such minimal sets relies heavily on the existence of (minimal) conflict sets. In this paper we introduce BFX (Boosted FastXplain), a conflict detection algorithm which exploits the basic structural properties of constraint-based recommendation problems. BFX shows a significantly better performance compared to existing conflict detection algorithms. In order to demonstrate the performance of BFX, we report the results of a comparative performance evaluation. [ABSTRACT FROM AUTHOR]

This paper presents an original dynamic subsumption technique for Boolean CNF formulae. It exploits simple and sufficient conditions to detect, during conflict analysis, clauses from the formula that can be reduced by subsumption. During the learnt clause derivation, and at each step of the associated resolution process, checks for backward subsumption between the current resolvent and clauses from the original formula are efficiently performed. The resulting method allows the dynamic removal of literals from the original clauses. Experimental results show that the integration of our dynamic subsumption technique within the state-of-the-art SAT solvers Minisat and Rsat particularly benefits to crafted problems. [ABSTRACT FROM AUTHOR]

When a practical problem can be modeled as a constraint satisfaction problem (CSP), which is a set of constraints that need to be satisfied, it can be solved using many constraint programming techniques. In many practical applications, while users can recognize examples of where a CSP should be satisfied or violated, they cannot articulate the specification of the CSP itself. In these situations, it can be helpful if the computer can take an active role in learning the CSP from examples of its solutions and non-solutions. This is called constraint acquisition. This paper introduces a framework for constraint acquisition in which one can uniformly define and formulate constraint acquisition problems of different types as optimization problems. The difference between constraint acquisition problems within the framework is not only in the type of constraints that need to be acquired but also in the learning objective. The generic framework can be instantiated to obtain specific formulations for acquiring classical, fuzzy, weighted or probabilistic constraints. The paper shows as an example how recent techniques for acquiring classical constraints can be directly obtained from the framework. Specifically, the formulation obtained from the framework to acquire classical CSPs with the minimum number of violated examples is equivalent to a simple pseudo-boolean optimization problem, thus being efficiently solvable by using many available optimization tools. The paper also reports empirical results on constraint acquisition methods to show the utility of the framework. [ABSTRACT FROM AUTHOR]

Precedence constraints specify that an activity must finish before another activity starts and hence such constraints play a crucial role in planning and scheduling problems. Many real-life problems also include dependency constraints expressing logical relations between the activities – for example, an activity requires presence of another activity in the plan. For such problems a typical objective is a maximization of the number of activities satisfying the precedence and dependency constraints. In the paper we propose new incremental filtering rules integrating propagation through both precedence and dependency constraints. We also propose a new filtering rule using the information about the requested number of activities in the plan. We demonstrate efficiency of the proposed rules on log-based reconciliation problems and min-cutset problems. [ABSTRACT FROM AUTHOR]

Recent advances in solving constraint satisfaction problems (CSPs) and heuristic search have made it possible to solve classical planning problems significantly faster. There is an increasing amount of work on extending these advances to solving planning problems in more expressive languages. These problems and languages contain metric time, quantifiers and resource quantities. SAT-based approaches are very effective at optimal planning. In this paper we report on SAT-based temporal planner T-SATPLAN. One key challenge in the development of planners casting planning as SAT or CSP is the identification of constraints which are satisfied if and only if there is a plan of k steps. In this paper we show how such a SAT encoding can be synthesized for temporal planning. As part of this, we generalize explanatory frame axioms for two states of fluents (true, false) to three states of fluents (true, false and undefined). We show how this SAT encoding can be simplified. We discuss two additional SAT encodings of temporal planning. The encoding schemes make it easier to exploit progress in SAT and CSP solving to solve temporal planning problems. We also report on an experimental evaluation of T-SATPLAN using one such encoding scheme. The evaluation shows that significantly large SAT encodings of temporal planning problems can be solved extremely fast. [ABSTRACT FROM AUTHOR]

We study in this paper the partitioning of the constraints of a temporal planning problem by subgoals, their sequential evaluation before parallelizing the actions, and the resolution of inconsistent global constraints across subgoals. Using an ℓ1-penalty formulation and the theory of extended saddle points, we propose a global-search strategy that looks for local minima in the original-variable space of the ℓ1-penalty function and for local maxima in the penalty space. Our approach improves over a previous scheme that partitions constraints along the temporal horizon. The previous scheme leads to many global constraints that relate states in adjacent stages, which means that an incorrect assignment of states in an earlier stage of the horizon may violate a global constraint in a later stage of the horizon. To resolve the violated global constraint in this case, state changes will need to propagate sequentially through multiple stages, often leading to a search that gets stuck in an infeasible point for an extended period of time. In this paper, we propose to partition all the constraints by subgoals and to add new global constraints in order to ensure that state assignments of a subgoal are consistent with those in other subgoals. Such an approach allows the information on incorrect state assignments in one subgoal to propagate quickly to other subgoals. Using MIPS as the basic planner in a partitioned implementation, we demonstrate significant improvements in time and quality in solving some PDDL2.1 benchmark problems. [ABSTRACT FROM AUTHOR]

In this paper we present a new method that uses data-flow coherence constraints in definite logic program generation. We outline three main advantages of these constraints supported by our results: i) drastically pruning the search space (around 90%), ii) reducing the set of positive examples and reducing or even removing the need for the set of negative examples, and iii) allowing the induction of predicates that are difficult or even impossible to generate by other methods. Besides these constraints, the approach takes into consideration the program termination condition for recursive predicates. The paper outlines some theoretical issues and implementation aspects of our system for automatic logic program induction. [ABSTRACT FROM AUTHOR]

This paper proposes a new hybrid encoding of finite linear CSP to SAT which integrates order and log encodings. The former maintains bound consistency by unit propagation and works well for constraints consisting of small/middle sized arity and variable domains. The latter generates smaller CNF and works well for constraints consisting of larger sized arity and variable domains but its performance is not good in general because more inference steps are required to ripple carries. This paper describes the first attempt of hybridizing the order and log encodings without channeling constraints. Each variable is encoded by either the order encoding or the log encoding, and each constraint can contain both types of variables. Using the CSP solver competition benchmark consisting of 1458 instances, we made a comparison between the order, log and proposed hybrid encodings. As a result, the hybrid encoding solves the largest number of instances with the shortest CPU time. We also made a comparison with the four state-of-the-art CSP and SMT solvers Mistral, Opturion CPX, Yices, and z3. In this comparison, the hybrid encoding also shows the best performance. Furthermore, we found that the hybrid encoding is especially superior than other solvers for instances containing disjunctive constraints and global constraints - it indeed solves more instances than the virtual best solver consisting of those four state-of-the-art systems. [ABSTRACT FROM AUTHOR]

The present paper applies a heuristic and genetic algorithms approaches to the path planning problem for Unmanned Aerial Vehicles (UAVs), during an emergency landing, without putting at risk people and properties. The path re-planning can be caused by critical situations such as equipment failures or extreme environmental events, which lead the current UAV mission to be aborted by executing an emergency landing. This path planning problem is introduced through a mathematical formulation, where all problem constraints are properly described. Planner algorithms must define a new path to land the UAV following problem constraints. Three path planning approaches are introduced: greedy heuristic, genetic algorithm and multi-population genetic algorithm. The greedy heuristic aims at quickly find feasible paths, while the genetic algorithms are able to return better quality solutions within a reasonable computational time. These methods are evaluated over a large set of scenarios with different levels of diffculty. Simulations are also conducted by using FlightGear simulator, where the UAV's behaviour is evaluated for different wind velocities and wind directions. Statistical analysis reveal that combining the greedy heuristic with the genetic algorithms is a good strategy for this problem. [ABSTRACT FROM AUTHOR]

A scalable, reactive and easy to evolve reasoning mechanism is essential for the success of automated smart environments, augmented with a large number of sensors and actuators. While constraint satisfaction problem (CSP) model is applicable for modelling decision making in such environments, the straightforward representation of the model as a CSP leads to a great number of excessive calculations. In this paper, we propose a method of modelling the task as a Dynamic CSP in a way that avoids unnecessary recalculations with new events in the environment. We present a Dependency Graph data structure, which not only allows to reduce CSP search space for every consecutive sensor event by detecting only affected parts of the environment, but also allows to give enough information to users of the system to specify the exact reasons of system's decisions, even with a large number of constraints. We formally prove that partial recalculation of affected parts still keeps the full environment globally satisfied and globally optimal. The evaluation of the system in the living lab showed real-time responses for all events. Additional simulated performance experiments showed that the Dependency Graph approach consistently outperforms the straightforward CSP representation. The experiments also showed that the clusterization of the environment has a noticeable effect on the performance, with highly clusterized environments requiring less computations. [ABSTRACT FROM AUTHOR]

Many machine learning applications rely on learning distance functions with side information. Most of these distance metric learning approaches learns a Mahalanobis distance. While these approaches may work well when data is in low dimensionality, they become computationally expensive or even infeasible for high dimensional data. In this paper, we propose a novel method of learning nonlinear distance functions with side information while clustering the data. The new semi-supervised clustering approach is called Semi-Supervised Fuzzy clustering with Learnable Cluster dependent Kernels (SS-FLeCK). The proposed algorithm learns the underlying cluster-dependent dissimilarity measure while finding compact clusters in the given data set. The learned dissimilarity is based on a Gaussian kernel function with cluster dependent parameters. This objective function integrates penalty and reward cost functions. These cost functions are weighted by fuzzy membership degrees. Moreover, they use side-information in the form of a small set of constraints on which instances should or should not reside in the same cluster. The proposed algorithm uses only the pairwise relation between the feature vectors. This makes it applicable when similar objects cannot be represented by a single prototype. Using synthetic and real data sets, we show that SS-FLeCK outperforms several other algorithms. [ABSTRACT FROM AUTHOR]

Rule engines, business rule management systems and other rule-based systems used today widely utilize methods, techniques and technologies from the era of expert systems. Unfortunately, this doesn't seem to be the case when it comes to explanation facilities. Nowadays, the use of explanation facilities seems more important than ever. Business rule management systems control or constrain the behavior of business processes through business rules and an explanation of the inference process intended for the end user would be more than welcome. An explanation facility framework which was created in order to remedy this situation is presented in this paper. It is written in Java and is supposed to be a generic solution for modern rule-based systems. Besides being free and open-source, it is simple to use and can generate explanations in the form of natural language like sentences. Internationalization is also supported and explanations can be saved as textual, XML or PDF reports. [ABSTRACT FROM AUTHOR]

Crossword puzzles are used everyday by millions of people for entertainment, but have applications also in educational and rehabilitation contexts. Unfortunately, the generation of ad-hoc puzzles, especially on specific subjects, typically requires a great deal of human expert work. This paper presents the architecture of WebCrow-generation, a system that is able to generate crosswords with no human intervention, including clue generation and crossword compilation. In particular, the proposed system crawls information sources on the Web, extracts definitions from the downloaded pages using state-of-the-art natural language processing techniques and, finally, compiles the crossword schema with the extracted definitions by constraint satisfaction programming. The system has been tested on the creation of Italian crosswords, but the extensive use of machine learning makes the system easily portable to other languages. [ABSTRACT FROM AUTHOR]

In this paper we introduce a new cardinality constraint: Ordered Distribute. Given a set of variables, this constraint limits for each value v the number of times v or any value greater than v is taken. It extends the global cardinality constraint, that constrains only the number of times a value v is taken by a set of variables and does not consider at the same time the occurrences of all the values greater than v. We design an algorithm for achieving generalized arc-consistency on Ordered Distribute, with a time complexity linear in the sum of the number of variables and the number of values in the union of their domains. In addition, we give some experiments showing the advantage of this new constraint for problems where values represent levels whose overrunning has to be under control. Finally, we present three extensions of our constraint that can be particularly useful in practice. [ABSTRACT FROM AUTHOR]

In many situations, an explanation of the reasons behind inconsistency in an overconstrained CSP is required. This explanation can be given in terms of minimal unsatisfiable subsets (MUSes) of constraints. This paper presents algorithms for finding minimal unsatisfiable subsets (MUSes) of constraints in overconstrained CSPs with finite domains and binary constraints. The approach followed is to generate subsets in the subset space, test them for consistency and record the inconsistent subsets found. We present three algorithms as variations of this basic approach. Each algorithm generates subsets in the subset space in a different order and curtails search by employing various search pruning mechanisms. The proposed algorithms are anytime algorithms: a time limit can be set on an algorithm's search and the algorithm can be made to find a subset of MUSes. Experimental evaluation of the proposed algorithms demonstrates that they perform two to three orders of magnitude better than the existing indirect algorithms. Furthermore, the algorithms are able to find MUSes in large CSP benchmarks. [ABSTRACT FROM AUTHOR]

In this paper a new learning scheme for SAT is proposed. The originality of our approach arises from its ability to achieve clause learning even if no conflict occurs. This kind of learning from successes clearly contrasts with all the traditional learning approaches which generally refer to conflict analysis. To make such learning possible, relevant clauses, taken from the satisfied part of the formula are conjointly used with the classical implication graph to derive new and more powerful reasons for the implication of a given literal. Based on this extension a first learning scheme called Learning for Dynamic Assignments Reordering (LDAR) is proposed. It exploits the new derived reasons to dynamically reorder partial assignments. Experimental results show that the integration of LDAR within a state-of-the-art SAT solver achieves interesting improvements particularly on satisfiable instances. [ABSTRACT FROM AUTHOR]

Today's supply chains increasingly involve complex sets of processes, objectives and constraints, and therefore agent-based architectures for supply chain management (SCM) become much more difficult to implement and maintain. The paper presents a multi-agent architecture for specifying, analyzing and developing SCM systems, in which asynchronous teams (A-Team) of problem solving agents exchange results within populations that provide effective management of information flows in supply chains, and cooperate to produce sets of non-dominated solutions that show the tradeoffs between objectives. Our approach distinguishes itself by improving problem-solving efficiency based on a diverse set of algorithms without complicated synthesis efforts, removing the focus from agent communication and coordination details, and improving reusability, flexibility and extensibility by supporting object-oriented and component-based programming style. We examine the effectiveness of the architecture through a real-world case study and experimental results. [ABSTRACT FROM AUTHOR]

Backtracking search is often the method of choice for solving constraint satisfaction and propositional satisfiability problems. Previous studies have shown that portfolios of backtracking algorithms — a selection of one or more algorithms plus a schedule for executing the algorithms — can dramatically improve performance on some instances. In this paper, we consider a setting that often arises in practice where the instances to be solved arise over time, the instances all belong to some class of problem instances, and a limit or deadline is placed on the computational resources that can be consumed in solving any instance. For such a scenario, we present a simple scheme for learning a good portfolio of backtracking algorithms from a small sample of instances. We demonstrate the effectiveness of our approach through an extensive empirical evaluation using two testbeds: real-world instruction scheduling problems and the widely used quasigroup completion problems. [ABSTRACT FROM AUTHOR]

In this paper we present a radical approach to obtaining a backtrack-free representation for a constraint satisfaction problem: remove values that lead to dead-ends. This technique does not require additional space but has the drawback of removing solutions. We investigate a number of variations on the basic algorithm including the use of seed solutions, consistency techniques, and a variety of pruning heuristics. Our experimental results indicate that a significant proportion of the solutions to the original problem can be retained especially when an optimization algorithm that specifically searches for such “good” backtrack-free representations is employed. Further extensions increase solution retention by searching for high-coverage backtrack-free representations, by removing tuples rather than values, and by combining multiple backtrack-free representations. Our approach elucidates, for the first time, a three-way trade-off between space complexity, potential backtracks, and solution loss and enables algorithms that can actively reason about the trade-off between space, backtracks, and solution loss. [ABSTRACT FROM AUTHOR]

When a Constraint Satisfaction Problem (CSP) admits no solution, it can be useful to pinpoint which constraints are actually contradicting one another and make the problem infeasible. In this paper, a recent heuristic-based approach to compute infeasible minimal subparts of discrete CSPs, also called Minimally Unsatisfiable Cores (MUCs), is improved. The approach is based on the heuristic exploitation of the number of times each constraint has been falsified during previous failed search steps. It appears to enhance the performance of the initial technique, which was the most efficient one until now. [ABSTRACT FROM AUTHOR]

The Quantified Constraint Satisfaction Problem (QCSP) is an extension of the CSP that can be used to model combinatorial problems containing contingency or uncertainty. It allows for universally quantified variables that can model uncertain actions and events, such as the unknown weather for a future party, or an opponent's next move in a game. Although interest in QCSPs is increasing in recent years, the development of techniques for handling QCSPs is still at an early stage. For example, although it is well known that local consistencies are of primary importance in CSPs, only arc consistency has been extended to quantified problems. In this paper we contribute towards the development of solution methods for QCSPs in two ways. First, by extending directional arc and path consistency, two popular local consistencies in constraint satisfaction, to the quantified case and proposing an algorithm that achieves these consistencies. Second, by showing how value ordering heuristics can be utilized to speed up computation in QCSPs. We study the impact of preprocessing QCSPs with value reordering and directional quantified arc and path consistency by running experiments on randomly generated problems. Results show that our preprocessing methods can significantly speed up the QCSP solving process, especially on hard instances from the phase transition region. [ABSTRACT FROM AUTHOR]

The adaptation of software technology to distributed environments is an important challenge today. In this work we combine parallel and distributed search. By this way we add the potential speed-up of a parallel exploration in the processing of distributed problems. This paper extends DIBT, a distributed search procedure operating in distributed constraint networks. The extension is threefold. First, the ordered hierarchies used during backtracking are extended to remove partial orders. Second the procedure is updated to face delayed information problems upcoming in heterogeneous systems. Third, the search is extended to simultaneously explore independent parts of a distributed search tree. The first and third points were first presented in 1999. The third improvement introduces parallelism into distributed search, which brings to Interleaved Distributed Intelligent BackTracking (IDIBT). Our results show that 1) insoluble problems do not greatly degrade performance over DIBT and 2) super-linear speed-up can be achieved when the distribution of solutions is non-uniform. [ABSTRACT FROM AUTHOR]

Recently, efficient algorithms have been proposed to achieve arc- and path-consistencey in constraint networks. For example, for arc-consistency, there are linear time algorithms (in the size of the problem) which are efficient in practice (e.g. AC-6 and AC-7). The best path-consistency algorithm proposed is PC-{5|6} which is a natural generalization of AC-6 to path-consistency. While its theoretical complexity is the best, experimentations show clearly that it is not very efficient in practice. In this paper, we propose two algorithms, one for arc-consistency, AC-8, and the second for path-consistency, PC-8. These algorithms are based on the same principle: to exploit minimal supports as AC-6 and PC-{5|6} do, but without recording them. While for AC-8, this approach is of limited interest, we show that for path-consistency, this new approach allows to outperform significantly existing algorithms. [ABSTRACT FROM AUTHOR]

Constraint Satisfaction Problems (CSPs) offer a powerful framework for representing a great variety of problems. The difficulty is that most of the requests associated with CSPs are NP-hard. When these requests have to be addressed online, Multivalued Decision Diagrams (MDDs) have been proposed as a way to compile CSPs. In the present paper, we draw a compilation map of MDDs, in the spirit of the NNF compilation map, analyzing MDDs according to their succinctness and to their tractable transformations and queries. Deterministic ordered MDDs are a generalization of ordered binary decision diagrams to non-Boolean domains: unsurprisingly, they have similar capabilities. More interestingly, our study puts forward the interest of non-deterministic ordered MDDs: when restricted to Boolean domains, they capture OBDDs and DNFs as proper subsets and have performances close to those of DNNFs. The comparison to classical, deterministic MDDs shows that relaxing the determinism requirement leads to an increase in succinctness and allows more transformations to be satisfied in polynomial time (typically, the disjunctive ones). Experiments on random problems confirm the gain in succinctness. [ABSTRACT FROM AUTHOR]

This paper presents a hybrid algorithm that combines local search and constraint programming techniques to solve a network routing problem. The problem considered is that of routing traffic demands from a set of requests over a network with limited capacity so as to minimise the cost of any unrouted demands. The hybridisation is twofold: pure local search is used to find a good cost bound for a subsequent branch-and-bound optimisation phase, with local search again applied at the nodes of the branch-and-bound search tree. Constraint propagation occurs in the search tree to reduce the domains of the decision variable, using a set of constraints that are independent of the action of local search at the nodes. In contrast to previous constraint programming/local search hybridisations, here local search is used to satisfy the hard problem constraints, while optimisation is handled in the framework of constraint programming. The resulting algorithm is incomplete, but is shown to compare favourably with a complete approach to this problem. [ABSTRACT FROM AUTHOR]

This paper describes work on methods that evaluate algebraic solutions to word problems in physics. Many current tutoring systems rely on substantial scaffolding and consequently require students to completely describe every variable used in the solution. A heuristic, based on constraint propagation, capable of inferring the description of variables (i.e., the possible dimensions and physics concepts) is shown to be highly reliable on three real world data sets, one covering a few problems with a small number of student answers and two others covering a large class of problems (~100) with a large number of student answers (~11,000). The heuristic uniquely determines the dimensions of all the variables in 91–92% of the equation sets. By asking the student for dimension information about one variable, an additional 3% of the sets can be determined. An ITS tutoring system can use this heuristic to reason about a student's answers even when the scaffolding and context are removed. [ABSTRACT FROM AUTHOR]

Dealing with constraints due to obstacles is an important topic in constraint-based spatial clustering. In this paper, we proposed the DBRS_O method to identify clusters in the presence of intersected obstacles. Without doing any preprocessing, DBRS_O processes the constraints during clustering. DBRS_O can also avoid unnecessary computations when obstacles do not affect the clustering result. As well, DBRS_O can find clusters with arbitrary shapes, varying densities, deal with significant non-spatial attributes and handle large datasets. [ABSTRACT FROM AUTHOR]

A general approach to implement propagation and simplification of constraints consists of applying rules over these constraints. However, a difficulty that arises frequently when writing a constraint solver is to determine the constraint propagation algorithm. In previous work, different methods for automatic generation of rule-based solvers for constraints defined over finite domains have been proposed. In this paper, we present a method for generating rule-based solvers for constraint predicates defined by means of a constraint logic program, even when the constraint domain is infinite. [ABSTRACT FROM AUTHOR]

In this paper we describe a paradigm for content-focused matchmaking, based on a recently proposed model for constraint acquisition and satisfaction. Matchmaking agents are conceived as constraint-based solvers that interact with other, possibly human, agents (Customers). The Matchmaker provides potential solutions ("suggestions") based on partial knowledge, while gaining further information about the problem itself from the other agent through the latter's evaluation of these suggestions. The dialogue between Matchmaker and Customer results in iterative improvement of solution quality, as demonstrated in simple simulations. We also show empirically that this paradigm supports "suggestion strategies" for finding acceptable solutions more efficiently or for increasing the amount of information obtained from the Customer. This work also indicates some ways in which the tradeoff between these two metrics for evaluating performance can be handled. [ABSTRACT FROM AUTHOR]

Efficient algorithms for checking consistency of a set of spatial constraints among spatiotemporal objects are crucial for many practical application systems needing real-time response. This paper is focused on the consistency for directional spatial constraints in a two-dimensional Euclidean space, which is critical in application domains such as geographic information systems, battlefield visualization, transportation, etc. We propose a dimension graph representation to maintain the Euclidean spatial constraints among 2D objects(points, intervals, regions). The basic idea is to project the spatial constraints on both X and Y dimensions, and then to construct a dimension graph on each dimension. The dimension graph representation transforms the problem of consistency checking into the problem of graph cycle detection. Consistency checking for conjunctive constraints can then be achieved in linear time complexity. This approach is much more efficient than competing approaches when there are few disjunctions in the spatial constraints, which are often true in above applications. We also demonstrate that the proposed algorithm can guarantee global consistency. [ABSTRACT FROM AUTHOR]

Automated theorem proving with connection tableau calculi imposes search problems in tremendous search spaces. In this paper, we present a new approach to search space reduction in connection tableau calculi. In our approach structurally similar parts of the search space are compressed by means of disjunctive constraints. We describe the necessary changes of the calculus, and we develop elaborate techniques for an efficient constraint processing. Moreover, we present an experimental evaluation of our approach. [ABSTRACT FROM AUTHOR]

Hard or large-scale constraint satisfaction and optimization problems, occur widely in artificial intelligence and operations research. These problems are often difficult to solve with global search methods, but many of them can be efficiently solved by local search methods. Evolutionary algorithms are local search methods which have considerable success in tackling difficult, or illdefined optimization problems. In contrast they have not been so successful in tackling constraint satisfaction problems. Other local search methods, in particular GENET and EGENET are designed specifically for constraint satisfaction problems, and have demonstrated remarkable success in solving hard examples of these problems. In this paper we examine how we can transfer the mechanisms that were so successful in (E)GENET to evolutionary algorithms, in order to tackle constraint satisfaction algorithms efficiently. An empirical comparison of our evolutionary algorithm improved by mechanisms from EGENET and shows how it can markedly improve on the efficiency of EGENET in solving certain hard instances of constraint satisfaction problems. [ABSTRACT FROM AUTHOR]

RETE match for production systems and Arc Consistency (AC) filtering are two efficient AI algorithms that are designed for particular constraint satisfaction problems (CSP). Interestingly, it is possible to integrate the two within a common framework, and provide RETE with the lookahead advantages of AC. Unfortunately, the resulting quadratic dependence of AC on working memory (WM) size precludes the application of AC to RETE, since RETE responds to incremental changes in WM. Recent results in AC graph factorization, however, reduce the quadratic dependence to just linear for certain classes of problems, including RETE. In this paper, we present RETE and AC within the unified framework of Call-Graph Caching (CGC) evaluation. We describe factored arc consistency (FAC) and its use in an integrated FAC/RETE algorithm that provides RETE match with AC lookahead. We discuss our implementations, promising initial empirical results, and explore FAC/RETE's applicability conditions and extensions. We conclude that incorporating factored AC into RETE match is an interesting and potentially useful application of arc consistency methods to the RETE CSP. [ABSTRACT FROM AUTHOR]

Emergency incidents increase the uncertainty of supply chain environment, and also make the supply chain vulnerability expose. Creating resilient supply chain is an effective way to overcome the supply chain vulnerability. The supply chain characteristics of self-adaptation and self-coordination are consistent with the self-organization feature of ant colony's labor division. In this paper, a generalized ant colony's labor division model with constraints is provided, which is used to construct the ant colony's labor division model with constraints of resilient supply chain to solve task allocation of resilient supply chains. The simulation principle and algorithm of resilient supply chain are provided based on the proposed model and task allocation of the supply chain is analyzed from the five aspects, that is, task allocation status, supply chain coordination, emergency incidents' impact to task allocation, task allocation rate and the influence of different incidents for task allocation. The simulation results show that, with the proposed model, it is effective to allocate resilient supply chain tasks and has excellent performance, such as faster response and robustness. [ABSTRACT FROM AUTHOR]

Domain filtering local consistencies, such as inverse consistencies, that only delete values and do not add new constraints are particularly useful in Constraint Programming. Although many such consistencies for binary constraints have been proposed and evaluated, the situation with non-binary constraints is quite different. Only very recently have domain filtering consistencies stronger than GAC started to attract interest. Following this line of research, we define a number of strong domain filtering consistencies for non-binary constraints and theoretically compare their pruning power. We prove that three of these consistencies are equivalent to maxRPC in binary CSPs while another is equivalent to PIC. We also describe a generic algorithm for domain filtering consistencies in non-binary CSPs. We show how this algorithm can be instantiated to enforce some of the proposed consistencies and analyze the worst-case complexities of the resulting algorithms. Finally, we make a preliminary empirical study. [ABSTRACT FROM AUTHOR]