Abstract Domains in Constraint Programming by Marie Pelleau

By Marie Pelleau

Constraint Programming goals at fixing demanding combinatorial difficulties, with a computation time expanding in perform exponentially. The tools are at the present time effective adequate to unravel huge commercial difficulties, in a known framework. despite the fact that, solvers are devoted to a unmarried variable kind: integer or genuine. fixing combined difficulties will depend on advert hoc differences. In one other box, summary Interpretation bargains instruments to end up software homes, by means of learning an abstraction in their concrete semantics, that's, the set of attainable values of the variables in the course of an execution. quite a few representations for those abstractions were proposed. they're known as summary domain names. summary domain names can combine any form of variables, or even signify kinfolk among the variables.

In this paintings, we outline summary domain names for Constraint Programming, with a purpose to construct a universal fixing approach, facing either integer and actual variables. We additionally research the octagons summary area, already outlined in summary Interpretation. Guiding the hunt through the octagonal family members, we receive reliable effects on a continuing benchmark. We additionally outline our fixing procedure utilizing summary Interpretation concepts, so as to comprise latest summary domain names. Our solver, AbSolute, is ready to remedy combined difficulties and use relational domains.

  • Exploits the over-approximation ways to combine AI instruments within the tools of CP
  • Exploits the relationships captured to resolve non-stop difficulties extra effectively
  • Learn from the builders of a solver in a position to dealing with virtually all summary domains

Show description

Read Online or Download Abstract Domains in Constraint Programming PDF

Similar software design & engineering books

Distributed Services with OpenAFS: for Enterprise and Education

This booklet indicates intimately how you can construct enterprise-level safe, redundant, and hugely scalable prone from scratch on most sensible of the open resource Linux working method, appropriate for small businesses in addition to titanic universities. The center structure awarded is predicated on Kerberos, LDAP, AFS, and Samba. it truly is proven easy methods to combine internet, message similar, info base and different companies with this spine.

Creating Mac Widgets with Dashcode (Firstpress)

With the arrival of Mac OSX Leopard and Dashcode, it has turn into really easy to write down your individual widgets (small courses that sometimes do one task). Even company humans can write little courses to do such things as graph revenues that immediately replace. So this booklet is written for all clients who should want to create their very own widgets.

Beyond Redundancy: How Geographic Redundancy Can Improve Service Availability and Reliability of Computer-Based Systems

How Geographic Redundancy Can increase carrier Availability and Reliability of Computer-Based SystemsEnterprises make major investments in geographically redundant structures to mitigate the impossible chance of a normal or man-made catastrophe rendering their fundamental web site inaccessible or destroying it thoroughly.

Additional info for Abstract Domains in Constraint Programming

Example text

Moreover, the definition of the abstract domains in CP gives the possibility of solving problems using non-Cartesian domain representations. 1. Introduction In CP, solving techniques strongly depend on the type of variables, and are even dedicated to a type of variables (integer or real). If a problem contains both integer and real variables, there are no solving methods. There are three possible solutions to this kind of problem with CP: the integers are transformed into real variables and integrity constraints are added to the problem (the propagation of these new constraints refine the bound of the integer variables [GRA 06]); the real varibales are discretized, the possible values for the real variables are enumerated with a given step [CHO 10]; or a discrete and a continuous solver are combined [COL 94, FAG 14] By looking more closely, we can see that regardless of the resolution method used, it alternates between propagation and 54 Abstract Domains in Constraint Programming exploration phases.

We present here only the HC as defined in [BEN 97b]. – Let v1 . . vn be the variables on continuous ˆ i , and C a domains represented with intervals D1 . . Dn ∈ I, Di ⊆ D constraint. Domains D1 . . Dn are said to be HC for C if and only if D1 × · · · × Dn is the smallest box with floating-point bounds containing the solutions for C in D1 × · · · × Dn . – Consider two variables (v1 , v2 ) on continuous domains D1 = D2 = [−1, 4] and the constraint v1 = 2v2 + 2. The hull-consistent domains for this CSP are D1 = [0, 4] and D2 = [−1, 1].

This method is detailed in the next section. 5. Local iterations The abstract transfer function F (α ◦ F ◦ γ) does not always compute efficiently the smallest abstract domain containing the considered expression, even though when it is optimal (γ ◦ F ◦ α) = F . To efficiently compute the result of the transfer functions, transfer functions often involve lower closure operators [GRA 92]. – An operator ρ : D → D is a lower closure operator if and only if ρ is: 1) monotonic, ∀X, Y ∈ D, X 2) reductive, ∀X ∈ D, ρ(X) Y ⇒ ρ(X) X; 3) idempotent, ∀X ∈ D, ρ(X) = (ρ ◦ ρ)X.

Download PDF sample

Rated 4.06 of 5 – based on 45 votes