Contractibility for open global constraints

DOI10.1017/S1471068417000126MaRDI QIDQ4593091zbMATH OpenOpenAlexFDO

Publication date 9 November 2017

Published in Theory and Practice of Logic Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.07889

global constraints soft constraints open constraints

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

Abstract: Open forms of global constraints allow the addition of new variables to an argument during the execution of a constraint program. Such forms are needed for difficult constraint programming problems where problem construction and problem solving are interleaved, and fit naturally within constraint logic programming. However, in general, filtering that is sound for a global constraint can be unsound when the constraint is open. This paper provides a simple characterization, called contractibility, of the constraints where filtering remains sound when the constraint is open. With this characterization we can easily determine whether a constraint has this property or not. In the latter case, we can use it to derive a contractible approximation to the constraint. We demonstrate this work on both hard and soft constraints. In the process, we formulate two general classes of soft constraints.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Contractibility for open global constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4593091)