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.
the SEQUENCE constraint is useful in modelling car sequencing, rostering, scheduling and related problems. We introduce half a dozen new encodings of the SEQUENCE constraint, some of which do not hinder propagation. W...
详细信息
ISBN:
(纸本)9783540749691
the SEQUENCE constraint is useful in modelling car sequencing, rostering, scheduling and related problems. We introduce half a dozen new encodings of the SEQUENCE constraint, some of which do not hinder propagation. We prove that, down a branch of a search tree, domain consistency can be enforced on the SEQUENCE constraint in just O(n(2) log n) time. this improves upon the previous bound of O(n(3)) for each call down the tree. We also consider a generalization of the SEQUENCE constraint - the Multiple SEQUENCE constraint. Our experiments suggest that, on very large and tight problems, domain consistency algorithms are best. However, on smaller or looser problems, much simpler encodings are better, even though these encodings hinder propagation. When there are multiple SEQUENCE constraints, a more expensive propagator shows promise.
Several models based on constraintprogramming have been proposed to solve the traveling salesman problem (TSP). the most efficient ones, such as the weighted circuit constraint (WCC), mainly rely on the Lagrangian re...
详细信息
ISBN:
(纸本)9783030300487
Several models based on constraintprogramming have been proposed to solve the traveling salesman problem (TSP). the most efficient ones, such as the weighted circuit constraint (WCC), mainly rely on the Lagrangian relaxation of the TSP, based on the search for spanning tree or more precisely "1-tree". the weakness of these approaches is that they do not include enough structural constraints and are based almost exclusively on edge costs. the purpose of this paper is to correct this drawback by introducing the Hamiltonian cycle constraint associated with propagators. We propose some properties preventing the existence of a Hamiltonian cycle in a graph or, conversely, properties requiring that certain edges be in the TSP solution set. Notably, we design a propagator based on the research of k-cutsets. the combination of this constraint withthe WCC constraint allows us to obtain, for the resolution of the TSP, gains of an order of magnitude for the number of backtracks as well as a strong reduction of the computation time.
We present a method for solving weighted constraint Satisfaction Problems, based on translation into a constraint Optimization Problem and iterative calls to an SMT solver, with successively tighter bounds of the obje...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
We present a method for solving weighted constraint Satisfaction Problems, based on translation into a constraint Optimization Problem and iterative calls to an SMT solver, with successively tighter bounds of the objective function. the novelty of the method herewith described lies in representing the bound constraint as a shared Binary Decision Diagram, which in turn is translated into SAT. this offers two benefits: first, BDDs built for previous bounds can be used to build the BDDs for new (tighter) bounds, considerably reducing the BDD construction time;second, as a by-product, many clauses asserted to the solver in previous iterations can be reused. the reported experimentation on the WSimply system shows that this technique has better performance in general than other methods implemented in the system. Moreover, withthe new technique WSimply outperforms some state-of-the-art solvers in most of the studied instances.
this paper revisits the tree constraint introduced in [2] which partitions the nodes of a n-nodes, m-arcs directed graph into a set of node-disjoint anti-arborescences for which only certain nodes can be tree roo...
详细信息
Stream constraintprogramming is a recent addition to the family of constraintprogramming frameworks, where variable domains are sets of infinite streams over finite alphabets. Previous works showed promising results...
详细信息
ISBN:
(数字)9783319983349
ISBN:
(纸本)9783319983349;9783319983332
Stream constraintprogramming is a recent addition to the family of constraintprogramming frameworks, where variable domains are sets of infinite streams over finite alphabets. Previous works showed promising results for its applicability to real-world planning and control problems. In this paper, motivated by the modelling of planning applications, we improve the expressiveness of the framework by introducing (1) the "until" constraint, a new construct that is adapted from Linear Temporal Logic and (2) the @ operator on streams, a syntactic sugar for which we provide a more efficient solving algorithm over simple desugaring. For both constructs, we propose corresponding novel solving algorithms and prove their correctness. We present competitive experimental results on the Missionaries and Cannibals logic puzzle and a standard path planning application on the grid, by comparing with Apt and Brand's method for verifying eventuality conditions using a cp approach.
In this paper we describe a constraint Seeker application which provides a web interface to search for global constraints in the global constraint catalog, given positive and negative, fully instantiated (ground) exam...
详细信息
It is well known that the constraint satisfaction problem over general relational structures can be reduced in polynomial time to digraphs. We present a simple variant of such a reduction and use it to show that the a...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
It is well known that the constraint satisfaction problem over general relational structures can be reduced in polynomial time to digraphs. We present a simple variant of such a reduction and use it to show that the algebraic dichotomy conjecture is equivalent to its restriction to digraphs and that the polynomial reduction can be made in logspace. We also show that our reduction preserves the bounded width property, i.e., solvability by local consistency methods. We discuss further algorithmic properties that are preserved and related open problems.
In this paper, we describe a constraintprogramming (cp) route finding application for a container transportation company. Mathematically, this amounts to finding the k shortest paths in a directed graph. However the ...
详细信息
Many cumulative problems are such that the horizon is fixed and cannot be delayed. In this situation, it often occurs that all the activities cannot be scheduled without exceeding the capacity at some points in time. ...
详细信息
暂无评论