Branching: The Essence of Constraint Solving

Title: Branching: The Essence of Constraint Solving

Research Question: How can we develop a generic schema for constraint solving that includes a branching process, applicable to most existing constraint domains and systems?

Methodology: The researchers propose a schema for constraint solving that is generic and applicable to both classical and partial constraint satisfaction problems (CSPs). The schema focuses on the branching process, which is a crucial step in complete constraint solving. They provide a formal specification of the schema and state a number of institutional properties that are satisfied by any instances of the schema. The operational procedures of many constraint systems, including cooperative systems, are shown to satisfy these conditions.

Results: The researchers present a formal specification of the schema and declare its main properties. They also provide examples of instances of the schema that solve various CSPs and demonstrate different ways of solving the same CSP using different instantiations of the schema's parameters.

Implications: The proposed schema provides a unified approach to constraint solving, making it applicable to a wide range of constraint domains and systems. This can lead to more efficient and generalized solutions for CSPs, as well as a better understanding of the branching process in constraint solving. The schema can also be extended to partial CSPs, making it even more versatile and useful for various problem-solving scenarios.

Link to Article: https://arxiv.org/abs/0109060v1 Authors: arXiv ID: 0109060v1