Workflow Satisfiability Problem (WSP)

Note: this is code I did in 2021 December/2022 January so it may be quite sloppy to my current day stndards

This repository contains a Python implementation of a solver for the Workflow Satisfiability Problem (WSP). The solution leverages Google OR-Tools and Constraint Programming (CP) to handle various constraints efficiently.

Features

Flexible Constraint Support: Includes constraints such as:
- Authorisation
- Binding-of-Duty
- Separation-of-Duty
- At-most-k Constraints
- One-team Constraints
Efficient Solver: Built with Google OR-Tools for performance and scalability.
Custom Constraint Generation: Automatically generates constraints for testing.
Multiple Solution Modes: Supports enumeration of all feasible solutions or finding a single optimal solution.

Installation

Ensure you have Python installed and run the following command to install the required dependency:

python -m pip install --upgrade --user ortools
python -m pip install --upgrade --user numpy

Usage

Command-Line Execution

Run the solver by specifying the input file or constraints directly:

Using Input Files:
```
python workflowSatisfiabilityProblem.py instances/example1.txt
```
The above reads a file containing WSP constraints and solves it.
Generate Custom Constraints:
```
python workflowSatisfiabilityProblem.py <print_type> <multiple_solutions> <num_auth> <num_bind> <num_sep> <num_atmostk> <num_oneteam> <users> <steps>
```
Parameters:
- <print_type>: Output style (1 for standard, 2 for detailed).
- <multiple_solutions>: Solve for all solutions (1) or a single solution (0).
- <num_auth>: Number of Authorisation constraints.
- <num_bind>: Number of Binding-of-Duty constraints.
- <num_sep>: Number of Separation-of-Duty constraints.
- <num_atmostk>: Number of At-most-k constraints.
- <num_oneteam>: Number of One-team constraints.
- <users>: Number of users.
- <steps>: Number of steps.

Examples

Solve with a File:

python workflowSatisfiabilityProblem.py instances/example1.txt

Developer Notes

Key Files

workflowSatisfiabilityProblem.py: Main script for solving the WSP.
problem-tester.py: Test the solution against all problems

Core Dependencies

Google OR-Tools: Used for Constraint Programming.

Performance Metrics

The solver reports:

Conflicts: Number of constraint conflicts encountered.
Branches: Number of branches explored.
Wall Time: Total time taken to solve.
Solution Statistics: Number of solutions found.

License

This project is licensed under the All Rights Reserved. See the LICENSE file for details.

License

salmanmkc/Workflow-Satisfiability-Problem

ErrorLooks like something went wrong!

About

Resources

License

Uh oh!

Stars

Watchers

Forks

Releases

Packages 0

Uh oh!

Languages

Error
Looks like something went wrong!

Packages