Global constraints are used in constraintprogramming to help users specify patterns that occur frequently in the real world. In addition, global constraints facilitate the use of efficient constraint propagation algo...
详细信息
ISBN:
(纸本)9783540898115
Global constraints are used in constraintprogramming to help users specify patterns that occur frequently in the real world. In addition, global constraints facilitate the use of efficient constraint propagation algorithms for problem solving. Many of the most common global constraints used in constraintprogramming use filtering algorithms based on network flow theory. We show how we can formulate global constraints such as GCC, Among, and their combinations, in terms of a tractable set-intersection problem called Two Families Of Sets (TFOS). We demonstrate that the TFOS problem allows us to represent tasks that are often difficult to model in terms of a classical constraint satisfaction paradigm. In the final part of the paper we specify some tractable and intractable extensions of the TFOS problem. the contribution of this paper is the characterisation of a general framework that helps us to study the tractability of global constraints that rely on filtering algorithms based on network flow theory.
this paper presents a theoretical framework for the integration of the cooperative constraintsolving of several algebraic domains into higher-order functional and logicprogramming on A-abstractions, using an instanc...
详细信息
ISBN:
(纸本)9783642177958
this paper presents a theoretical framework for the integration of the cooperative constraintsolving of several algebraic domains into higher-order functional and logicprogramming on A-abstractions, using an instance of a generic constraint Functional logicprogramming (CFLP) scheme over a so-called higher-order coordination domain. We provide this framework as a powerful computational model for the higher-order cooperation of algebraic constraint domains over real numbers and integers, which has been useful in practical applications involving the hybrid combination of its components, so that more declarative and efficient solutions can be promoted. Our proposal of computational model has been proved sound and complete with respect to the declarative semantics provided by the CFLP scheme, and enriched with new mechanisms for modeling the intended cooperation among the algebraic domains and a novel higher-order constraint domain equipped with a sound and complete constraint solver for solving higher-order equations. We argue the applicability of our approach describing a prototype implementation on top of the constraint functional logic system TOY.
In the analysis of hybrid discrete-continuous systems, rich arithmetic constraint formulae with complex Boolean structure arise naturally. the iSAT algorithm, a solver for such formulae, is aimed at bounded model chec...
详细信息
ISBN:
(纸本)9783642032509
In the analysis of hybrid discrete-continuous systems, rich arithmetic constraint formulae with complex Boolean structure arise naturally. the iSAT algorithm, a solver for such formulae, is aimed at bounded model checking of hybrid systems. In this paper, we identify, challenges emerging from planned and ongoing work to enhance the iSAT algorithm. First, we propose an extension of iSAT to directly handle ordinary differential equations as constraints. Second, we outline the recently introduced generalization of the iSAT algorithm to deal with probabilistic hybrid systems and some open research issues in that context. third, we present ideas on how to move from bounded to unbounded model checking by using the concept of interpolation. Finally, we discuss the adaption of some parallelization techniques to the iSAT case, which will hopefully lead to performance gains in the future. By presenting these open research questions, this paper aims at fostering discussions oil these extensions of constraintsolving.
this book describes recent findings in the domain of Boolean logic and Boolean algebra, covering application domains in circuit and system design, but also basic research in mathematics and theoretical computer scienc...
ISBN:
(纸本)9783030203221
this book describes recent findings in the domain of Boolean logic and Boolean algebra, covering application domains in circuit and system design, but also basic research in mathematics and theoretical computer science. Content includes invited chapters and a selection of the best papers presented at the 13thannualinternationalworkshop on Boolean Problems. Provides a single-source reference to the state-of-the-art research in the field of logic synthesis and Boolean techniques; Includes a selection of the best papers presented at the 13thannualinternationalworkshop on Boolean Problems; Covers Boolean algebras, Boolean logic, Boolean modeling, Combinatorial Search, Boolean and bitwise arithmetic, Software and tools for the solution of Boolean problems, Applications of Boolean logic and algebras, Applications to real-world problems, Boolean constraintsolving, and Extensions of Boolean logic.
In this work we represent the Optimal Stable Marriage problem as a Soft constraint Satisfaction Problem. In addition, we extend this problem from couples of individuals to coalitions of generic agents, in order to def...
详细信息
ISBN:
(纸本)9783642032509
In this work we represent the Optimal Stable Marriage problem as a Soft constraint Satisfaction Problem. In addition, we extend this problem from couples of individuals to coalitions of generic agents, in order to define new coalition-formation principles and stability conditions. In the coalition case, we suppose the preference value as a trust score, since trust can describe the belief of a node in the capabilities of another node, in its honesty and reliability. Semiring-based soft constraints represent a general and expressive framework that is able to deal with distinct concepts of optimality by only changing the related c-semiring structure, instead of using different ad-hoc algorithms. At last, we propose an implementation of the classical OSM problem using integer linear programming tools.
We present algorithms that perform the extraction of partial assignments from binary constraint Satisfaction Problems without introducing new constraints. they are based on a new perspective on domain values: we view ...
详细信息
ISBN:
(纸本)9783540738169
We present algorithms that perform the extraction of partial assignments from binary constraint Satisfaction Problems without introducing new constraints. they are based on a new perspective on domain values: we view a value not as a single, indivisible unit, but as a combination of value fragments. Applications include removing nogoods while maintaining constraint arity, learning nogoods in the constraint network, enforcing on neighborhood inverse consistency and removal of unsolvable sub-problems from the constraint network.
In this paper, we present a rule-based modelling language for constraintprogramming, called Rules2CP. Unlike other modelling languages, Rules2CP adopts a single knowledge representation paradigm based on rules withou...
详细信息
ISBN:
(纸本)9783642032509
In this paper, we present a rule-based modelling language for constraintprogramming, called Rules2CP. Unlike other modelling languages, Rules2CP adopts a single knowledge representation paradigm based on rules without recursion, and a. restricted set of data structures based on records and enumerated lists given with iterators. We show that this is sufficient to model constraint satisfaction problems, together with search strategies where search trees are expressed by logical formulae, and heuristic choice criteria are defined by preference orderings on variables and formulae. We describe the compilation of Rules2CP statements to constraint programs over finite domains, by a, term rewriting system and partial evaluation. We prove the confluence of these transformations and provide a complexity bound on the size of the generated programs. the expressiveness of Rules2CP is illustrated first with simple examples, and then with a complete library for packing problems, called PKML, which, in addition to pure bin packing and bin design problems, can deal with common sense rules about weights, stability, as well is specific packing business rules. the performances of boththe compiler and the generated code are evaluated on Korf's benchmarks of optimal rectangle packing problems.
constraint Handling Rules (CHR) is a concurrent, committed-choice, rule-based language. One of the first CHR programs is the classic constraint solver for syntactic equality of rational trees that performs unification...
详细信息
ISBN:
(纸本)9783540738169
constraint Handling Rules (CHR) is a concurrent, committed-choice, rule-based language. One of the first CHR programs is the classic constraint solver for syntactic equality of rational trees that performs unification. We first prove its exponential complexity in time and space for non-flat equations and deduce from this proof a quadratic complexity for flat equations. We then present an extended CHR solver for solving existentially quantified conjunctions of non-flat equations in the theory of finite or infinite trees. We reach a quadratic complexity by first flattening the equations and introducing new existentially quantified variables, then using the classic solver, and finally eliminating particular equations and quantified variables.
this book constitutes the refereed conference proceedings of the 20thinternationalworkshop on Functional and constraintlogicprogramming, WFLP 2011, held in Odense, Denmark, in July 2011 as Part of the 13th Interna...
详细信息
ISBN:
(数字)9783642225314
ISBN:
(纸本)9783642225307
this book constitutes the refereed conference proceedings of the 20thinternationalworkshop on Functional and constraintlogicprogramming, WFLP 2011, held in Odense, Denmark, in July 2011 as Part of the 13thinternational Symposium on Principles and Practice of Declarative programming (PPDP 2011), the 22st international Symposium on logic-Based Program Synthesis and Transformation (LOPSTR 2011), and the 4thinternationalworkshop on Approaches and Applications of Inductive programming (AAIP 2011).
From the 10 papers submitted, 9 were accepted for presentation the proceeding. the papers cover current research in all areas of functional and logicprogramming as well as the integration of constraintlogic and object-oriented programming, and term rewriting.
Many agent coordination problems can be modeled as distributed constraint optimization (DCOP) problems. ADOPT is an asynchronous and distributed search algorithm that is able to solve DCOP problems optimally. In this ...
详细信息
ISBN:
(纸本)9783642032509
Many agent coordination problems can be modeled as distributed constraint optimization (DCOP) problems. ADOPT is an asynchronous and distributed search algorithm that is able to solve DCOP problems optimally. In this paper, we introduce Iterative Decreasing Bound ADOPT (IDB-ADOPT), a modification of ADOPT that changes the search strategy of ADOPT from performing one best-first search to performing a series of depth-first searches. Each depth-first search is provided with a bound, initially a, large integer, and returns the first solution whose cost is smaller than or equal to the bound. the bound is then reduced to the cost of this solution minus one and the process repeats. If there is no solution whose cost is smaller than or equal to the bound, it returns a. cost-minimal solution. thus, IDB-ADOPT is an anytime algorithm that solves DCOP problems with integer costs optimally. Our experimental results for graph coloring problems show that IDB-ADOPT runs faster (that is, needs fewer cycles) than ADOPT oil large DCOP problems, with savings of up to one order of magnitude.
暂无评论