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.
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.
Agricultural land allocation is a problem that exists in most provinces in Vietnam. Each household owns many disconnected parcels, which reduces agricultural development. the solution to the problem is to repartition ...
详细信息
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.
We study the complexity of constraint satisfaction problems involving global constraints, i.e., special-purpose constraints provided by a solver and represented implicitly by a parametrised algorithm. Such constraints...
详细信息
Sophisticated compact SAT encodings exist for many types of constraints. Alternatively, for instances with many (or large) constraints, the SAT solver can also be extended with built-in propagators (the SAT Modulo the...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
Sophisticated compact SAT encodings exist for many types of constraints. Alternatively, for instances with many (or large) constraints, the SAT solver can also be extended with built-in propagators (the SAT Modulo theories approach, SMT). For example, given a cardinality constraint x(1) + ... + x(n) <= k, as soon as k variables become true, such a propagator can set the remaining variables to false, generating a so-called explanation clause of the form x(1) boolean AND ... boolean AND x(k) -> (x(i)) over bar. But certain "bottle-neck" constraints end up generating an exponential number of explanations, equivalent to a naive SAT encoding, much worse than using a compact encoding with auxiliary variables from the beginning. therefore, Abio and Stuckey proposed starting off with a full SMT approach and partially encoding, on the fly, only certain "active" parts of constraints. Here we build upon their work. Equipping our solvers with some additional bookkeeping to monitor constraint activity has allowed us to shed light on the effectiveness of SMT: many constraints generate very few, or few different, explanations. We also give strong experimental evidence showing that it is typically unnecessary to consider partial encodings: it is competitive to encode the few really active constraints entirely. this makes the approach amenable to any kind of constraint, not just the ones for which partial encodings are known.
Weighted Partial MaxSAT (WPMS) is an optimization variant of the Satisfiability (SAT) problem. Several combinatorial optimization problems can be translated into WPMS. In this paper we extend the state-of-the-art WPM2...
详细信息
the course timetabling problem can be generally defined as the task of assigning a number of lectures to a limited set of timeslots and rooms, subject to a given set of hard and soft constraints. the modeling language...
详细信息
the course timetabling problem can be generally defined as the task of assigning a number of lectures to a limited set of timeslots and rooms, subject to a given set of hard and soft constraints. the modeling language for course timetabling is required to be expressive enough to specify a wide variety of soft constraints and objective functions. Furthermore, the resulting encoding is required to be extensible for capturing new constraints and for switching them between hard and soft, and to be flexible enough to deal with different formulations. In this paper, we propose to make effective use of ASP as a modeling language for course timetabling. We show that our ASP-based approach can naturally satisfy the above requirements, through an ASP encoding of the curriculum-based course timetabling problem proposed in the third track of the second international timetabling competition (ITC-2007). Our encoding is compact and human-readable, since each constraint is individually expressed by either one or two rules. Each hard constraint is expressed by using integrity constraints and aggregates of ASP. Each soft constraint S is expressed by rules in which the head is the form of penalty (S, V, C), and a violation V and its penalty cost C are detected and calculated respectively in the body. We carried out experiments on four different benchmark sets with five different formulations. We succeeded either in improving the bounds or producing the same bounds for many combinations of problem instances and formulations, compared withthe previous best known bounds.
We present a method that, given a constraint model, suggests global constraints to replace parts of it. this helps non-expert users to write higher-level models that are easier to reason about and may result in better...
详细信息
the course timetabling problem can be generally defined as the task of assigning a number of lectures to a limited set of timeslots and rooms, subject to a given set of hard and soft constraints. the modeling language...
详细信息
the course timetabling problem can be generally defined as the task of assigning a number of lectures to a limited set of timeslots and rooms, subject to a given set of hard and soft constraints. the modeling language for course timetabling is required to be expressive enough to specify a wide variety of soft constraints and objective functions. Furthermore, the resulting encoding is required to be extensible for capturing new constraints and for switching them between hard and soft, and to be flexible enough to deal with different formulations. In this paper, we propose to make effective use of ASP as a modeling language for course timetabling. We show that our ASP-based approach can naturally satisfy the above requirements, through an ASP encoding of the curriculum-based course timetabling problem proposed in the third track of the second international timetabling competition (ITC-2007). Our encoding is compact and human-readable, since each constraint is individually expressed by either one or two rules. Each hard constraint is expressed by using integrity constraints and aggregates of ASP. Each soft constraint S is expressed by rules in which the head is the form of penalty (S, V, C), and a violation V and its penalty cost C are detected and calculated respectively in the body. We carried out experiments on four different benchmark sets with five different formulations. We succeeded either in improving the bounds or producing the same bounds for many combinations of problem instances and formulations, compared withthe previous best known bounds.
暂无评论