this paper presents a novel domain-consistency algorithm which does not maintain supports dynamically during propagation, but rather maintain forbidden values. It introduces the optimal NAC4 (negative AC4) algorithm b...
详细信息
ISBN:
(纸本)9783642153952
this paper presents a novel domain-consistency algorithm which does not maintain supports dynamically during propagation, but rather maintain forbidden values. It introduces the optimal NAC4 (negative AC4) algorithm based on this idea. It further shows that maintaining forbidden values dynamically allows the generic algorithm AC5 to achieve domain consistency in time O(ed) for classes of constraints in which the number of supports is O(d(2)) but the number of forbidden values is O(d). the paper also shows how forbidden values and supports can be used jointly to achieve domain consistency on logical combinations of constraints and to compute validity as well as entailment of constraints. Experimental results show the benefits of the joint exploitation of supports and forbidden values.
VLSI chips design is becoming increasingly complex and calling for more and more automation. Many chip design problems can be formulated is constraint problems and are potentially amenable to CP techniques. To the bes...
详细信息
ISBN:
(纸本)9783642042430
VLSI chips design is becoming increasingly complex and calling for more and more automation. Many chip design problems can be formulated is constraint problems and are potentially amenable to CP techniques. To the best of our knowledge, though there has been little CP work in this domain to date. We describe a successful application of a CP based tool to a particular pin-assignment problem hi which tens of thousands of phis (i.e.;connection points) belonging to internal units on the chip must be placed within their units so as to satisfy certain constraints and optimize the wirability of the design. Our tool has been tested on read IBM designs and is now being integrated into IBM's chip development environment.
In this paper we consider the consistency problem for qualitative constraint networks representing temporal or spatial information. the most efficient method for solving this problem consists in a search algorithm usi...
详细信息
ISBN:
(纸本)9783540749691
In this paper we consider the consistency problem for qualitative constraint networks representing temporal or spatial information. the most efficient method for solving this problem consists in a search algorithm using, on the one hand, the weak composition closure method as a local propagation method, and on the other hand, a decomposition of the constraints into subrelations of a tractable set. We extend this algorithm withthe notion of eligibility and the notion of frozen constraints. the first concept allows to characterise constraints which will not be considered during the search. the second one allows to freeze constraints in order to avoid unnecessary updates.
Objective-CP is an optimization system that views an optimization program as the combination of a model, a search, and a solver. Models in Objective-CP follow the modeling style of constraintprogramming and are concr...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
Objective-CP is an optimization system that views an optimization program as the combination of a model, a search, and a solver. Models in Objective-CP follow the modeling style of constraintprogramming and are concretized into specific solvers. Search procedures are specified in terms of high-level nondeterministic constructs, search combinators, and node selection strategies. Objective-CP supports fully transparent parallelization of multi-start and branch & bound algorithms. the implementation of Objective-CP is based on a sequence of model transformations, followed by a concretization step. Moreover, Objective-CP features a constraint-programming solver following a micro-kernel architecture for ease of maintenance and extensibility. Experimental results show the practicability of the approach.
We investigate utilizing the integer programming (IP) technique of reduced cost fixing to improve maximum satisfiability (MaxSAT) solving. In particular, we show how reduced cost fixing can be used within the implicit...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
We investigate utilizing the integer programming (IP) technique of reduced cost fixing to improve maximum satisfiability (MaxSAT) solving. In particular, we show how reduced cost fixing can be used within the implicit hitting set approach (IHS) for solving MaxSAT. Solvers based on IHS have proved to be quite effective for MaxSAT, especially on problems with a variety of clause weights. the unique feature of IHS solvers is that they utilize both SAT and IP techniques. We show how reduced cost fixing can be used in this framework to conclude that some soft clauses can be left falsified or forced to be satisfied without influencing the optimal cost. Applying these forcings simplifies the remaining problem. We provide an extensive empirical study showing that reduced cost fixing employed in this manner can be useful in improving the state-of-the-art in MaxSAT solving especially on hard instances arising from real-world application domains.
We propose a framework to construct web-oriented user interfaces in a high-level way by exploiting declarative programming techniques. Such user interfaces are intended to manipulate complex data in a type-safe way, i...
详细信息
Covering arrays can be applied to the testing of software, hardware and advanced materials, and to the effects of hormone interaction on gene expression. In this paper we develop constraintprogramming models of the p...
详细信息
Covering arrays can be applied to the testing of software, hardware and advanced materials, and to the effects of hormone interaction on gene expression. In this paper we develop constraintprogramming models of the problem of finding an optimal covering array. Our models exploit global constraints, multiple viewpoints and symmetry-breaking constraints. We show that compound variables, representing tuples of variables in our original model, allow the constraints of this problem to be represented more easily and hence propagate better. With our best integrated model, we are able to either prove the optimality of existing bounds or find new optimal solutions, for arrays of moderate size. Local search on a SAT-encoding of the model is able to find improved solutions and bounds for larger problems.
In this paper we show that the clique concept can be exploited in order to solve Max-CSP. We present a clique inference process which leads to construct linear systems useful for computing new lower bounds. the clique...
详细信息
ISBN:
(纸本)3540462678
In this paper we show that the clique concept can be exploited in order to solve Max-CSP. We present a clique inference process which leads to construct linear systems useful for computing new lower bounds. the clique inference process is introduced in the PFC-MPRDAC [5] algorithm and the obtained algorithm is called PFC-MPRDAC+CBB (CBB for Clique Based Bound). the carried out experiments have shown that PFC-MPRDAC+CBB leads to obtain very encouraging results.
the length-lex representation for set variables orders all subsets of a given universe of values according to cardinality and lexicography. To achieve length-lex bounds consistency for Knapsack constraints it has been...
详细信息
ISBN:
(纸本)9783642042430
the length-lex representation for set variables orders all subsets of a given universe of values according to cardinality and lexicography. To achieve length-lex bounds consistency for Knapsack constraints it has been proposed to decompose the constraint into two sum constraints. We provide theoretical and practical evidence which shows that decomposition increases the problem of computing a fixpoint which is intrinsic to the length-lex representation: 1. the fixpoint problem for this domain representation is NP-hard in general. 2. For a tractable sub-family of Knapsack decomposition takes more time than exponential brute-force enumeration. 3. Experimental results on decomposed Knapsack constraints show that exponential-time fixpoint computation is the rule and not some pathological exception.
Filtering constraint networks to reduce search space is one of the main cornerstones of constraintprogramming and among them (Generalized) Arc Consistency has been the most fundamental. While stronger consistencies a...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Filtering constraint networks to reduce search space is one of the main cornerstones of constraintprogramming and among them (Generalized) Arc Consistency has been the most fundamental. While stronger consistencies are also the subject of considerable attention, none matches GAC's and for this reason it continues to advance at a steady pace and has become the popular choice of consistency for filtering algorithms. In this paper, we build on the success of GAC by proposing a way to transform a constraint network into another such that enforcing GAC on the latter is equivalent to enforcing a stronger consistency on the former. the key idea is to factor out commonly shared variables from constraints' scopes, form new variables, then re-attach them back to the constraints where they come from. Experiments show that this method is inexpensive and outperforms specialized algorithms and other techniques when it comes to full pair-wise consistency (FPWC).
暂无评论