Contractibility for open global constraints

DOI10.1017/S1471068417000126zbMATH Open1379.68076arXiv1702.07889OpenAlexW2964046206MaRDI QIDQ4593091FDOQ4593091

Authors: Michael J. Maher 

Publication date: 9 November 2017

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

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.

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

Recommendations

• Open Constraints in a Boundable World
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Contractibility and contractible approximations of soft global constraints
• scientific article; zbMATH DE number 2159467
• Open constraint programming

zbMATH Keywords

global constraintssoft constraintsopen constraints

Mathematics Subject Classification ID

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

Cites Work

• Introduction to algorithms
• Handbook of constraint programming.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Introducing global constraints in CHIP
• Principles and Practice of Constraint Programming – CP 2004
• The Theory of Stabilisation Monoids and Regular Cost Functions
• On conjunctive queries containing inequalities
• On global warming: Flow-based soft global constraints
• Title not available (Why is that?)
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Semiring-based constraint satisfaction and optimization
• Open constraint programming
• Quantitative languages
• Interval propagation to reason about sets: Definition and implementation of a practical language
• Global Grammar Constraints
• Principles and Practice of Constraint Programming – CP 2004
• Constraint solving in uncertain and dynamic environments: A survey
• The Theory of Grammar Constraints
• Decision Problems for Convex Languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• Constraint retraction in CLP(FD): Formal framework and performance results
• Title not available (Why is that?)
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Dynamic global constraints in backtracking based environments
• Local consistency for extended CSPs
• Contractibility and contractible approximations of soft global constraints
• Open Constraints in a Boundable World

Cited In (3)

• Contractibility and contractible approximations of soft global constraints
• Open Constraints in a Boundable World
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems

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)