Martin Cooper

Title: Martin Cooper

Main Research Question: Can a notion of soft arc consistency be extended to non-idempotent cost combination operators, such as Max-CSP, which allows for a more general and practical problem formulation?

Methodology: The researchers proposed a small additional axiom that is satisfied by most existing soft constraints proposals. This axiom allows for the extension of soft arc consistency to non-idempotent cost combination operators. They introduced a directional version of arc consistency, which has the potential to propagate penalties non-locally, and demonstrated its utility by showing that it implies a form of local optimality called arc irreducibility.

Results: The researchers showed that using the additional axiom, it is possible to define a notion of soft arc consistency that extends the classical notion of arc consistency and works with non-idempotent cost combination operators. They also demonstrated that the enforcement of this soft arc consistency is polynomial in time and has the same space and time complexities as enforcing arc consistency in CSPs when the cost combination operator is strictly monotonic.

Implications: The extension of soft arc consistency to non-idempotent cost combination operators has significant implications for the field of combinatorial optimisation. It allows for a more general and practical problem formulation, such as Max-CSP, which was previously infeasible with existing methods. The directional version of arc consistency and the concept of arc irreducibility provide new tools for solving these more complex problems.

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