Invited Session Mon.2.H 3003A

Monday, 13:15 - 14:45 h, Room: H 3003A

Cluster 5: Constraint programming [...]

Improved representations for constraint programming


Chair: Jean-Charles Régin and Michel Rueher



Monday, 14:15 - 14:40 h, Room: H 3003A, Talk 3

Marie Pelleau
Octagonal domains for constraint programming

Coauthors: Frédéric Benhamou, Charlotte Truchet


Continuous Constraint Programming relies on interval representations of the variables domains. Filtering and solution set approximations are based on Cartesian products of intervals, called boxes. We propose to improve the Cartesian representation precision by introducing an n-ary octagonal representation of the domains in order to improve the propagation accuracy. The principles of constraint solving remain the same: reduce the domains by applying constraint propagators (filtering), by computing fixpoints of these operators (propagation) and by splitting the domains to search the solution space. Nevertheless, each of these steps is redesigned so as to take the new domains into account. Our contributions are the following: first, we show how to transform the initial constraint problem into an semantically equivalent problem on octagonal domains. Second, we define a specific local consistency, oct-consistency, and propose a propagation algorithm, built on top of any continuous filtering method. Third, we propose a split algorithm and a notion of precision adapted to the octagonal case. Pratical experiments show that the octagonal domains perform well on the Coconut benchmark.


  Payday Loans In Michigan. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra Without Prescription influence on blood clots.