In interactive decision-making settings, such as product configuration, users are stating preferences, or foreground constraints, over a set of possible solutions, as defined by background constraints. When the foregr...
详细信息
ISBN:
(纸本)9783642042430
In interactive decision-making settings, such as product configuration, users are stating preferences, or foreground constraints, over a set of possible solutions, as defined by background constraints. When the foreground constraints introduce inconsistencies withthe background constraints, we wish to find explanations that help the user converge to a solution. In order to provide satisfactory explanations, it call be useful to know one or several subsets of conflicting constraints;Such a subset is called a conflict. When computing such conflicts is intractable in an interactive context, we call choose to compile the problem so as to allow faster response times. In this paper we propose a new representation, which implicitly encompasses all conflicts possibly introduced by a user's choices. We claim that it call help in Situations where extra information about conflicts is needed, such as when explanations of inconsistency are required.
this paper presents a global constraintthat enforces rules written in a language based on arithmetic and first-order logic to hold among a set of objects. In a first step, the rules are rewritten to Quantifier-Free P...
详细信息
ISBN:
(纸本)9783540859574
this paper presents a global constraintthat enforces rules written in a language based on arithmetic and first-order logic to hold among a set of objects. In a first step, the rules are rewritten to Quantifier-Free Presburger Arithmetic (QFPA) formulas. Secondly. such formulas arc compiled to generators of k-dimensional forbidden sets. Such generators are a generalization of the indexicals of cc(FD). Finally, the forbidden sets generated by such indexicals are aggregated by a sweep-based algorithm and used for filtering. the business rules allow to express a great variety of packing and placement constraints, while admitting effective filtering of the domain variables of the k-dimensional object, without the need to use spatial data structures.
In this paper we present new techniques for improving backtracking based Quantified constraint Satisfaction Problem (QCSP) solvers. QCSP is a generalization of CSP in which variables are either universally or existent...
详细信息
ISBN:
(纸本)9783540749691
In this paper we present new techniques for improving backtracking based Quantified constraint Satisfaction Problem (QCSP) solvers. QCSP is a generalization of CSP in which variables are either universally or existentially quantified and these quantifiers can be alternated in arbitrary ways. Our main new technique is solution directed backjumping (SBJ). In analogue to conflict directed backjumping, SBJ allows the solver to backtrack out of solved sub-trees without having to find all of the distinct solutions normally required to validate the universal variables. Experiments withthe solver QCSP-Solve demonstrate that SBJ can improve its performance on random instances by orders of magnitude. In addition to this contribution, we demonstrate that performing varying levels of propagation for universal vs. existential variables can also be useful for enhancing performance. Finally, we discuss some techniques that are technically interesting but do not yet yield empirical improvements.
this paper presents the results of a case study, concerning the propagation of a global disjunctive resource constraint, when the resource is over-loaded. the problem can be seen as a partial constraint satisfaction p...
详细信息
ISBN:
(纸本)3540652248
this paper presents the results of a case study, concerning the propagation of a global disjunctive resource constraint, when the resource is over-loaded. the problem can be seen as a partial constraint satisfaction problem, in which either the resource constraint or the due dates of some jobs have to be violated. Global constraint propagation methods are introduced to efficiently deal withthis situation. these methods are applied to a well-known operations research problem: minimizing the number of late jobs on a single machine, when jobs are subjected to release dates and due dates. Dominance criteria and a branch and bound procedure are developed for this problem. 960 instances are generated with respect to different characteristics (number of jobs, overload ratio, distribution of release dales, of due dates and of processing times). Instances with 60 jobs are solved in 23 seconds on average and 90% of the instances with100 jobs are solved in less than 1 hour.
Classical constraint satisfaction is concerned withthe feasibility of satisfying a collection of constraints. the extension of this framework to include optimisation is now also being investigated and a theory of so-...
详细信息
ISBN:
(纸本)3540462678
Classical constraint satisfaction is concerned withthe feasibility of satisfying a collection of constraints. the extension of this framework to include optimisation is now also being investigated and a theory of so-called soft constraints is being developed. In this extended framework, tuples of values allowed by constraints are given desirability weightings, or costs, and the goal is to find the most desirable (or least cost) assignment. the complexity of any optimisation problem depends critically on the type of function which has to be minimized. For soft constraint problems this function is a sum of cost functions chosen from some fixed set of available cost functions, known as a valued constraint language. We show in this paper that when the costs are rational numbers or infinite the complexity of a soft constraint problem is determined by certain algebraic properties of the valued constraint language, which we call feasibility polymorphisms and fractional polymorphisms. As an immediate application of these results, we show that the existence of a non-trivial fractional polymorphism is a necessary condition for the tractability of a valued constraint language with rational or infinite costs over any finite domain (assuming P not equal NP).
Accurately estimating the distribution of solutions to a problem, should such solutions exist, provides efficient search heuristics. the purpose of this paper is to propose new ways of computing such estimates, with d...
详细信息
ISBN:
(纸本)9783642042430
Accurately estimating the distribution of solutions to a problem, should such solutions exist, provides efficient search heuristics. the purpose of this paper is to propose new ways of computing such estimates, with different degrees of accuracy and complexity. We build oil the Expectation-Maximizatiou Belief-Propagation (EMPB) framework proposed by Hsu et al. to solve constraint Satisfaction Problems (CSPs). We propose two general approaches within the EMBP framework: we firstly derive update rules at;the constraint level while enforcing domain consistency and then derive update rules globally, at the problem level. the contribution of this paper is two-fold: first, we derive new generic update rules suited to tackle ally CSP;second, we propose all efficient EMP-inspired approach, thereby improving this method and making it competitive withthe state of the art. We evaluate these approaches experimentally and demonstrate their effectiveness.
Ideally, programming propagators as implementations of constraints should be an entirely declarative specification process for a large class of constraints: a high-level declarative specification is automatically tran...
详细信息
ISBN:
(纸本)3540462678
Ideally, programming propagators as implementations of constraints should be an entirely declarative specification process for a large class of constraints: a high-level declarative specification is automatically translated into an efficient propagator. this paper introduces the use of existential monadic second-order logic as declarative specification language for finite set propagators. the approach taken in the paper is to automatically derive projection propagators (involving a single variable only) implementing constraints described by formulas. By this, the paper transfers the ideas of indexicals to finite set constraints while considerably increasing the level of abstraction available with indexicals. the paper proves soundness and completeness of the derived propagators and presents a run-time analysis, including techniques for efficiently executing projectors for n-ary constraints.
the 10th international conference on the principles and practice of constraint programming (CP 2003) was held in Toronto, Canada, during September 27 – October 1, 2004. Information about the conference can be found o...
详细信息
ISBN:
(数字)9783540302018
ISBN:
(纸本)9783540232414
the 10th international conference on the principles and practice of constraint programming (CP 2003) was held in Toronto, Canada, during September 27 – October 1, 2004. Information about the conference can be found on the Web at http://***/~cp2004/ constraintprogramming (CP) is about problem modelling, problem solving, programming, optimization, software engineering, databases, visualization, user interfaces, and anything to do with satisfying complex constraints. It reaches into mathematics, operations research, arti?cial intelligence, algorithms, c- plexity, modelling and programming languages, and many aspects of computer science. Moreover, CP is never far from applications, and its successful use in industry and government goes hand in hand withthe success of the CP research community. constraintprogrammingcontinuesto beanexciting,?ourishingandgrowing research?eld,***, from 158 submissions, we chose 46 to be published in full in the proceedings. Instead of selecting one overall best paper, we picked out four “distinguished” papers – though we were tempted to select at least 12 such papers. In addition we included 16 short papersin the proceedings– these were presentedas posters at CP 2004. this volume includes summaries of the four invited talks of CP 2004. Two speakers from industry were invited. However these were no ordinary industrial representatives,buttwoofthe leadingresearchersinthe CPcommunity:Helmut Simonis of Parc Technologies, until its recent takeover by Cisco Systems; and Jean Francoi ¸ s Puget, Director of Optimization Technology at ILOG. the other two invited speakers are also big movers and shakers in the researchcommunity.
We define Realtime Online solving of Quantified constraint Satisfaction Problems (QCSPs) as a, model for realtime online CSP solving. We use a combination of propagation, lookahead and heuristics and show how all thre...
详细信息
ISBN:
(纸本)9783642042430
We define Realtime Online solving of Quantified constraint Satisfaction Problems (QCSPs) as a, model for realtime online CSP solving. We use a combination of propagation, lookahead and heuristics and show how all three improve performance. For adversarial opponents we show that we can achieve promising results through good lookahead and heuristics and that a version of alpha beta pruning performs strongly. For random opponents, we show that we can frequently achieve solutions even on problems which lack a winning strategy and that. we can improve our success rate by using Existential Quantified Generalised Arc Consistency;a, lower level of consistency than SQGAC, to maximise pruning without removing solutions. We also consider the power of the universal opponent and show that through good heuristic selection we can generate a significantly stronger player than a static heuristic provides.
暂无评论