---
title: "A Maximal Tractable Class of Soft Constraints"
authors:
  - "David A. Cohen"
  - "Martin C. Cooper"
  - "Peter Jeavons"
  - "Andrei A. Krokhin"
doi: ""
url: "https://ijcai.org/proceedings/2003/30"
pdf: "https://ijcai.org/proceedings/2003/0030.pdf"
venue: "Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence"
year: 2003
pages: "209-213"
track: ""
keywords:
---

# A Maximal Tractable Class of Soft Constraints

David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin

*Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence*, pages 209-213.

## Abstract

Many optimization problems can be expressed using some form of soft constraints, where different measures of desirability are associated with different combinations of domain values for specified subsets of variables. In this paper we identify a class of soft binary constraints for which the problem of finding the optimal solution is tractable. In other words, we show that for any given set of such constraints, there exists a polynomial time algorithm to determine the assignment having the best overall combined measure of desirability. This tractable class includes many commonly-occurring soft constraints, such as "as near as possible" or "as soon as possible after", as well as crisp constraints such as "greater than".