Many combinatorial problems can be represented naturally as constraint satisfaction problems (CSP). However, in some domains the set of variables in a solution should change dynamically on the basis of assignments of ...
详细信息
ISBN:
(纸本)3540666265
Many combinatorial problems can be represented naturally as constraint satisfaction problems (CSP). However, in some domains the set of variables in a solution should change dynamically on the basis of assignments of values to variables. In this paper we argue that such dynamic constraint satisfaction problems (DCSP), introduced by Mittal and Falkenhainer, are more expressive than CSP in a knowledge representation sense. We then study the problem of generalizing the original DCSP with disjunctive activity constraints and default negation which are useful in, e.g., product configuration problems. the generalization is based on a novel definition of a solution to DCSP. It uses a fixpoint condition instead of the subset minimality condition in the original formulation. Our approach coincides withthe original definition when disjunctions and default negations are not allowed. However, it leads to lower computational complexity than if the original definition were generalized similarly. In fact we show that the generalized DCSP is NP-complete. As a proof of concept, we briefly describe two novel implementations of the original DCSP and give test results for them.
We provide here a simple, yet very general framework that allows us to explain several constraint propagation algorithms in a systematic way. In particular, using the notions commutativity and semi-commutativity, we s...
详细信息
Experience using constraintprogramming to solve real-life problems has shown that finding an efficient solution to the problem often requires experimentation with different constraint solvers or even building a probl...
详细信息
Model-based decision support systems rely on an explicit representation of some system whose dynamics is often qualitatively described by specifying the rates at which the system variables change. Such models are natu...
ISBN:
(纸本)3540666265
Model-based decision support systems rely on an explicit representation of some system whose dynamics is often qualitatively described by specifying the rates at which the system variables change. Such models are naturally represented as a set of ordinary differential equations (ODEs) which are parametric (they include parameters whose value is not known exactly). If safe decisions are to be made based on the values of these parameters, it is important to know them with sufficient precision.
A lot of workin constraint satisfaction has been focused on finding solutions to difficult problems. Many real life problems however, while not extremely complicated, have a huge number of solutions, few of which are ...
详细信息
Inaccurate scientific computation is useless at best and dangerous at worst. We address several major sources of inaccuracy. Roundoff error is well known and there is a great deal of work on minimizing it [Act96,Tay97...
ISBN:
(纸本)3540666265
Inaccurate scientific computation is useless at best and dangerous at worst. We address several major sources of inaccuracy. Roundoff error is well known and there is a great deal of work on minimizing it [Act96,Tay97]. By using interval constraints, we dont eliminate roundoff error, but we make it explicit, so each answer comes with a clear indication of its accuracy. Another source of error arises from misapplying an algorithm (e.g. starting the Newton method with a poor initial choice, or using a method in a case where it does not perform well). We propose a method for reducing the chance of numerical errors in scientific programming by casting the problem as the design of an appropriate constraint solving algorithm and then separating the algorithm design process into two steps.
Column generation is a state-of-the-art method for optimally solving difficult large-scale optimization problems such as airline crew assignment. We show how to apply column generation even if those problems have comp...
详细信息
We study here constraint satisfaction problems that are based on predefined, explicitly given finite constraints. To solve them we propose a notion of rule consistency that can be expressed in terms of rules derived f...
详细信息
the order in which the variables are assigned can have an enormous impact on the time taken by a backtracking search algorithm to solve a constraint satisfaction problem (CSP). the Brélaz heuristic is a dynamic v...
详细信息
Solving non-binary constraint satisfaction problems, a crucial challenge for the next years, can be tackled in two different ways: translating the non-binary problem into an equivalent binary one, or extending binary ...
详细信息
暂无评论