constraintprogramming (CP) and propositional satisfiability (SAT) based framework for modeling and solving pattern mining tasks has gained a considerable audience in recent years. However, this nice declarative and g...
详细信息
ISBN:
(数字)9783319983349
ISBN:
(纸本)9783319983349;9783319983332
constraintprogramming (CP) and propositional satisfiability (SAT) based framework for modeling and solving pattern mining tasks has gained a considerable audience in recent years. However, this nice declarative and generic framework encounters a scaling problem. the huge size of constraints networks/propositional formulas encoding large datasets is identified as the main bottleneck of most existing approaches. In this paper, we propose a parallel SAT based framework for itemset mining problem to push forward the solving efficiency. the proposed approach is based on a divide-and-conquer paradigm, where the transaction database is partitioned using item-based guiding paths. Such decomposition allows us to derive smaller and independent Boolean formulas that can be solved in parallel. the performance and scalability of the proposed algorithm are evaluated through extensive experiments on several datasets. We demonstrate that our partition-based parallel SAT approach outperforms other CP approaches even in the sequential case, while significantly reducing the performances gap with specialized approaches.
Translating procedural object oriented code into constraints is required for many processes that reason about the execution of this code. the most obvious is for symbolic execution of the code, where the code is execu...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
Translating procedural object oriented code into constraints is required for many processes that reason about the execution of this code. the most obvious is for symbolic execution of the code, where the code is executed without necessarily knowing the concrete values. In this paper, we discuss translations from procedural object oriented code to constraints in the context of solving optimisation problems defined via simulation. A key difficulty arising in the translation is the modelling of state changes. We introduce a new technique for modelling destructive assignments that outperforms previous approaches. Our results show that the optimisation models generated by our technique can be as efficient as equivalent hand written models.
this paper studies how to generalize Lagrangian relaxation to high-level optimization models, including constraint-programming and local search models. It exploits the concepts of constraint violation (typically used ...
详细信息
the Distributed constraint Optimization Problem (DCOP) is a powerful framework for modeling and solving applications in multi-agent coordination. Asynchronous Forward Bounding (AFB_BJ) is one of the best algorithms to...
详细信息
ISBN:
(纸本)9783642406263;9783642406270
the Distributed constraint Optimization Problem (DCOP) is a powerful framework for modeling and solving applications in multi-agent coordination. Asynchronous Forward Bounding (AFB_BJ) is one of the best algorithms to solve DCOPs. We propose AFB_BJ(+), a revisited version of AFB_BJ in which we refine the lower bound computations. We also propose to compute lower bounds for the whole domain of the last assigned agent instead of only doing this for its current assignment. this reduces boththe number of messages needed and the time future agents remain idle. In addition, these lower bounds can be used as a value ordering heuristic in AFB_BJ(+). the experimental evaluation on standard benchmark problems shows the efficiency of AFB_BJ(+) compared to other algorithms for DCOPs.
the primary contribution of this paper consists in using the AND/OR search paradigm [1,2] to define the new concept of semantic width of a constraint network. the well known parameter tree-width is graph based, and ca...
详细信息
Session-based concurrency is a type-based approach to the analysis of communication-intensive systems. Correct behavior in these systems may be specified in an operational or declarative style: the former defines how ...
详细信息
ISBN:
(纸本)9781450335164
Session-based concurrency is a type-based approach to the analysis of communication-intensive systems. Correct behavior in these systems may be specified in an operational or declarative style: the former defines how interactions are structured;the latter defines governing conditions. In this paper, we investigate the relationship between operational and declarative models of session-based concurrency. We propose two interpretations of session pi-calculus processes as declarative processes in linear concurrent constraintprogramming (1cc). they offer a basis on which both operational and declarative requirements can be specified and reasoned about. By coupling our interpretations with a type system for 1cc, we obtain robust declarative encodings of pi-calculus mobility.
Dealing with domains involving substantial quantitative information in Answer Set programming (ASP) often results in cumbersome and inefficient encodings. Hybrid "CASP" languages combining ASP and constraint...
详细信息
Dealing with domains involving substantial quantitative information in Answer Set programming (ASP) often results in cumbersome and inefficient encodings. Hybrid "CASP" languages combining ASP and constraintprogramming aim to overcome this limitation, but also impose inconvenient constraints - first and foremost that quantitative information must be encoded by means of total functions. this goes against central knowledge representation principlesthat contribute to the power of ASP, and makes the formalization of certain domains difficult. ASP{f} is being developed withthe ultimate goal of providing scientists and practitioners with an alternative to CASP languages that allows for the efficient representation of qualitative and quantitative information in ASP without restricting one's ability to deal with incompleteness or uncertainty. In this paper we present the latest outcome of such research: versions of the language and of the supporting system that allow for practical, industrial-size use and scalability. the applicability of ASP{f} is demonstrated by a case study on an actual industrial application.
the paper introduces value precedence on integer and set sequences. A useful application of the notion is in breaking symmetries of indistinguishable values, an important class of symmetries in practice. Although valu...
详细信息
the assembly problem is the spatial joining of separate rigid bodies within a CAD/CAM-system. the solution to the assembly does not only need to contain one consistent instantiation, but also qualitative information. ...
详细信息
ISBN:
(纸本)3540652248
the assembly problem is the spatial joining of separate rigid bodies within a CAD/CAM-system. the solution to the assembly does not only need to contain one consistent instantiation, but also qualitative information. In particular, this covers the localization of redundancy and remaining degrees of freedom in the mechanism. Although it is natural to model the assembly as a constraint satisfaction problem (CSP), solving remains a difficult task In general, a CSP can be attacked by two strategies: consistency enforcement and search. Algorithms work best if they combine these strategies in a clever way. When modeling the assembly problem as a CSP, one is confronted with two special conditions. First, the variable domains are continuous. Second, constraints are not arbitrary, but are conjunctions of instantiated predefined constraint types. thus, search is not possible because of the continuous domains and numeric iterative or interval approaches deliver no information on degrees of freedom and redundancy. therefore, pure consistency enforcement, which has many drawbacks in general CSPs, is the best choice
暂无评论