the geost constraint has been proposed to model and solve discrete placement problems involving multi-dimensional boxes (packing in space and time). the filtering technique is based on a sweeping algorithm that requir...
详细信息
ISBN:
(纸本)9783642153952
the geost constraint has been proposed to model and solve discrete placement problems involving multi-dimensional boxes (packing in space and time). the filtering technique is based on a sweeping algorithm that requires the ability for each constraint to compute a forbidden box around a given fixed point and within a. surrounding area.. Several cases have been studied so far, including integer linear inequalities. Motivated by the placement of objects with curved shapes, this paper shows how to implement this service for continuous constraints with arbitrary mathematical expressions. the approach relies on symbolic processing and defines a new interval arithmetic.
We study the expressibility problem: given a finite constraint language F on a finite domain and another relation R, can F express R? We prove, by an explicit family of examples;that the standard witnesses to expressi...
详细信息
ISBN:
(纸本)9783642153952
We study the expressibility problem: given a finite constraint language F on a finite domain and another relation R, can F express R? We prove, by an explicit family of examples;that the standard witnesses to expressibility and inexpressibility (gadgets/formulas/conjunctive queries and polymorphisms respectively) may be required to be exponentially larger than the instances. We also show that the full expressibility problem is co-NEXPTIME-hard. Our proofs hinge on a novel interpretation of a tiling problem into the expressibility problem.
the recent series 5 of the Answer Set programming (ASP) system clingo provides generic means to enhance basic ASP withtheory reasoning capabilities. We instantiate this framework with different forms of linear constr...
详细信息
the recent series 5 of the Answer Set programming (ASP) system clingo provides generic means to enhance basic ASP withtheory reasoning capabilities. We instantiate this framework with different forms of linear constraints and elaborate upon its formal properties. Given this, we discuss the respective implementations, and present techniques for using these constraints in a reactive context. More precisely, we introduce extensions to clingo with difference and linear constraints over integers and reals, respectively, and realize them in complementary ways. Finally, we empirically evaluate the resulting clingo derivatives clingo[dl] and clingo[lp] on common language fragments and contrast them to related ASP systems.
Tolerant Algebraic Side-Channel Attack (TASCA) is a combination of algebraic and side-channel analysis with error tolerance. Oren et al., used mathematical programming to implement TASCA over a round-limited version o...
详细信息
ISBN:
(数字)9783319983349
ISBN:
(纸本)9783319983349;9783319983332
Tolerant Algebraic Side-Channel Attack (TASCA) is a combination of algebraic and side-channel analysis with error tolerance. Oren et al., used mathematical programming to implement TASCA over a round-limited version of AES. In [7], Liu et al. revisited their results and introduced a TASCA-cp model that delivers solutions to this 1-round relaxation with orders of magnitude improvement in both solving time and memory consumption. this paper extends the result and considers TASCA for the full 10-rounds AES algorithm. Two approaches are introduced: staged and integrated. the staged approach uses TASCA-cp as a spring board to enumerate and check its candidate solutions against the requirements of subsequent rounds. the integrated model formulates all the rounds of AES together with side-channel constraints on all rounds within a single unified optimization model. Empirical results shows both approaches are suitable to find the correct key of AES while the integrated model dominates the staged both in simplicity and solving time.
Research on constraint propagation has primarily focused on designing polynomial-time propagators sometimes at the cost of a weaker filtering. Interestingly, the evolution of constraintprogramming over sets have been...
详细信息
ISBN:
(纸本)9783642153952
Research on constraint propagation has primarily focused on designing polynomial-time propagators sometimes at the cost of a weaker filtering. Interestingly, the evolution of constraintprogramming over sets have been diametrically different. the domain representations are becoming increasingly expensive computationally and theoretical results appear to question the wisdom of these research directions. this paper explores this apparent contradiction by pursuing even more complexity in the domain representation and the filtering algorithms. It shows that;the product of the length-lex and subset-bound domains improves filtering and produces orders of magnitude improvements over existing approaches on standard benchmarks. Moreover, the paper proposes exponential-time algorithms for NP-hard intersection constraints and demonstrates that they bring significant performance improvements and speeds up constraint propagation considerably.
Integration of explanations into a CSP solver is a technique addressing difficult question "why my problem has no solution". Besides providing some sort of answer to the user, explanations can be used for de...
详细信息
Feature modeling has been found very effective for modeling and managing variability in Software Product Lines. the nature of feature models invites, sometimes even requires, the use of global constraints. this paper ...
详细信息
ISBN:
(纸本)9783642153952
Feature modeling has been found very effective for modeling and managing variability in Software Product Lines. the nature of feature models invites, sometimes even requires, the use of global constraints. this paper lays the groundwork for the inclusion of global constraints in automated reasoning on feature models. We present a mapping from extended feature models to constraint logic programming over finite domains, and show that this mapping enables using global constraints on feature attributes, as well as features, for a variety of analysis operations on feature models. We also present performance test results and discuss the benefits of using global constraints.
In this paper we show that the power of using k-consistency techniques in a constraint problem is precisely captured by using a particular inference rule, which we call positive-hyper-resolution, on the direct Boolean...
详细信息
ISBN:
(纸本)9783642153952
In this paper we show that the power of using k-consistency techniques in a constraint problem is precisely captured by using a particular inference rule, which we call positive-hyper-resolution, on the direct Boolean encoding of the CSP instance. We also show that current clause-learning SAT-solvers will deduce any positive-hyper-resolvent of a fixed size from a given set of clauses in polynomial expected time. We combine these two results to show that, without being explicitly designed to do so, current clause-learning SAT-solvers efficiently simulate k-consistency techniques, for all values of k. We then give some experimental results to show that this feature allows clause-learning SAT-solvers to efficiently solve certain families of CSP instances which are challenging for conventional cp solvers.
We show in this article(1) how the Weighted CSP framework can be used to solve an optimisation version of numerical planning. the WCSP finds an optimal plan in the planning graph containing all solution plans of minim...
详细信息
ISBN:
(纸本)3540462678
We show in this article(1) how the Weighted CSP framework can be used to solve an optimisation version of numerical planning. the WCSP finds an optimal plan in the planning graph containing all solution plans of minimum length. Experimental trials were performed to study the impact of soft arc consistency techniques (FDAC and EDAC) on the efficiency of the search for an optimal plan in this graph. We conclude by giving a possible theoretical explanation for the fact that we were able to solve optimisation problems involving several hundred variables.
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.
暂无评论