Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Pattern-Based Approach to the Workflow Satisfiability Problem with User-Independent Constraints
Authors: Daniel Karapetyan, Andrew J. Parkes, Gregory Gutin, Andrei Gagarin
JAIR 2019 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In our computational study, the phase transition (PT) properties of the WSP are investigated for the first time, under a model for generation of random instances. We show how PT studies can be extended, in a novel fashion, to support empirical evaluation of scaling of FPT algorithms. ... Experimental studies of the algorithm performances, focusing on average case complexity, and supported by a new methodology that carefully exploits work in AI on phase transition (PT) phenomena |
| Researcher Affiliation | Academia | Daniel Karapetyan EMAIL Institute for Analytics and Data Science, University of Essex, Colchester CO4 3SQ, UK; Andrew J. Parkes EMAIL School of Computer Science, University of Nottingham, Nottingham NG8 1BB, UK; Gregory Gutin EMAIL Department of Computer Science, Royal Holloway, University of London, Egham TW20 0EX, UK; Andrei Gagarin EMAIL School of Mathematics, Cardiff University, Cardiff CF10 3AT, UK |
| Pseudocode | Yes | Algorithm 1: Backtracking search initialisation (entry procedure of PBT) Algorithm 2: Recursion(P, G, M) (recursive function for backtracking search) |
| Open Source Code | Yes | The source codes of the instance generator and PBT, as well as the test instances, solutions, translation routines and the experimental data, are publicly available from Karapetyan (2019). |
| Open Datasets | Yes | The PBT algorithm, conversion routines, test instances with solutions and the test instance generator are available for downloading from Karapetyan (2019). |
| Dataset Splits | No | The paper describes how instances are generated for evaluation ('For each value of k we generated 100 instances using WIG(k, 10k, e50, k).'), but it does not specify explicit training/validation/test splits from a larger, fixed dataset in the typical machine learning sense. |
| Hardware Specification | Yes | Our test machine is based on two Intel Xeon CPU E5-2630 v2 (2.6 GHz) and has 32 GB RAM installed. |
| Software Dependencies | No | The paper mentions using "SAT4J" and "OR-Tools1 (CP-SAT)" as solvers and that the PBT algorithm is implemented in "C#" and PUI in "C++". While the reference for SAT4J (Le Berre & Parrain, 2010) mentions "release 2.2", this specific version number is not explicitly stated in the main text when discussing its use. No version numbers are provided for OR-Tools, C#, or C++ within the body of the paper for reproducibility. |
| Experiment Setup | Yes | The values of parameters α =, α =, , α , , α0 , α1 and α2 were selected empirically using a bespoke automated parameter tuning method. We found out that the algorithm is not very sensitive to the values of these parameters, and we settled at α = = 3, α =, = 4, α , = 2, α0 = 40, α1 = 4 and α2 = 0. |