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.
Traditional constraint-programming systems provide the concept of variable views which implement a view of the type y = f(x) by delegating operations on variable y to variable x. While the traditional support is limit...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Traditional constraint-programming systems provide the concept of variable views which implement a view of the type y = f(x) by delegating operations on variable y to variable x. While the traditional support is limited to bound consistency, this paper offers views that support domain consistency without any limitations. this paper proposes the alternative concept of domain views which delegate all domain operations. Domain views preserve the benefits of variable views, simplify the implementation of value-based propagation, and also support noninjective views compositionally. Experimental results demonstrate the practical benefits of domain views. the paper also reveals a subtle interaction between views and the exploitation of constraint idempotence, which may lead to incomplete propagation.
the ability to verify critical software is a key issue in embedded and cyber physical systems typical of automotive, aeronautics or aerospace industries. Bounded model checking and constraintprogramming approaches se...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
the ability to verify critical software is a key issue in embedded and cyber physical systems typical of automotive, aeronautics or aerospace industries. Bounded model checking and constraintprogramming approaches search for counter-examples that exemplify a property violation. the search of such counter-examples is a long, tedious and costly task especially for programs performing floating point computations. Indeed, available search strategies are dedicated to finite domains and, to a lesser extent, to continuous domains. In this paper, we introduce new strategies dedicated to floating point constraints. they take advantage of the properties of floating point domains (e.g., domain density) and of floating point constraints (e.g., floating point arithmetic) to improve the search for floating point constraint problems. First experiments on a set of realistic benchmarks show that such dedicated strategies outperform standard search and splitting strategies.
the generalization of the constraint satisfaction problem with universal quantifiers is a challenging PSPACE-complete problem, which is interesting theoretically and also relevant to solving other PSPACE problems aris...
详细信息
ISBN:
(纸本)3540292381
the generalization of the constraint satisfaction problem with universal quantifiers is a challenging PSPACE-complete problem, which is interesting theoretically and also relevant to solving other PSPACE problems arising in AI, such as reasoning with uncertainty, and multiplayer games. I define two new levels of consistency for QCSP, and give an algorithm to enforce consistency for one of these definitions. the algorithm is embedded in backtracking search, and tested empirically. the aims of this work are to increase the facilities available for modelling and to increase the power of constraint propagation for QCSPs. the work is motivated by examples from adversarial games.
We use a local search method we term Large Neighbourhood Search (LNS) to solve vehicle routing problems. LNS is analogous to the shuffling technique of job-shop scheduling, and so meshes well withconstraint programmi...
详细信息
ISBN:
(纸本)3540652248
We use a local search method we term Large Neighbourhood Search (LNS) to solve vehicle routing problems. LNS is analogous to the shuffling technique of job-shop scheduling, and so meshes well withconstraintprogramming technology. LNS explores a large neighbourhood of the current solution by selecting a number of "related" customer visits to remove from the set of planned routes. and re-inserting these visits using a constraint-based tree search. Unlike similar methods, we use Limited Discrepancy Search during the tree search to re-insert visits. We analyse the performance of our method on benchmark problems. We demonstrate that results produced are competitive with Operations Research meta-heuristic methods. indicating that constraint-based technology is directly applicable to vehicle routing problems.
We study a family of problems, called MAXIMUM SOLUTION, where the objective is to maximise a linear goal function over the feasible integer assignments to a set of variables subject to a set of constraints. this probl...
详细信息
ISBN:
(纸本)3540462678
We study a family of problems, called MAXIMUM SOLUTION, where the objective is to maximise a linear goal function over the feasible integer assignments to a set of variables subject to a set of constraints. this problem is closely related to INTEGER LINEAR programming. When the domain is Boolean (i.e. restricted to 10, 11), the maximum solution problem is identical to the well-studied MAX ONES problem, and the approximability is completely understood for all restrictions on the underlying constraints. We continue this line of research by considering domains containing more than two elements. We present two main results: a complete classification for the approximability of all maximal constraint languages, and a complete classification of the approximability of the problem when the set of allowed constraints contains all permutation constraints. Our results are proved by using algebraic results from clone theory and the results indicates that this approach is very useful for classifying the approximability of certain optimisation problems.
Fixed-width MDDs were introduced recently as a more refined alternative for the domain store to represent partial solutions to CSPs. In this work, we present a systematic approach to MDD-based constraintprogramming. ...
详细信息
ISBN:
(纸本)9783642153952
Fixed-width MDDs were introduced recently as a more refined alternative for the domain store to represent partial solutions to CSPs. In this work, we present a systematic approach to MDD-based constraintprogramming. First, we introduce a generic scheme for constraint propagation in MDDs. We show that all previously known propagation algorithms for MDDs can be expressed using this scheme. Moreover, we use the scheme to produce algorithms for a number of other constraints, including Among, Element, and unary resource constraints. Finally, we discuss an implementation of our MDD-based CP solver, and provide experimental evidence of the benefits of MDD-based constraintprogramming.
Call control features (e.g., call-divert, voice-mail) are primitive options to which users can subscribe off-line to personalise their service. the configuration of a feature subscription involves choosing and sequenc...
详细信息
ISBN:
(纸本)9783540859574
Call control features (e.g., call-divert, voice-mail) are primitive options to which users can subscribe off-line to personalise their service. the configuration of a feature subscription involves choosing and sequencing features from a catalogue and is subject to constraints that prevent undesirable feature interactions at run-time. When the subscription requested by a user is inconsistent, one problem is to find an optimal relaxation. In this paper, we show that this problem is NP-hard and we present a constraintprogramming formulation using the variable weighted constraint satisfaction problem framework. We also present simple formulations using partial weighted maximum satisfiability and integer linear programming. We experimentally compare our formulations of the different approaches;the results suggest that our constraintprogramming approach is the best of the three overall.
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.
in this paper, we propose a constraint-based approach to determining protein structures compatible with distance constraints obtained from Nuclear Magnetic Resonance (NMR) data. We compare the performance of our propo...
详细信息
ISBN:
(纸本)3540666265
in this paper, we propose a constraint-based approach to determining protein structures compatible with distance constraints obtained from Nuclear Magnetic Resonance (NMR) data. We compare the performance of our proposed algorithm with DYANA ("Dynamics algorithm for NMR applications" [1]) an existing commercial application based on simulated annealing. For our test case, computation time for DYANA was more than six hours, whereas the method we propose produced similar results in 8 minutes, so we show that the application of constraintprogramming (CP) technology can greatly reduce computation time. this is a major advantage because this NMR technique generally demands multiple runs of structural computation.
暂无评论