The Smart Table Constraint
Table Constraints are very useful for modeling combinatorial problems in Constraint Programming (CP). They are a universal mechanism for representing constraints, but unfortunately the size of their tables can grow exponentially with their arities. In thi
- PDF / 864,426 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 72 Downloads / 204 Views
ICTEAM, Universit´e catholique de Louvain, 1348 Louvain-la-Neuve, Belgium {jean-baptiste.mairy,yves.deville}@uclouvain.be 2 CRIL-CNRS UMR 8188, Universit´e d’Artois, F-62307 Lens, France [email protected] Abstract. Table Constraints are very useful for modeling combinatorial problems in Constraint Programming (CP). They are a universal mechanism for representing constraints, but unfortunately the size of their tables can grow exponentially with their arities. In this paper, we propose to authorize entries in tables to contain simple arithmetic constraints, replacing classical tuples of values by so-called smart tuples. Smart table constraints can thus be viewed as logical combinations of those simple arithmetic constraints. This new form of tuples allows us to encode compactly many constraints, including a dozen of well-known global constraints. We show that, under a very reasonable assumption about the acyclicity of smart tuples, a Generalized Arc Consistency algorithm of low time complexity can be devised. Our experimental results demonstrate that the smart table constraint is a highly promising general purpose tool for CP.
Table constraints explicitly express the allowed combinations of values as sets of tuples, which are called tables. Table constraints can theoretically encode any kind of constraints and are amongst the most useful ones in Constraint Programming (CP). Indeed, they are often required when modeling combinatorial problems in many application fields. The design of filtering algorithms for such constraints has generated a lot of research effort, see [2,8,14–16,19,21,24,27]. The biggest problem with table constraints are their size. Several approaches have been proposed to reduce this size. Two of them modify the definition of classical tuples: compressed tuples [12,25,30] and short supports applied to table constraints [10]. Compressed tuples allow tuples entries to contain sets. A compressed tuple thus represents all the tuples in the cartesian product of the sets. Short supports applied to table constraints allow variables to be left out of the short tuple. Left-out variables can take any values from their domains. In this paper, we propose to generalize both compressed tuples and short supports in table constraints by authorizing tuples to contain simple arithmetic constraints. We call such tuples smart tuples, and tables containing smart tuples smart tables. For instance, the following set of tuples {(1, 2, 1), (1, 3, 1), (2, 2, 2), (2, 3, 2), (3, 2, 3), (3, 3, 3)} on variables {x1 , x2 , x3 } with domains {1, 2, 3} can be represented by a smart table containing only one smart tuple: x1 = x3
x2 ≥2
x3 ∗
c Springer International Publishing Switzerland 2015 L. Michel (Ed.): CPAIOR 2015, LNCS 9075, pp. 271–287, 2015. DOI: 10.1007/978-3-319-18008-3 19
272
J.-B. Mairy et al.
or in an equivalent form by (x1 = x3 , x2 ≥ 2). A symbol ∗ in the tabular form of a smart tuple means that, if not occurring anywhere else, the corresponding variable is not constrained at all by the tuple (which is not the
Data Loading...
