the problem of finding a collection of solutions to a combinatorial problem that is optimal in terms of ail inter-solution objective function exists in many application settings. For example, maximizing diversity amon...
详细信息
ISBN:
(纸本)9783642042430
the problem of finding a collection of solutions to a combinatorial problem that is optimal in terms of ail inter-solution objective function exists in many application settings. For example, maximizing diversity amongst a set of solutions in a product configuration setting is desirable so that a wide range of different options is offered to a customer. Given the computationally Challenging nature of these multi-resolution queries, existing algorithmic approaches either apply heuristics or combinatorial search, which does not scale to large solution spaces. However, in many domains compiling the original problem into a compact representation call support computationally efficient query answering. In this paper we present a new approach to find optimal collections of solutions when the problem is compiled into a multi-valued decision diagram. We demonstrate empirically that for real-world configuration problems, both exact and approximate versions of our methods are effective and are capable of significantly outperforming state-of-the-art search-based techniques.
constraintprogramming often involves global constraints, for which various custom filtering algorithms have been published. this work Presents a semi-automatic generation of CHR solvers for the subset of global const...
详细信息
ISBN:
(纸本)9783540859574
constraintprogramming often involves global constraints, for which various custom filtering algorithms have been published. this work Presents a semi-automatic generation of CHR solvers for the subset of global constraints defineable by specific automata. the generation is hissed on a constraint logic program modelling an automaton and an improved version of the Prim-Miner algorithm. the solvers only need to be generated once and achieve are-consistency for over 40 global constraints.
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.
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.
Recently proposed impact based heuristics have been shown to outperform other instances of tire first-fail policy such as the common dons and dom/deg heuristics. this paper compares the behaviour of a constraint and a...
详细信息
ISBN:
(纸本)9783540859574
Recently proposed impact based heuristics have been shown to outperform other instances of tire first-fail policy such as the common dons and dom/deg heuristics. this paper compares the behaviour of a constraint and a. variable centered impact based heuristic and relates it to the amount of constraint propagation inherent to the model of the problem. Additionally, it presents results which suggest that: a lookahead impact heuristic we recently proposed might be the best choice for problems with low locality and where constraint propagation plays an important role.
constraints that are defined by tables of allowed tuples of assignments are common in constraintprogramming. In this paper we present an approach to reformulating table constraints of large arity into a conjunction o...
详细信息
ISBN:
(纸本)9783540859574
constraints that are defined by tables of allowed tuples of assignments are common in constraintprogramming. In this paper we present an approach to reformulating table constraints of large arity into a conjunction of lower arity constraints. Our approach exploits functional dependencies. We Study the complexity of finding reformulations that either minimize the memory size or arity of a constraint using a Set of its functional dependencies. We also present an algorithm to compute such reformulations. We Show that our technique is complementary to existing approaches for compressing extensional constraints.
In this paper, we describe a new algorithm for sampling solutions from a uniform distribution over the solutions of a constraint network. Our new algorithm improves upon the Sampling/Importance Resampling (SIR) compon...
详细信息
ISBN:
(纸本)9783540859574
In this paper, we describe a new algorithm for sampling solutions from a uniform distribution over the solutions of a constraint network. Our new algorithm improves upon the Sampling/Importance Resampling (SIR) component of our previous scheme of SampleSearch-SIR by taking advantage of the decomposition implied by the network's AND/OR search space. We also describe how our new scheme can approximately count and lower bound the number of solutions of a constraint network. We demonstrate boththeoretically and empirically that our new algorithm yields far better performance than competing approaches.
Solutions to valid Quantified constraint Satisfaction Problems (QCSPs) are called winning strategies and represent possible ways in which the existential player can react to the moves of the universal one to "win...
详细信息
ISBN:
(纸本)9783540859574
Solutions to valid Quantified constraint Satisfaction Problems (QCSPs) are called winning strategies and represent possible ways in which the existential player can react to the moves of the universal one to "win the game". However, different winning strategies are not necessarily equivalent: some may be preferred to others. We define Quantified constraint Optimization Problems (QCOP) as a framework which allows both to formally express preferences over QCSP strategies, and to solve the related optimization problem. We present examples and some experimental results. We also discuss flow this framework relates to other formalisms for hierarchical decision modeling known as von Stackelberg games and bilevel (and multilevel) programming.
Call control features (e.g., call-divert, voice-mail) are primitive options to which users can subscribe off-line to personalise their service. the configuration of a feature subscription involves choosing and sequenc...
详细信息
ISBN:
(纸本)9783540859574
Call control features (e.g., call-divert, voice-mail) are primitive options to which users can subscribe off-line to personalise their service. the configuration of a feature subscription involves choosing and sequencing features from a catalogue and is subject to constraints that prevent undesirable feature interactions at run-time. When the subscription requested by a user is inconsistent, one problem is to find an optimal relaxation. In this paper, we show that this problem is NP-hard and we present a constraintprogramming formulation using the variable weighted constraint satisfaction problem framework. We also present simple formulations using partial weighted maximum satisfiability and integer linear programming. We experimentally compare our formulations of the different approaches;the results suggest that our constraintprogramming approach is the best of the three overall.
ABT is the reference algorithm for asynchronous distributed constraint satisfaction. When searching, ABT produces nogoods as justifications of deleted values. When one of such nogoods has an empty left-hand side, the ...
详细信息
ISBN:
(纸本)9783540859574
ABT is the reference algorithm for asynchronous distributed constraint satisfaction. When searching, ABT produces nogoods as justifications of deleted values. When one of such nogoods has an empty left-hand side, the considered value is eliminated unconditionally, once and for all. this value deletion can be propagated using standard arc consistency techniques, producing new deletions in the domains of other variables. this causes substantial reductions in the search effort required to solve a class of problems. We also extend this idea to the propagation of conditional deletions. something already proposed in the past. We provide experimental results that show the benefits of the proposed approach, especially considering communication cost.
暂无评论