We analyze the complexity of optimization problems expressed using valued constraints. this very general framework includes a number of well-known optimization problems such as MAX-SAT, and WEIGHTED MAX-SAT, as well a...
详细信息
ISBN:
(纸本)3540232419
We analyze the complexity of optimization problems expressed using valued constraints. this very general framework includes a number of well-known optimization problems such as MAX-SAT, and WEIGHTED MAX-SAT, as well as properly generalizing the classical CSP framework by allowing the expression of preferences. We focus on valued constraints over Boolean variables, and we establish a dichotomy theorem which characterizes the complexity of any problem involving a fixed set of constraints of this kind.
It is well known that the Davis-Putnam-Logemann-Loveland (DPLL) algorithm for satisfiability (SAT) can be extended to an algorithm for maximum SAT (max-SAT). In this paper, we propose a number of strategies to signifi...
详细信息
ISBN:
(纸本)3540232419
It is well known that the Davis-Putnam-Logemann-Loveland (DPLL) algorithm for satisfiability (SAT) can be extended to an algorithm for maximum SAT (max-SAT). In this paper, we propose a number of strategies to significantly improve this max-SAT method. the first strategy is a set of unit propagation rules;the second is an effective lookahead heuristic based on linear programming;and the third strategy is a dynamic variable ordering that exploits problem constrainedness during search. We integrate these strategies in an efficient complete solver for both max-SAT and weighted max-SAT. Our experimental results on random problem instances and many instances from SATLIB demonstrate the efficacy of these strategies and show that the new solver is able to significantly outperform most of the existing complete max-SAT solvers, with a few orders of magnitude of improvement in running time in many cases.
Existing random models for the constraint satisfaction problem (CSP) all require an extremely low constraint tightness in order to have non-trivial threshold behaviors and guaranteed hard instances at the threshold. W...
详细信息
ISBN:
(纸本)3540232419
Existing random models for the constraint satisfaction problem (CSP) all require an extremely low constraint tightness in order to have non-trivial threshold behaviors and guaranteed hard instances at the threshold. We study the possibility of designing random CSP models that have interesting threshold and typical-case complexity behaviors while at the same time, allow a much higher constraint tightness. We show that random CSP models that enforce the constraint consistency have guaranteed exponential resolution complexity without putting much restriction on the constraint tightness. A new random CSP model is proposed to generate random CSPs with a high tightness whose instances are always consistent. Initial experimental results are also reported to illustrate the sensitivity of instance hardness to the constraint tightness in classical CSP models and to evaluate the proposed new random CSP model.
the paper introduces the notion of freely completable partial solutions to characterize constraint satisfaction problems that have components which are relatively easy to solve and are only loosely connected to the re...
详细信息
ISBN:
(纸本)3540232419
the paper introduces the notion of freely completable partial solutions to characterize constraint satisfaction problems that have components which are relatively easy to solve and are only loosely connected to the remaining parts of the problem. Discovering such partial solutions during the solution process can result in strongly pruned search trees. We give a general definition of freely completable partial solutions, and then apply it to resource-constrained project scheduling. In this domain, we suggest a heuristic algorithm that is able to construct freely completable partial schedules. the method – together with symmetry breaking applied before search – has been successfully tested on real-life resource-constrained project scheduling problems containing up to 2000 tasks.
A distributed concurrent search algorithm for distributed constraint satisfaction problems (DisCSPs) is presented. Concurrent search algorithms are composed of multiple search processes (SPs) that operate concurrently...
详细信息
ISBN:
(纸本)3540232419
A distributed concurrent search algorithm for distributed constraint satisfaction problems (DisCSPs) is presented. Concurrent search algorithms are composed of multiple search processes (SPs) that operate concurrently and scan non-intersecting parts of the global search space. Search processes are generated dynamically, started by the initializing agent, and by any number of agents during search. In the proposed, ConcDB, algorithm, all search processes perform dynamic backtracking (DB). As a consequence of DB, a search space scanned by one search process can be found unsolvable by a different search process. this enhances the efficiency of the ConcDB algorithm. Concurrent search is an asynchronous distributed algorithm and is shown to be faster than asynchronous backtracking (ABT). the network load of ConcDB is also much lower than that of ABT.
the tightness of a constraint refers to how restricted the constraint is. the existing work shows that there exists a relationship between tightness and global consistency of a constraint network. In this paper, we co...
详细信息
ISBN:
(纸本)3540232419
the tightness of a constraint refers to how restricted the constraint is. the existing work shows that there exists a relationship between tightness and global consistency of a constraint network. In this paper, we conduct a comprehensive study on this relationship. Under the concept of k-consistency (k is a number), we strengthen the existing results by establishing that only some of the tightest, not all, binary constraints are used to predict a number k such that strong k-consistency ensures global consistency of an arbitrary constraint network which may include non-binary constraints. More importantly, we have identified a lower bound of the number of the tightest constraints we have to consider in predicting the number k. To make better use of the tightness of constraints, we propose a new type of consistency: dually adaptive consistency. Under this concept, only the tightest directionally relevant constraint on each variable (and thus in total n - 1 such constraints where n is the number of variables) will be used to predict the level of "consistency" ensuring global consistency of a network.
this article deals with global constraints for which the set of solutions can be recognized by an extended finite automaton whose size is bounded by a polynomial in n, where n is the number of variables of the corresp...
详细信息
ISBN:
(纸本)3540232419
this article deals with global constraints for which the set of solutions can be recognized by an extended finite automaton whose size is bounded by a polynomial in n, where n is the number of variables of the corresponding global constraint. By reformulating the automaton as a conjunction of signature and transition constraints we show how to systematically obtain a filtering algorithm. Under some restrictions on the signature and transition constraints this filtering algorithm achieves arc-consistency. An implementation based on some constraints as well as on the metaprogramming facilities of SICStus Prolog is available. For a restricted class of automata we provide a filtering algorithm for the relaxed case, where the violation cost is the minimum number of variables to unassign in order to get back to a solution.
XML data can be modeled as node-labeled graphs and XML queries can be expressed by structural relationships between labeled elements. XML query evaluation has been addressed using mainly database, and in some cases gr...
详细信息
ISBN:
(纸本)3540232419
XML data can be modeled as node-labeled graphs and XML queries can be expressed by structural relationships between labeled elements. XML query evaluation has been addressed using mainly database, and in some cases graph search, techniques. We propose an alternative method that models and solves such queries as constraint satisfaction problems (CSPs). We describe common constraint types occurring in XML queries and show how query evaluation can benefit from methods for preprocessing and solving CSPs. We identify an important non-binary constraintthat is a common module of XML queries and describe a generalized arc consistency algorithm with low cost that can ensure polynomial query evaluation. Finally, we demonstrate that maintaining the consistency of such non-binary constraints can greatly accelerate search in intractable queries that include referential relationships.
Super solutions, introduced first for SAT problems in [1], are solutions in which, if a small number of variables lose their values, we are guaranteed to be able to repair the solution with only a few changes. In this...
ISBN:
(纸本)3540232419
Super solutions, introduced first for SAT problems in [1], are solutions in which, if a small number of variables lose their values, we are guaranteed to be able to repair the solution with only a few changes. In this paper, we stress the need to extend the super-solution framework along several dimensions to make it more useful practically. For instance, consider the jobshop scheduling problem (jsp). A jsp involves a set of jobs (sequences of activities) and a set of machines. the objective is to schedule the jobs such that no machine is required by two activities that overlap, and the makespan is minimized. A jsp can be formulated as a CSP, with one variable for each activity, and a domain size equal to the makespan minus its duration. To find the minimal makespan, one starts withthe makespan equal to a lower bound and increase it till a solution exists.
作者：
Golden, KPang, WLNASA
Computat Sci Div Ames Res Ctr Moffett Field CA 94035 USA NASA
QSS Grp Inc Ames Res Ctr Moffett Field CA 94035 USA
Earth-science data processing at NASA is the problem of transforming low-level observations of the Earth system, such as data from Earth-observing satellites, into high-level observations or predictions, such as crop ...
ISBN:
(纸本)3540232419
Earth-science data processing at NASA is the problem of transforming low-level observations of the Earth system, such as data from Earth-observing satellites, into high-level observations or predictions, such as crop failure or high fire risk. Given the large number of socially and economically important variables that can be derived from the data, the complexity of the data processing needed to derive them and the many terabytes of data that must be processed each day, there are great challenges and opportunities in processing the data in a timely manner, and a need for more effective automation. Our approach to providing this automation is to cast it as a constraint-based planning problem: we represent data-processing operations as planner actions and desired data products as planner goals, and use a planner to generate data-flow programs that produce the requested data. the planning problem is translated into a constraint satisfaction problem (CSP) and solved by constraint propagation and search algorithms.
暂无评论