Efficient constraint propagation is crucial to any constraint solver. We show that watched literals, already a great success in the satisfiability community, can be used to provide highly efficient implementations of ...
详细信息
ISBN:
(纸本)3540462678
Efficient constraint propagation is crucial to any constraint solver. We show that watched literals, already a great success in the satisfiability community, can be used to provide highly efficient implementations of constraint propagators. We describe three important aspects of watched literals as we apply them to constraints, and how they are implemented in the MINION constraint solver. We show three successful applications of to constraint propagators: the sum of Boolean variables;GAC for the 'element' constraint;and GAC for the 'table' constraint.
In this paper we present and evaluate an evolutionary approach for learning new constraint satisfaction algorithms, specifically for MAX-SAT optimisation problems. Our approach offers two significant advantages over e...
详细信息
ISBN:
(纸本)3540292381
In this paper we present and evaluate an evolutionary approach for learning new constraint satisfaction algorithms, specifically for MAX-SAT optimisation problems. Our approach offers two significant advantages over existing methods: it allows the evolution of more complex combinations of heuristics, and;it can identify fruitful synergies among heuristics. Using four different classes of MAX-SAT problems, we experimentally demonstrate that algorithms evolved withthis method exhibit superior performance in comparison to general purpose methods.
tIn this paper we give an overview of applications of constraintprogramming for IP (Internet Protocol) data networks, and discuss the problem of Resilience Analysis in more detail. In this problem we try to predict t...
详细信息
ISBN:
(纸本)3540462678
tIn this paper we give an overview of applications of constraintprogramming for IP (Internet Protocol) data networks, and discuss the problem of Resilience Analysis in more detail. In this problem we try to predict the loading of a network in different failure scenarios, without knowing end-to-end flow values throughout the network;the inference is based only on observed link traffic values. the related problem of Traffic Flow Analysis aims to derive a traffic matrix from the observed link traffic data. this is a severely under-constrained problem, we can show that the obtained flow values vary widely in different, feasible solutions. Experimental results indicate that using the same data much more accurate, bounded results can be obtained for Resilience Analysis.
the problem of finding an optimal solution in a constraint satisfaction problem with preferences has attracted a lot of researchers in Artificial Intelligence in general, and in the constraintprogramming community in...
详细信息
ISBN:
(纸本)9783540859574
the problem of finding an optimal solution in a constraint satisfaction problem with preferences has attracted a lot of researchers in Artificial Intelligence in general, and in the constraintprogramming community in particular. As a consequence, several approaches for expressing and reasoning about satisfiability problems with preferences have been proposed, and viable solutions exist for finding one optimal Solution. However, in many cases, it is not desirable to find just one solution. Indeed, it might be desirable to he able to compute more, and possibly all, optimal solutions, e.g.. for comparatively evaluate them on the basis of other criteria not captured by the preferences. In this paper we present a procedure for computing all optimal solutions of a satisfiability problem with preferences. the procedure is guaranteed to compute all and only the optimal solutions, i.e., models which are not optimal are not even computed.
We propose a new filtering algorithm for the cumulative constraint. It applies the Edge-Finding, the Extended-Edge-Finding and the Time-Tabling rules in O(kn log n) where k is the number of distinct task heights. By a...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
We propose a new filtering algorithm for the cumulative constraint. It applies the Edge-Finding, the Extended-Edge-Finding and the Time-Tabling rules in O(kn log n) where k is the number of distinct task heights. By a proper use of tasks decomposition, it enforces the Time-Tabling rule and the Time-Table Extended-Edge-Finding rule. thus our algorithm improves upon the best known Extended-Edge-Finding propagator by a factor of O(log n) while achieving a much stronger filtering.
We improve an existing propagator for the context-free grammar constraint and demonstrate experimentally the practicality of the resulting propagator. the underlying technique could be applied to other existing propag...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
We improve an existing propagator for the context-free grammar constraint and demonstrate experimentally the practicality of the resulting propagator. the underlying technique could be applied to other existing propagators for this constraint. We argue that constraintprogramming solvers are more suitable than existing solvers for verification tools that have to solve string constraints, as they have a rich tradition of constraints for membership in formal languages.
We propose new filtering algorithms for the SEQUENCE constraint and some extensions of the SEQUENCE constraint based on network flows. We enforce domain consistency on the SEQUENCE constraint in O(n(2)) time down a br...
详细信息
ISBN:
(纸本)9783540859574
We propose new filtering algorithms for the SEQUENCE constraint and some extensions of the SEQUENCE constraint based on network flows. We enforce domain consistency on the SEQUENCE constraint in O(n(2)) time down a branch of the search tree. this improves upon the best existing domain consistency algorithm by a factor of O(log n). the flows used in these algorithms are derived from a linear program. Some of them differ from the flows used to propagate global constraints like GCC since the domains of the variables are encoded as costs on the edges rather than capacities. Such flows are efficient for maintaining bounds consistency over large domains and may be useful for other global constraints.
A kernelization algorithm for a computational problem is a procedure which compresses an instance into an equivalent instance whose size is bounded with respect to a complexity parameter. For the constraint satisfacti...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
A kernelization algorithm for a computational problem is a procedure which compresses an instance into an equivalent instance whose size is bounded with respect to a complexity parameter. For the constraint satisfaction problem (CSP), there exist many results concerning upper and lower bounds for kernelizability of specific problems, but it is safe to say that we lack general methods to determine whether a given problem admits a kernel of a particular size. In this paper, we take an algebraic approach to the problem of characterizing the kernelization limits of NP-hard CSP problems, parameterized by the number of variables. Our main focus is on problems admitting linear kernels, as has, somewhat surprisingly, previously been shown to exist. We show that a finite-domain CSP problem has a kernel with O(n) constraints if it can be embedded (via a domain extension) into a CSP which is preserved by a Maltsev operation. this result utilise a variant of the simple algorithm for Maltsev constraints. In the complementary direction, we give indication that the Maltsev condition might be a complete characterization for Boolean CSPs with linear kernels, by showing that an algebraic condition that is shared by all problems with a Maltsev embedding is also necessary for the existence of a linear kernel unless NP subset of co-NP/poly.
We study a generalization of the constraint satisfaction problem (CSP), the periodic constraint satisfaction problem. An input instance of the periodic CSP is a finite set of "generating" constraints over a ...
详细信息
We study a generalization of the constraint satisfaction problem (CSP), the periodic constraint satisfaction problem. An input instance of the periodic CSP is a finite set of "generating" constraints over a structured variable set that implicitly specifies a larger, possibly infinite set of constraints;the problem is to decide whether or not the larger set of constraints has a satisfying assignment. this model is natural for studying constraint networks consisting of constraints obeying a high degree of regularity or symmetry. Our main contribution is the identification of two broad polynomial-time tractable subclasses of the periodic CSP.
this paper introduces a new velocity tuning approach for autonomous vehicles based on constraintprogramming (CP) over continuous domains. We use CP to compute a safe approximation of configurations where collisions w...
详细信息
ISBN:
(纸本)9783642153952
this paper introduces a new velocity tuning approach for autonomous vehicles based on constraintprogramming (CP) over continuous domains. We use CP to compute a safe approximation of configurations where collisions with obstacles may occur or technological limits may be violated. the use of CP leads to a flexible approach, facilitating the incorporation of new characteristics, e.g., constraints modeling the influence of currents. We illustrate these capabilities offered by CP in the context of UAV missions. Experimental results obtained on actual wind charts are provided.
暂无评论