Filtering constraint networks to reduce search space is one of the main cornerstones of constraintprogramming and among them (Generalized) Arc Consistency has been the most fundamental. While stronger consistencies a...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Filtering constraint networks to reduce search space is one of the main cornerstones of constraintprogramming and among them (Generalized) Arc Consistency has been the most fundamental. While stronger consistencies are also the subject of considerable attention, none matches GAC's and for this reason it continues to advance at a steady pace and has become the popular choice of consistency for filtering algorithms. In this paper, we build on the success of GAC by proposing a way to transform a constraint network into another such that enforcing GAC on the latter is equivalent to enforcing a stronger consistency on the former. the key idea is to factor out commonly shared variables from constraints' scopes, form new variables, then re-attach them back to the constraints where they come from. Experiments show that this method is inexpensive and outperforms specialized algorithms and other techniques when it comes to full pair-wise consistency (FPWC).
Scheduling a subset of solvers belonging to a given portfolio has proven to be a good strategy when solving constraint Satisfaction Problems (CSPs). In this paper, we show that this approach can also be effective for ...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Scheduling a subset of solvers belonging to a given portfolio has proven to be a good strategy when solving constraint Satisfaction Problems (CSPs). In this paper, we show that this approach can also be effective for constraint Optimization Problems (COPs). Unlike CSPs, sequential execution of optimization solvers can communicate information in the form of bounds to improve the performance of the following solvers. We provide a hybrid and flexible portfolio approach that combines static and dynamic time splitting for solving a given COP. Empirical evaluations show the approach is promising and sometimes even able to outperform the best solver of the porfolio.
Relational consistency algorithms are instrumental for solving difficult instances of constraint Satisfaction Problems (CSPs), often allowing backtrack-free search. In this paper, we improve an algorithm for enforcing...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Relational consistency algorithms are instrumental for solving difficult instances of constraint Satisfaction Problems (CSPs), often allowing backtrack-free search. In this paper, we improve an algorithm for enforcing relational consistency by exploiting the property that the constraints of the dual encoding of a CSP are piecewise functional. this property allows us to partition a CSP relation into blocks of equivalent tuples at varying levels of granularity. Our new algorithm dynamically exploits those partitions. Our experiments show a significant improvement of the processing time for enforcing relational consistency.
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.
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.
Finding the largest clique in a given graph is one of the fundamental NP-hard problems. We take a widely used branch and bound algorithm for the maximum clique problem, and discuss an alternative way of understanding ...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Finding the largest clique in a given graph is one of the fundamental NP-hard problems. We take a widely used branch and bound algorithm for the maximum clique problem, and discuss an alternative way of understanding the algorithm which closely resembles a constraint model. By using this view, and by taking measurements inside search, we provide a new explanation for the success of the algorithm: one of the intermediate steps, by coincidence, often approximates a "smallest domain first" heuristic. We show that replacing this step with a genuine "smallest domain first" heuristic leads to a reduced branching factor and a smaller search space, but longer runtimes. We then introduce a "domains of size two first" heuristic, which integrates cleanly into the algorithm, and which both reduces the size of the search space and gives a reduction in runtimes.
Many real world discrete optimization problems are expressible as nested problems where we solve one optimization or satisfaction problem as a subproblem of a larger meta problem. Nested problems include many importan...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Many real world discrete optimization problems are expressible as nested problems where we solve one optimization or satisfaction problem as a subproblem of a larger meta problem. Nested problems include many important problem classes such as: stochastic constraint satisfaction/optimization, quantified constraint satisfaction/optimization and minimax problems. In this paper we define a new class of problems called nested constraint programs (NCP) which include the previously mentioned problem classes as special cases, and describe a search-based CP solver for solving NCP's. We briefly discuss how nogood learning can be used to significantly speedup such an NCP solver. We show that the new solver can be significantly faster than existing solvers for the special cases of stochastic/quantified CSP/COP's, and that it can solve new types of problems which cannot be solved with existing solvers.
Novel search space splitting techniques have recently been successfully exploited to paralleliz constraintprogramming and Mixed Integer programming solvers. We first show how universal hashing can be used to extend o...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Novel search space splitting techniques have recently been successfully exploited to paralleliz constraintprogramming and Mixed Integer programming solvers. We first show how universal hashing can be used to extend one such interesting approach to a generalized setting that goes beyond discrepancy-based search, while still retaining strong theoretical guarantees. We then explain that such static or explicit splitting approaches are not as effective in the context of parallel combinatorial search with intensive knowledge acquisition and sharing such as parallel SAT, where implicit splitting through clause sharing appears to dominate. Furthermore, we show that in a parallel setting there exists a surprising tradeoff between the well-known communication cost for knowledge sharing across multiple compute nodes and the so far neglected cost incurred by the computational load per node. We provide experimental evidence that one can successfully exploit this tradeoff and achieve reasonable speedups in parallel SAT solving beyond 16 cores.
When implementing a propagator for a constraint, one must decide about variants: When implementing min, should one also implement max? Should one implement linear equations both with and without coefficients? Constrai...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
When implementing a propagator for a constraint, one must decide about variants: When implementing min, should one also implement max? Should one implement linear equations both with and without coefficients? constraint variants are ubiquitous: implementing them requires considerable effort, but yields better performance. this abstract shows how to use views to derive propagator variants where derived propagators are perfect in that they inherit essential properties such as correctness and domain and bounds consistency. Techniques for systematically deriving propagators are developed, and the abstract sketches an implementation architecture for views that is independent of the underlying constraintprogramming system. Evaluation of views implemented in Gecode shows that derived propagators are efficient and that views often incur no overhead. Views have proven essential for implementing Gecode, substantially reducing the amount of code that needs to be written and maintained.
Elimination of inconsistent values in instances of the constraint satisfaction problem (CSP) conserves all solutions. Elimination of substitutable values conserves at least one solution. We show that certain values wh...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Elimination of inconsistent values in instances of the constraint satisfaction problem (CSP) conserves all solutions. Elimination of substitutable values conserves at least one solution. We show that certain values which are neither inconsistent nor substitutable can also be deleted while conserving at least one solution. this allows us to state novel rules for the elimination of values in a binary CSP. From a practical point of view, we show that one such rule can be applied in the same asymptotic time complexity as neighbourhood substitution but is strictly stronger. An alternative to the elimination of values from domains is the elimination of variables. We give novel satisfiability-preserving variable elimination operations. In each case we show that if the instance is satisfiable, then a solution to the original instance can always be recovered in low-order polynomial time from a solution to the reduced instance.
暂无评论