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. ...
详细信息
A depth-first search algorithm can be used to find optimal solutions of a constraint Satisfaction Problem (CSP) with respect to a set of conditional preferences statements (e.g., a cp-net). this involves checking at e...
详细信息
the presence of symmetries in a constraint satisfaction problem gives an opportunity for more efficient search. Within the class of matrix models, we show that the problem of deciding whether some well known permutati...
详细信息
Gutierrez and Meseguer show how to enforce consistency in BnB-ADOPT(+) for distributed constraint optimization, but they consider unconditional deletions only. However, during search, more values can be pruned conditi...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
Gutierrez and Meseguer show how to enforce consistency in BnB-ADOPT(+) for distributed constraint optimization, but they consider unconditional deletions only. However, during search, more values can be pruned conditionally according to variable instantiations that define subproblems. Enforcing consistency in these subproblems can cause further search space reduction. We introduce efficient methods to maintain soft arc consistencies in every subproblem during search, a non trivial task due to asynchronicity and induced overheads. Experimental results show substantial benefits on three different benchmarks.
Soft neighborhood substitutability (SNS) is a powerful technique to automatically detect and prune dominated solutions in combinatorial optimization. Recently, it has been shown in [26] that enforcing partial SNS (PSN...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
Soft neighborhood substitutability (SNS) is a powerful technique to automatically detect and prune dominated solutions in combinatorial optimization. Recently, it has been shown in [26] that enforcing partial SNS (PSNSr) during search can be worthwhile in the context of Weighted constraint Satisfaction Problems (WCSP). However, for some problems, especially with large domains, PSNSr is still too costly to enforce due to its worst-case time complexity in O(ned(4)) for binary WCSP. We present a simplified dominance breaking constraint, called restricted dead-end elimination (DEEr), the worst-case time complexity of which is in O(ned(2)). Dead-end elimination was introduced in the context of computational biology as a preprocessing technique to reduce the search space [13, 14, 16, 17, 28, 30]. Our restriction involves testing only one pair of values per variable instead of all the pairs, withthe possibility to prune several values at the same time. We further improve the original dead-end elimination criterion, keeping the same time and space complexity as DEEr. Our results show that maintaining DEEr during a depth-first branch and bound (DFBB) search is often faster than maintaining PSNSr and always faster than or similar to DFBB alone.
We consider the impact of value ordering heuristics on the search effort required to find all solutions, or proving none exist, to a constraint satisfaction problem in k-way branching search. We show that when the var...
详细信息
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 difficulty that arises frequently when writing a constraint solver is to determine the constraint propagation and simplification algorithm. In previous work, different methods for automatic generation of propagation...
详细信息
MC-nets is a concise representation of the characteristic functions that exploits a set of rules to compute payoffs. Given a MC-nets instance, the problem of computing a payoff division in the least core, which is a g...
详细信息
ISBN:
(数字)9783319131917
ISBN:
(纸本)9783319131917;9783319131900
MC-nets is a concise representation of the characteristic functions that exploits a set of rules to compute payoffs. Given a MC-nets instance, the problem of computing a payoff division in the least core, which is a generalization of the core-non-emptiness problem that is known to be coNP-complete, is definitely a hard computational problem. In fact, to the best of our knowledge, no algorithm can actually compute such a payoff division for MC-nets instances with dozens of agents. We propose a new algorithm for this problem, that exploits the constraint generation technique to solve the linear programming problem that potentially has a huge number of constraints. Our experimental results are striking since, using 8 GB memory, our proposed algorithm can successfully compute a payoff division in the least core for the instances with up to 100 agents, but the naive algorithm fails due to a lack of memory for instances with 30 or more agents.
Recent years have seen an increasing interest in the application of constraint solving techniques to test, verify and analyze software systems. A significant body of constraint-based techniques has been proposed and i...
详细信息
ISBN:
(纸本)9780769549934;9781479913244
Recent years have seen an increasing interest in the application of constraint solving techniques to test, verify and analyze software systems. A significant body of constraint-based techniques has been proposed and investigated in the context of test input generation, model-based testing, symbolic execution, static analysis, program verification, and many other areas. these techniques use or extend constraint solvers such as SAT and SMT solvers to reason about boolean, integer, real and floating-point data types, as well as complex data structures, control structures, method calls and other program features. the constraint systems that result from this work usually share many common features and are relevant to a variety of application domains. Following a first meeting held withthe principles and practice of constraintprogramming (cp) conference in 2006, and three subsequent meetings at the internationalconference on Software Testing, Verification and Validation (ICST) in 2010, 2011 and 2012, the aim of this paper is to bring together researchers and practitioners working in constraint-based software testing, verification and analysis, to investigate future developments in this research field.
暂无评论