Iterative Plan Construction for the Workflow Satisfiability Problem
Authors: D. Cohen, J. Crampton, A. Gagarin, G. Gutin, M. Jones
JAIR 2014 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We have implemented our algorithm and compared its performance to SAT4J on another set of synthetic instances of the WSP (Cohen et al., 2014). These instances use k = 16, 20 and 24, n = 10k and user-independent (cardinality) constraints of three different types: we vary the number of constraints and the proportions of the different constraint types; each user is authorized for between 1 and 8 tasks for k = 16, between 1 and 10 tasks for k = 20, and between 1 and 12 tasks for k = 24. The algorithm was implemented in C++ and has been enhanced by the inclusion of techniques employed in CSP solving, such as propagation. We also converted WSP instances into pseudo-Boolean problems for processing by SAT4J. All experiments were performed on a Mac Book Pro computer with a 2.6 GHz Intel Core i5 processor and 8 GB 1600 MHz DDR3 RAM (running Mac OS X 10.9.2). |
| Researcher Affiliation | Academia | David Cohen EMAIL Jason Crampton EMAIL Andrei Gagarin EMAIL Gregory Gutin EMAIL Mark Jones EMAIL Royal Holloway, University of London, UK |
| Pseudocode | Yes | Algorithm 1: Naive solution procedure for the WSP... Algorithm 2: Generic algorithm for the WSP |
| Open Source Code | No | We have implemented our algorithm and compared its performance to SAT4J on another set of synthetic instances of the WSP (Cohen et al., 2014). |
| Open Datasets | No | Wang and Li used synthetic data in their experimental study. We have implemented our algorithm and compared its performance to SAT4J on another set of synthetic instances of the WSP (Cohen et al., 2014). These instances use k = 16, 20 and 24, n = 10k and user-independent (cardinality) constraints of three different types: we vary the number of constraints and the proportions of the different constraint types; each user is authorized for between 1 and 8 tasks for k = 16, between 1 and 10 tasks for k = 20, and between 1 and 12 tasks for k = 24. |
| Dataset Splits | No | These instances use k = 16, 20 and 24, n = 10k and user-independent (cardinality) constraints of three different types: we vary the number of constraints and the proportions of the different constraint types; each user is authorized for between 1 and 8 tasks for k = 16, between 1 and 10 tasks for k = 20, and between 1 and 12 tasks for k = 24. |
| Hardware Specification | Yes | All experiments were performed on a Mac Book Pro computer with a 2.6 GHz Intel Core i5 processor and 8 GB 1600 MHz DDR3 RAM (running Mac OS X 10.9.2). |
| Software Dependencies | No | The algorithm was implemented in C++ and has been enhanced by the inclusion of techniques employed in CSP solving, such as propagation. We also converted WSP instances into pseudo-Boolean problems for processing by SAT4J. |
| Experiment Setup | Yes | These instances use k = 16, 20 and 24, n = 10k and user-independent (cardinality) constraints of three different types: we vary the number of constraints and the proportions of the different constraint types; each user is authorized for between 1 and 8 tasks for k = 16, between 1 and 10 tasks for k = 20, and between 1 and 12 tasks for k = 24. |