WSP: Workflow Satisfiability Problem Instances with Class-Independent Constraints

An experimental dataset for the Workflow Satisfiability Problem (WSP) with class-independent constraints, generated by a random instance generator described in a 2015 paper. The dataset includes instances stored in .wsp files and corresponding pseudo-Boolean satisfiability formulations in .opb files, alongside solution outputs from the SAT4J solver and a pattern-backtracking FPT algorithm. The dataset was created by Andrei Gagarin and colleagues for algorithm benchmarking.

Use Cases

• Benchmarking algorithm performance based on instance parameters like number of steps, users, and constraints.
• Testing pseudo-Boolean satisfiability solvers on converted WSP constraint formulations.
• Evaluating the efficiency of Fixed Parameter Tractability (FPT) algorithms for workflow authorization.
• Studying the impact of class-independent equivalence and non-equivalence constraints on problem satisfiability.
• Comparing solution assignments generated by different algorithmic approaches for the same problem instances.

Strengths

• Instances are generated to avoid trivially unsatisfiable cases, providing meaningful test cases.
• Multiple file formats (.wsp, .opb, .txt) provide raw problem data, solver inputs, and algorithm outputs for comprehensive analysis.
• The pattern-backtracking FPT algorithm implementation includes solution correctness checks and memory/time control features.
• Instance naming convention explicitly encodes key parameters (#S, #U, #C, constraint counts a,b,c,d) for easy filtering.

Limitations

• Row count and dataset size are unknown, which may limit suitability assessment for large-scale training.
• Column-level documentation is absent; field semantics must be inferred from file naming conventions and descriptions.
• Last update date is unknown; freshness unverified.

Provenance

Source

Andrei Gagarin and collaborators, associated with research papers from 2015.

Collection Method

Generated by a random instance generator developed from a prior generator described in a 2015 journal article.