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 argue that the clp(X) framework is a suitable vehicle for extending logic programming (LP) with probabilistic reasoning. this paper presents such a generic framework, clp(pdf(Y)), and proposes two promising instanc...
详细信息
ISBN:
(纸本)3540202021
We argue that the clp(X) framework is a suitable vehicle for extending logic programming (LP) with probabilistic reasoning. this paper presents such a generic framework, clp(pdf(Y)), and proposes two promising instances. the first provides a seamless integration of Bayesian Networks, while the second defines distributions over variables and employs conditional constraints over predicates. the generic methodology is based on attaching probability distributions over finite domains. We illustrate computational benefits of this approach by comparing program performances with a clp(fd) program on a cryptographic problem.
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.
Linear integer constraints are one of the most important constraints in combinatorial problems since they are commonly found in many practical applications. Typically, encoding linear constraints to SAT performs poorl...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Linear integer constraints are one of the most important constraints in combinatorial problems since they are commonly found in many practical applications. Typically, encoding linear constraints to SAT performs poorly in problems withthese constraints in comparison to constraintprogramming (CP) or mixed integer programming (MIP) solvers. But some problems contain a mix of combinatoric constraints and linear constraints, where encoding to SAT is highly effective. In this paper we define new approaches to encoding linear constraints into SAT, by extending encoding methods for pseudo-Boolean constraints. Experimental results show that these methods are not only better than the state-of-the-art SAT encodings, but also improve on MIP and CP solvers on appropriate problems. Combining the new encoding with lazy decomposition, which during runtime only encodes constraints that are important to the solving process that occurs, gives a robust approach to many highly combinatorial problems involving linear constraints.
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).
this paper investigates the relations among different partial consistencies which have been proposed for pruning the domains of the variables in constraint systems over the real numbers. We establish several propertie...
详细信息
ISBN:
(纸本)3540652248
this paper investigates the relations among different partial consistencies which have been proposed for pruning the domains of the variables in constraint systems over the real numbers. We establish several properties of the filtering achieved by the algorithms based upon these partial consistencies. Especially, we prove that : 1) 2B-Consistency (or Hull consistency) algorithms actually yield a weaker pruning than Box-consistency;2) 3B-Consistency algorithms perform a stronger pruning than Box-consistency. this paper also provides an analysis of boththe capabilities and the inherent limits of the filtering algorithms which achieve these partial consistencies.
Many tasks in automated reasoning can be modeled as weighted constraint satisfaction problems over Boolean variables (Boolean WCSPs). Tractable classes of Such problems have traditionally been identified by exploiting...
详细信息
ISBN:
(纸本)9783540859574
Many tasks in automated reasoning can be modeled as weighted constraint satisfaction problems over Boolean variables (Boolean WCSPs). Tractable classes of Such problems have traditionally been identified by exploiting either: (a) the topology of the associated constraint network, or (b) the structure of the weighted constraints. In this paper, we introduce the notion of a constraint composite graph (CCG) associated with a given (Boolean) WCSP. the CCG provides it unifying framework for characterizing/exploiting boththe graphical structure of the constraint network as well as the structure of the weighted constraints. We show that a given (Boolean) WCSP can be reduced to the problem of computing the minimum weighted vertex cover for its associated CM and we establish the following two important results: ( 1) "the CCG of a given Boolean WCSP has the same treewidth as its associated constraint network," and (2) "many classes of Boolean WCSPs that are tractable by, virtue of the structure of their weighted constraints have associated CCGs that arc bipartite in nature."
Since electromagnetic waves are strongly attenuated inside the water, the satellite based global positioning system (CPS) cannot be used by submarine robots except at the surface of the water. this paper shows that th...
详细信息
ISBN:
(纸本)3540462678
Since electromagnetic waves are strongly attenuated inside the water, the satellite based global positioning system (CPS) cannot be used by submarine robots except at the surface of the water. this paper shows that the localization problem in deep water can often be cast into a continuous constraints satisfaction problem where interval constraints propagation algorithms are particularly efficient. the efficiency of the resulting propagation methods is illustrated on the localization of a submarine robot, named Redermor. the experiments have been collected by the GESMA (Groupe d'Etude Sous-Marine de l'Atlantique) in the Douarnenez bay, in Brittany.
Stochastic constraintprogramming is an extension of constraintprogramming for modelling and solving combinatorial problems involving uncertainty. A solution to such a problem is a policy tree that specifies decision...
详细信息
ISBN:
(纸本)9783642042430
Stochastic constraintprogramming is an extension of constraintprogramming for modelling and solving combinatorial problems involving uncertainty. A solution to such a problem is a policy tree that specifies decision variable assignments in each scenario. Several Solution methods have been proposed but none seems practical for large multi-stage problems. We propose all incomplete approach: specifying a policy tree indirectly by a parameterised function, whose parameter values are found by evolutionary search. On some problems this method is orders of magnitude faster than a state-of-the-art scenario-based approach, and it also provides a very compact representation of policy trees.
暂无评论