thanks to its extended expressiveness, the quantified constraint satisfaction problem (QCSP) can be used to model problems that are difficult to express in the standard CSP formalism. this is only recently that the co...
详细信息
ISBN:
(纸本)3540462678
thanks to its extended expressiveness, the quantified constraint satisfaction problem (QCSP) can be used to model problems that are difficult to express in the standard CSP formalism. this is only recently that the constraint community got interested in QCSP and proposed algorithms to solve it. In this paper we propose BlockSolve, an algorithm for solving QCSPs that factorizes computations made in branches of the search tree. Instead of following the order of the variables in the quantification sequence, our technique searches for combinations of values for existential variables at the bottom of the tree that will work for (several) values of universal variables earlier in the sequence. An experimental study shows the good performance of BlockSolve compared to a state of the art QCSP solver.
the constraint Hierarchy (CH) framework is used to tackle multiple criteria selection (MCS), consisting of a set of candidates and a set of, possibly competing, criteria for selecting the "best" candidate(s)...
详细信息
ISBN:
(纸本)3540652248
the constraint Hierarchy (CH) framework is used to tackle multiple criteria selection (MCS), consisting of a set of candidates and a set of, possibly competing, criteria for selecting the "best" candidate(s). In this paper, we identify aspects of the CN framework for further enhancement so as to model and solve MCS problems more accurately. We propose the Fuzzy constraint Hierarchies framework, which allows constraints to belong to, possibly, more than one level in a constraint hierarchy to a varying degree. We also propose to replace the standard equality relation = used in valuation comparators of the CH framework by the alpha-approximate equality relation =(alpha)(alpha) for providing more flexible control over the handling of valuations with close error values. these proposals result in three new classes of valuation comparators. Formal properties of the new comparators are given, wherever possible.
Scaling frequency and voltage in a coordinated manner is a promising way to reduce energy and power. we explore the use of dynamic frequency clocking within the datapath and datapath scheduling algorithms that can be ...
详细信息
One strand of CP research seeks to design a small set of primitives and operators that can be used to build an appropriate algorithm for solving any given combinatorial problem. the aim is to "package" CP, s...
详细信息
ISBN:
(纸本)3540202021
One strand of CP research seeks to design a small set of primitives and operators that can be used to build an appropriate algorithm for solving any given combinatorial problem. the aim is to "package" CP, simplifying its use, in contrast to current systems which offer application developers a full constraintprogramming language. In this talk we examine the risks of this line of research, and argue that our field is still too immature to be ready for "packaging".
the presence of uncertainty in the real world makes robustness a desirable property of solutions to constraint Satisfaction Problems (CSP). A solution is said to be robust if it can be easily repaired when unexpected ...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
the presence of uncertainty in the real world makes robustness a desirable property of solutions to constraint Satisfaction Problems (CSP). A solution is said to be robust if it can be easily repaired when unexpected events happen. this has already been addressed in the frameworks of Boolean satisfiability (SAT) and constraintprogramming (CP). In this paper we consider the unaddressed problem of robustness in weighted MaxSAT, by showing how robust solutions to weighted MaxSAT instances can be effectively obtained via reformulation into pseudo-Boolean formulae. Our encoding provides a reasonable balance between increase in size and performance. We also consider flexible robustness for problems having some unrepairable breakage, in other words, problems for which there does not exist a robust solution.
the propositional satisfiability problem (SAT) is one of the simplest instances of constraintprogramming (CP): variables are bi-valued (can only take values 0 or 1), and all constraints are clauses (disjunctions of l...
详细信息
We consider a generic binary CSP solver parameterized by high-level design choices, i.e., backtracking mechanisms, constraint propagation levels, and variable ordering heuristics. We experimentally compare 24 differen...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
We consider a generic binary CSP solver parameterized by high-level design choices, i.e., backtracking mechanisms, constraint propagation levels, and variable ordering heuristics. We experimentally compare 24 different configurations of this generic solver on a benchmark of around a thousand instances. this allows us to understand the complementarity of the different search mechanisms, with an emphasis on Backtracking with Tree Decomposition (BTD). then, we use a per-instance algorithm selector to automatically select a good solver for each new instance to be solved. We introduce a new strategy for selecting the solvers of the portfolio, which aims at maximizing the number of instances for which the portfolio contains a good solver, independently from a time limit.
We consider constraint Satisfaction Problems in which constraints can be initially incomplete, where it is unknown whether certain tuples satisfy the constraint or not. We assume that we can determine such an unknown ...
详细信息
ISBN:
(纸本)9783540749691
We consider constraint Satisfaction Problems in which constraints can be initially incomplete, where it is unknown whether certain tuples satisfy the constraint or not. We assume that we can determine such an unknown tuple, i.e., find out whether this tuple is in the constraint or not, but doing so incurs a known cost, which may vary between tuples. We also assume that we know the probability of an unknown tuple satisfying a constraint. We define algorithms for this problem, based on backtracking search. Specifically, we consider a simple iterative algorithm based on a cost limit on which unknowns may be determined, and a more complex algorithm that delays determining an unknown in order to estimate better whether doing so is worthwhile. We show experimentally that the more sophisticated algorithms can greatly reduce the average cost.
Large neighbourhood search, a meta-heuristic, has proven to be successful on a wide range of optimisation problems. the algorithm repeatedly generates and searches through a neighbourhood around the current best solut...
详细信息
ISBN:
(数字)9783319983349
ISBN:
(纸本)9783319983349;9783319983332
Large neighbourhood search, a meta-heuristic, has proven to be successful on a wide range of optimisation problems. the algorithm repeatedly generates and searches through a neighbourhood around the current best solution. thus, it finds increasingly better solutions by solving a series of simplified problems, all of which are related to the current best solution. In this paper, we show that significant benefits can be obtained by simulating local-search behaviour in constraintprogramming by using phase saving based on the best solution found so far during the search, activity-based search (VSIDS), and nogood learning. the approach is highly effective despite its simplicity, improving the highest scoring solver, Chuffed, in the free category of the MiniZinc Challenge 2017, and can be easily integrated into modern constraintprogramming solvers. We validated the results on a wide range of benchmarks from the competition library, comparing against seventeen state-of-the-art solvers.
We introduce a parallelized version of tree-decomposition based dynamic programming for solving difficult weighted CSP instances on many cores. A tree decomposition organizes cost functions in a tree of collection of ...
详细信息
ISBN:
(纸本)9783642153952
We introduce a parallelized version of tree-decomposition based dynamic programming for solving difficult weighted CSP instances on many cores. A tree decomposition organizes cost functions in a tree of collection of functions called clusters. By processing the tree from the leaves up to the root, we solve each cluster concurrently, for each assignment of its separator, using a state-of-the-art exact sequential algorithm. the grain of parallelism obtained in tins way is directly related to the tree decomposition used. We use a dedicated strategy for building suitable decompositions. We present preliminary results of our prototype running on a cluster with hundreds of cores on different decomposable real problems. this implementation allowed us to solve the last open CELAR radio link frequency assignment instance to optimality.
暂无评论