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.
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.
In cp literature combinatorial design problems such as sport scheduling, Steiner systems, error-correcting codes and more, are typically solved using Finite Domain (FD) models despite often being more naturally expres...
详细信息
ISBN:
(纸本)3540232419
In cp literature combinatorial design problems such as sport scheduling, Steiner systems, error-correcting codes and more, are typically solved using Finite Domain (FD) models despite often being more naturally expressed as Finite Set (FS) models. Existing FS solvers have difficulty with such problems as they do not make strong use of the ubiquitous set cardinality information. We investigate a new approach to strengthen the propagation of FS constraints in a tractable way: extending the domain representation to more closely approximate the true domain of a set variable. We show how this approach allows us to reach a stronger level of consistency, compared to standard FS solvers, for arbitrary constraints as well as providing a mechanism for implementing certain symmetry breaking constraints. By experiments on Steiner Systems and error correcting codes, we demonstrate that our approach is not only an improvement over standard FS solvers but also an improvement on recently published results using FD 0/1 matrix models as well.
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.
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.
暂无评论