@inproceedings{72431cc55f8c4044b421dd3213fcbe3d,
title = "A soft global precedence constraint",
abstract = "Hard and soft precedence constraints play a key role in many application domains. In telecommunications, one application is the configuration of call-control feature subscriptions where the task is to sequence a set of user-selected features subject to a set of hard (catalogue) precedence constraints and a set of soft (user-selected) precedence constraints. When no such consistent sequence exists, the task is to find an optimal relaxation by discarding some features or user precedences. For this purpose, we present the global constraint SOFTPREC. Enforcing Generalized Arc Consistency (GAC) on SOFTPREC is NP-complete. Therefore, we approximate GAC based on domain pruning rules that follow from the semantics of SOFTPREC; this pruning is polynomial. Empirical results demonstrate that the search effort required by SOFTPREC is up to one order of magnitude less than the previously known best CP approach for the feature subscription problem. SOFTPREC is also applicable to other problem domains including minimum cutset problems for which initial experiments confirm the interest.",
author = "David Lesaint and Deepak Mehta and Barry O'Sullivan and Luis Quesada and Nic Wilson",
year = "2009",
language = "English",
isbn = "9781577354260",
series = "IJCAI International Joint Conference on Artificial Intelligence",
publisher = "International Joint Conferences on Artificial Intelligence",
pages = "566--571",
booktitle = "IJCAI-09 - Proceedings of the 21st International Joint Conference on Artificial Intelligence",
address = "United States",
note = "21st International Joint Conference on Artificial Intelligence, IJCAI 2009 ; Conference date: 11-07-2009 Through 16-07-2009",
}