A Maximal Tractable Class of Soft Constraints
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".
@inproceedings{ijcai2003p30,
title = {A Maximal Tractable Class of Soft Constraints},
author = {Cohen, David A. and Cooper, Martin C. and Jeavons, Peter and Krokhin, Andrei A.},
booktitle = {Proceedings of the Eighteenth International Joint Conference on
Artificial Intelligence, {IJCAI-03}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Georg Gottlob},
pages = {209--213},
year = {2003},
url = {https://ijcai.org/proceedings/2003/30},
}
TY - CPAPER TI - A Maximal Tractable Class of Soft Constraints AU - Cohen, David A. AU - Cooper, Martin C. AU - Jeavons, Peter AU - Krokhin, Andrei A. T2 - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03 PB - International Joint Conferences on Artificial Intelligence PY - 2003 SP - 209 EP - 213 UR - https://ijcai.org/proceedings/2003/30 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
