Streamlined constraint reasoning is the addition of uninferred constraints to a constraint model to reduce the search space, while retaining at least one solution. Previously it has been established that it is possibl...
详细信息
ISBN:
(数字)9783319983349
ISBN:
(纸本)9783319983349;9783319983332
Streamlined constraint reasoning is the addition of uninferred constraints to a constraint model to reduce the search space, while retaining at least one solution. Previously it has been established that it is possible to generate streamliners automatically from abstract constraint specifications in Essence and that effective combinations of streamliners can allow instances of much larger scale to be solved. A shortcoming of the previous approach was the crude exploration of the power set of all combinations using depth and breadth first search. We present a new approach based on Monte Carlo search over the lattice of streamlined models, which efficiently identifies effective streamliner combinations.
We present the w constraint combinator that models while loops in constraintprogramming. Embedded in a finite domain constraint solver, it allows programmers to develop non-trivial arithmetical relations using loops,...
详细信息
ISBN:
(纸本)9783540749691
We present the w constraint combinator that models while loops in constraintprogramming. Embedded in a finite domain constraint solver, it allows programmers to develop non-trivial arithmetical relations using loops, exactly as in an imperative language style. the deduction capabilities of this combinator come from abstract interpretation over the polyhedra abstract domain. this combinator has already demonstrated its utility in constraint- based verification and we argue that it also facilitates the rapid prototyping of arithmetic constraints (e.g. power, gcd or sum).
We show that a number of problems in Artificial Intelligence can be seen as Stochastic constraint Optimization Problems (SCOPs): problems that have both a stochastic and a constraint optimization component. We argue t...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
We show that a number of problems in Artificial Intelligence can be seen as Stochastic constraint Optimization Problems (SCOPs): problems that have both a stochastic and a constraint optimization component. We argue that these problems can be modeled in a new language, SC-ProbLog, that combines a generic Probabilistic Logic programming (PLP) language, ProbLog, with stochastic constraint optimization. We propose a toolchain for effectively solving these SC-ProbLog programs, which consists of two stages. In the first stage, decision diagrams are compiled for the underlying distributions. these diagrams are converted into models that are solved using Mixed Integer programming or constraintprogramming solvers in the second stage. We show that, to yield linear constraints, decision diagrams need to be compiled in a specific form. We introduce a new method for compiling small Sentential Decision Diagrams in this form. We evaluate the effectiveness of several variations of this toolchain on test cases in viral marketing and bioinformatics.
Deviation is a recent constraint to balance a set of variables with respect to a given mean. We show that the propagators recently introduced are not bound-consistent when the mean is rational. We introduce bound-cons...
详细信息
ISBN:
(纸本)9783540749691
Deviation is a recent constraint to balance a set of variables with respect to a given mean. We show that the propagators recently introduced are not bound-consistent when the mean is rational. We introduce bound-consistent propagators running in linear time with respect to the number of variables. We evaluate the improvement in terms of efficiency and pruning obtained withthe new propagators on the Balanced Academic Curriculum Problem.
A new interval constraint propagation algorithm;called MOnotonic Hall Consistency (Mohc), has recently been proposed. Mohc exploits monotonicity of functions to better filter variable domains. Embedded in an interval-...
详细信息
ISBN:
(纸本)9783642153952
A new interval constraint propagation algorithm;called MOnotonic Hall Consistency (Mohc), has recently been proposed. Mohc exploits monotonicity of functions to better filter variable domains. Embedded in an interval-based solver, Mohc shows very high performance for solving systems of numerical constraints (equations or inequalities) over the reals. However, the main drawback is that its revise procedure depends on two user-defined parameters. this paper reports a rigourous empirical study resulting in a variant of Mohc that avoids a manual tuning of the parameters. In particular, we propose a policy to adjust in an auto-adaptive way;during the search, the parameter sensitive to the monotonicity of the revised function.
In this paper we propose off-line and on-line extensions to the Resource Constrained Project Scheduling Problem. the off-line extension is a variant of RCPSP with time lags and uncertain, bounded activity durations. I...
详细信息
ISBN:
(纸本)9783642153952
In this paper we propose off-line and on-line extensions to the Resource Constrained Project Scheduling Problem. the off-line extension is a variant of RCPSP with time lags and uncertain, bounded activity durations. In this context we improve over our previous work presented in [12] by proposing an incremental flow computation for finding minimal conflict sets and a set of filtering rules for cumulative constraint propagation. the on-line extension is based instead on considering an on-line semantics such as the Self-Timed Execution and take it into account in the scheduling process. Adding the on-line aspect to the problem makes the CSP framework no longer suitable. We have extended the CSP framework to take into account general search decisions and auxiliary unbound variables. An extensive set of experimental results show an improvement
For the last ten years, a significant amount of work in the constraint community has been devoted to the improvement of complete methods for solving soft constraints networks. We wanted to see how recent progress in t...
详细信息
ISBN:
(纸本)3540202021
For the last ten years, a significant amount of work in the constraint community has been devoted to the improvement of complete methods for solving soft constraints networks. We wanted to see how recent progress in the weighted CSP (WCSP) field could compete with other approaches in related fields. One of these fields is propositional logic and the well-known Max-SAT problem. In this paper, we show how Max-SAT can be encoded as a weighted constraint network, either directly or using a dual encoding. We then solve Max-SAT instances using state-of-the-art algorithms for weighted Max-CSP, dedicated Max-SAT solvers and the state-of-the-art MIP solver CPLEX. the results show that, despite a limited adaptation to CNF structure, WCSP-solver based methods are competitive with existing methods and can even outperform them, especially on the hardest, most over-constrained problems.
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:
(纸本)9783540859574
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 paper shows how to use variable views to derive perfect propagator variants: derived propagators inherit essential properties such as correctness and domain and bounds completeness.
the availability of commodity multi-core and multi-processor machines and the inherent parallelism in constraintprogramming search offer significant opportunities for constraintprogramming. they also present a funda...
详细信息
ISBN:
(纸本)9783540749691
the availability of commodity multi-core and multi-processor machines and the inherent parallelism in constraintprogramming search offer significant opportunities for constraintprogramming. they also present a fundamental challenge: how to exploit parallelism transparently to speed up constraint programs. this paper shows how to parallelize constraint programs transparently without changes to the code. the main technical idea consists of automatically lifting a sequential exploration strategy into its parallel counterpart, allowing workers to share and steal subproblems. Experimental results show that the parallel implementation may produces significant speedups on multi-core machines.
We present new results in crossword composition, showing that our program significantly outperforms previous successful techniques in the literature. We emphasize phase transition phenomena, and identify classes of ha...
详细信息
ISBN:
(纸本)9783540859574
We present new results in crossword composition, showing that our program significantly outperforms previous successful techniques in the literature. We emphasize phase transition phenomena, and identify classes of hard problems. Phase transition is shown to occur when varying problem parameters, such as the dictionary size and the number of blocked cells on a grid, of large-size realistic problems.
暂无评论