Implementation of the Pattern Branch and Bound algorithm for the Valued Workflow Satisfiability Problem

This file contains source codes of the Pattern Branch and Bound algorithm and a pseudo-random instance generator for the valued workflow satisfiability problem with user-independent constraints. This implementation was used in "Jason Crampton, Gregory Z. Gutin, and Daniel Karapetyan. Valued workflow satisfiability problem. In proc. of ACM symposium on Access control models and technologies (SACMAT), 1–3 June, Vienna, Austria. ACM, 2015."

The algorithm and the generator are implemented in C#. The generator is deterministic; to produce distinct instances of the same size and properties, change the seed value. Provided are a Visual Studio 2013 project (including an example of generating an instance and solving it) and compiled x64 .NET executables. In addition, a class to solve the problem with CPLEX is included in the project. The MIP formulation of the problem can be found in the above paper. An installation of CPLEX is only required if this MIP based solver is used.

The implementation of the algorithm and the generator is provided for non-commercial use only. When using this source code, please cite the above paper.