Skip to content

Latest commit

 

History

History
96 lines (65 loc) · 2.83 KB

readme.md

File metadata and controls

96 lines (65 loc) · 2.83 KB
Raw

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:

  1. Using Input Files:

    python workflowSatisfiabilityProblem.py instances/example1.txt

    The above reads a file containing WSP constraints and solves it.

  2. 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

  1. 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

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.