A generic arc-consistency algorithm and its specializations.

*(English)*Zbl 0763.68059Summary: Consistency techniques have been studied extensively in the past as a way of tackling constraint satisfaction problems (CSP). In particular, various arc-consistency algorithms have been proposed, originating from Waltz’s filtering algorithm [D. Waltz, Generating semantic descriptions from drawings of scenes with shadows, Tech. Rept. AI271, MIT, Cambridge, MA (1972)] and culminating in the optimal algorithm AC-4 of R. Mohr and T. C. Henderson [Arc and path consistency revisited, Artif. Intell. 28, 225-233 (1986)]. AC-4 runs in \(O(ed^ 2)\) in the worst case, where \(e\) is the number of arcs (or constraints) and \(d\) is the size of the largest domain. Being applicable to the whole class of (binary) CSP, these algorithms do not take into account the semantics of constraints.

We present a new generic arc-consistency algorithm AC-5. This algorithm is parametrized on two specified procedures and can be instantiated to reduce to AC-3 and AC-4. More important, AC-5 can be instantiated to produce and \(O(ed)\) algorithm for a number of important classes of constraints: functional, anti-functional, monotonic, and their generalization to (functional, anti-functional, and monotonic) piecewise constraints.

We also show that AC-5 has an important application in constraint logic programming over finite domains. The kernel of the constraint solver for such a programming language is an arc-consistency algorithm for a set of basic constraints. We prove that AC-5, in conjunction with node consistency, provides a decision procedure for these constraints running in time \(O(ed)\).

We present a new generic arc-consistency algorithm AC-5. This algorithm is parametrized on two specified procedures and can be instantiated to reduce to AC-3 and AC-4. More important, AC-5 can be instantiated to produce and \(O(ed)\) algorithm for a number of important classes of constraints: functional, anti-functional, monotonic, and their generalization to (functional, anti-functional, and monotonic) piecewise constraints.

We also show that AC-5 has an important application in constraint logic programming over finite domains. The kernel of the constraint solver for such a programming language is an arc-consistency algorithm for a set of basic constraints. We prove that AC-5, in conjunction with node consistency, provides a decision procedure for these constraints running in time \(O(ed)\).

##### MSC:

68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |

##### Keywords:

constraint satisfaction problems; arc-consistency algorithms; constraint logic programming; finite domains##### Software:

CHIP
PDF
BibTeX
XML
Cite

\textit{P. van Hentenryck} et al., Artif. Intell. 57, No. 2--3, 291--321 (1992; Zbl 0763.68059)

Full Text:
DOI

##### References:

[1] | Cormen, T.H.; Leiserson, C.E.; Rivest, R.L., () |

[2] | Dechter, R.; Pearl, J., Network-based heuristics for constraint satisfaction problems, Artif. intell., 34, 1-38, (1988) · Zbl 0643.68156 |

[3] | Deville, Y.; Van Hentenryck, P., An efficient are consistency algorithm for a class of CSP problems, () |

[4] | Dincbas, M.; Simonis, H.; Van Hentenryck, P., Solving large combinatiorial problems in logic programming, J. logic programming, 8, 1-2, 75-93, (1990) · Zbl 0719.68013 |

[5] | Dincbas, M.; Van Hentenryck, P.; Simonis, H.; Aggoun, A.; Graf, T.; Berthier, F., The constraint logic programming language CHIP, () · Zbl 0800.68287 |

[6] | Freuder, E.C., Synthesizing constraint expressions, Commun. ACM, 21, 958-966, (1978) · Zbl 0386.68065 |

[7] | Gaschnig, J., A constraint satisfaction method for inference making, (), 866-874 |

[8] | Haralick, R.M.; Elliot, G.L., Increasing tree search efficiency for constraint satisfaction problems, Artif. intell., 14, 263-313, (1980) |

[9] | Jaffar, J.; Michaylov, S., Methodology and implementation of a CLP system, () |

[10] | Kasif, S., On the parallel complexity of discrete relaxation in constraint satisfaction networks, Artif. intell., 45, 275-286, (1990) · Zbl 0717.68043 |

[11] | Lauriere, J.-L., A language and a program for stating and solving combinatorial problems, Artif. intell., 10, 1, 29-127, (1978) · Zbl 0374.68060 |

[12] | Mackworth, A.K., Consistency in networks of relations, Artif. intell., 8, 1, 99-118, (1977) · Zbl 0341.68061 |

[13] | Mackworth, A.K., () |

[14] | Mackworth, A.K.; Freuder, E.C., The complexity of some polynomial network consistency algorithms for constraint satisfaction problems, Artif. intell., 25, 65-74, (1985) |

[15] | Mohr, R., Good old discrete relaxation, () |

[16] | Mohr, R.; Henderson, T.C., Arc and path consistency revisited, Artif. intell., 28, 225-233, (1986) |

[17] | Mohr, R.; Masini, G., (), 217-231 |

[18] | Montanari, U., Networks of constraints: fundamental properties and applications to picture processing, Inf. sci., 7, 2, 95-132, (1974) · Zbl 0284.68074 |

[19] | Montanari, U.; Rossi, F., An efficient algorithm for the solution of hierarchical networks of constraints, () |

[20] | Nadel, B., Constraint satisfaction algorithms, Comput. intell., 5, 4, 188-224, (1989) |

[21] | Perlin, M., Arc consistency for factorable relations, (), 340-345 |

[22] | Tarjan, R.E., Amortized computational complexity, SIAM J. alg. discrete methods, 6, 306-318, (1985) · Zbl 0599.68046 |

[23] | Van Hentenryck, P., A framework for consistency techniques in logic programming, () |

[24] | Van Hentenryck, P., Logic programming series, () · Zbl 1390.90520 |

[25] | Van Hentenryck, P.; Dincbas, M., Domains in logic programming, () · Zbl 0800.68287 |

[26] | Van Hentenryck, P.; Saraswat, V.; Deville, Y., Constraint processing in CC(FD), (1992), Tech. Rept. Brown University Providence, RI |

[27] | Waltz, D., Generating semantic descriptions from drawings of scenes with shadows, () |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.