Engineering algorithms for workflow satisfiability problem with user-independent constraints

Cohen, David, Crampton, Jason, Gagarin, Andrei ORCID: https://orcid.org/0000-0001-9749-9706, Gutin, Gregory and Jones, Mark 2014. Engineering algorithms for workflow satisfiability problem with user-independent constraints. Presented at: FAW 2014: 8th International Workshop on Frontiers in Algorithmics, Zhangjiajie, China, 28-30 June 2014. Published in: Chen, Jainer, Hopcroft, John E. and Wang, Jianxin eds. Frontiers in Algorithmics: 8th International Workshop, FAW 2014, Zhangjiajie, China, June 28-30, 2014. Proceedings. Lecture Notes in Computer Science. Lecture Notes in Computer Science , vol.8497 Springer Verlag, pp. 48-59. 10.1007/978-3-319-08016-1_5

Preview

PDF - Accepted Post-Print Version Download (295kB) | Preview

Abstract

The workflow satisfiability problem (WSP) is a planning problem. Certain sub-classes of this problem have been shown to be fixed-parameter tractable. In this paper we develop an implementation of an algorithm for WSP that has been shown, in our previous paper, to be fixed-parameter for user-independent constraints. In a set of computational experiments, we compare our algorithm to an encoding of the WSP into a pseudo-Boolean SAT problem solved by the well-known solver SAT4J. Our algorithm solves all instances of WSP generated in our experiments, unlike SAT4J, and it solves many instances faster than SAT4J. For lightly constrained instances, SAT4J usually outperforms our algorithm.

Item Type:	Conference or Workshop Item (Paper)
Status:	Published
Schools:	Mathematics
Subjects:	Q Science > QA Mathematics
Publisher:	Springer Verlag
ISBN:	9783319080154
ISSN:	0302-9743
Date of First Compliant Deposit:	1 June 2016
Last Modified:	26 Nov 2024 07:15
URI:	https://orca.cardiff.ac.uk/id/eprint/91298

Citation Data

Cited 13 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item