constraint problems with incomplete or erroneous data are often simplified to tractable deterministic models, or modified using error correction methods, withthe aim of seeking a solution. However, this can lead us t...
详细信息
ISBN:
(纸本)3540202021
constraint problems with incomplete or erroneous data are often simplified to tractable deterministic models, or modified using error correction methods, withthe aim of seeking a solution. However, this can lead us to solve the wrong problem because of the approximations made. Such an outcome is of little help to a user who expects the right problem to be tackled and reliable information returned. the certainty closure framework we present aims to provide the user with reliable insight by: (1) enclosing the uncertainty using what is known for sure about the data, to guarantee that the true problem is contained in the model so described, (2) deriving a closure, a set of possible solutions to the uncertain constraint problem. In this paper we first demonstrate the benefits of reliable constraint reasoning on two different case studies, and then generalise our approaches into a formal framework.
constraint satisfaction has been applied with great success in closed-world scenarios, where all options and constraints are known from the beginning and fixed. Withthe internet, many of the traditional CSP applicati...
详细信息
ISBN:
(纸本)3540202021
constraint satisfaction has been applied with great success in closed-world scenarios, where all options and constraints are known from the beginning and fixed. Withthe internet, many of the traditional CSP applications in resource allocation, scheduling and planning pose themselves in open-world settings, where options and constraints must be gathered from different agents in a network. We define open constraint optimization as a model of such tasks. Under the assumption that options are discovered in decreasing order of preference, it becomes possible to guarantee optimality even when domains and constraints are not completely known. We propose several algorithms for solving open constraint optimization problems by incrementally gathering options through the network. We report empirical results on their performance on random problems, and analyze how to achieve optimality with a minimal number of queries to the information sources.
We study from a formal perspective the consistency and propagation of constraints involving multiset variables. that is, variables whose values are multisets. these help us model problems more naturally and can, for e...
详细信息
ISBN:
(纸本)3540202021
We study from a formal perspective the consistency and propagation of constraints involving multiset variables. that is, variables whose values are multisets. these help us model problems more naturally and can, for example, prevent introducing unnecessary symmetry into a model. We identify a number of different representations for multiset variables and compare them. We then propose a definition of local consistency for constraints involving multiset, set and integer variables. this definition is a generalization of the notion of bounds consistency for integer variables. We show how this local consistency property can be enforced by means of some simple inference rules which tighten bounds on the variables. We also study a number of global constraints on set and multiset variables. Surprisingly, unlike finite domain variables, the decomposition of global constraints over set or multiset variables often does not hinder constraint propagation.
In this paper we study the applicability of bucket elimination (BE) to the problem of finding still-life patterns. Very recently, it has been tackled using integer programming and constraintprogramming, both of them ...
详细信息
ISBN:
(纸本)3540202021
In this paper we study the applicability of bucket elimination (BE) to the problem of finding still-life patterns. Very recently, it has been tackled using integer programming and constraintprogramming, both of them being search-based methods. We show that BE, which is based on dynamic programming, provides an exponentially lower worst-case time complexity than search methods. Unfortunately, BE requires exponential space, which is a disadvantage over the polynomial space requirement of depth-first search. With our experiments, we show that BE is quite competitive with search-based approaches. It clearly outperforms simple encodings and it is comparable with dedicated methods. While the best current search approach solves the n = 14 instance in about 6 cpu days, BE solves it in about 1 day. BE cannot solve the n = 15 instance due to space exhaustion (this instance is solved by search in 8 days). Finally, we show how BE can be adapted to exploit the problem symmetries, with which in several cases we outperform previous results in a relaxation of the problem which restrict solutions to symmetric patterns, only.
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.
Counting the number of solutions to CSP instances has vast applications in several areas ranging from statistical physics to artificial intelligence. We provide a new algorithm for counting the number of solutions to ...
详细信息
ISBN:
(纸本)3540202021
Counting the number of solutions to CSP instances has vast applications in several areas ranging from statistical physics to artificial intelligence. We provide a new algorithm for counting the number of solutions to binary CSP s which has a time complexity ranging from O ((d/4 . alpha(4))(n)) to O((alpha + alpha(5) + [d/4 - 1] . alpha(4))(n)) (where alpha approximate to 1.2561) depending on the domain size d greater than or equal to 3. this is substantially faster than previous algorithms, especially for small d. We also provide an algorithm for counting k-colourings in graphs and its running time ranges from O ([log(2) k](n)) to O ([log(2) k + 1](n)) depending on k greater than or equal to 4. Previously, only an O(1.8171(n)) time algorithm for counting 3-colourings were known, and we improve this upper bound to O(1.7879(n)).
this paper offers a critique of the framework of constraint Satisfaction Problems. While this framework has been successful in studying search techniques, and has inspired some constraintprogramming languages, it has...
详细信息
Engineering conceptual design can be defined as that phase of the product development process during which the designer takes a specification for a product to be designed and generates many broad solutions for it. It ...
详细信息
ISBN:
(纸本)3540202021
Engineering conceptual design can be defined as that phase of the product development process during which the designer takes a specification for a product to be designed and generates many broad solutions for it. It is well recognized that few computational tools exist that are capable of supporting the designer work through the conceptual phase of design. However, significant recent developments have been made in solid modeling and 3D computer-aided design. the use of such tools has become a critical element in the more sophisticated product development processes to be found in modem industry. this paper presents a prototype constraint-based computer-aided design (CAD) technology that can be used to support designers working in the early stages of design. the technology has been developed as an add-in application for Autodesk Inventor, a 3D solid-modeling environment. the add-in has, at its core, a constraint filtering system based on generalised arc-consistency processing and backtrack search. We present our current prototype and a detailed demonstration of its functionality. Finally, we describe our current work on a number of additional features for the next prototype, which will be deployed in an industrial context.
暂无评论