资源独立工作流可满足性的最小增量模式回溯  

Minimum Incremental Pattern Backtracking for Resource-independent Workflow Satisfiability Problem

作　　者：翟治年[1] 卢亚辉[2] 刘关俊[3] 雷景生 向坚[1] 吴茗蔚[1] ZHAI Zhi-Nian;LU Ya-Hui;LIU Guan-Jun;LEI Jing-Sheng;XIANG Jian;WU Ming-Wei(School of Information and Electronic Engineering,Zhejiang University of Science and Technology,Hangzhou 310023,China;College of Computer Science and Software Engineering,Shenzhen University,Shenzhen 518060,China;Department of Computer Science and Technology,Tongji University,Shanghai 201804,China)

机构地区：[1]浙江科技学院信息与电子工程学院,浙江杭州310023 [2]深圳大学计算机与软件学院,广东深圳518060 [3]同济大学计算机科学系,上海201804

出　　处：《软件学报》2023年第4期1543-1569,共27页Journal of Software

基　　金：国家自然科学基金(62172299,61972357);浙江省教育厅一般科研项目(Y201737476)。

摘　　要：工作流可满足性是业务安全规划的基本问题,正在面临高资源配比(资源数n显著大于步骤数k)造成的性能挑战.在资源独立约束下,其最高效求解途径是模式空间上的增量回溯法IPB.为克服结点真实性验证的性能瓶颈,它增量计算模式k指派(二部)图及其(左完备)匹配,分别需要O(kn)和O(k^(2))时间.利用父子模式的原子差异增量计算完全指派图,只需O(n)时间,特别是其实际性能,将随模式块规模增长迅速提高.但该图的O(kn)规模导致了同样的增量匹配时间.进而引入完备k核心匹配概念,证明其存在性等价于左完备匹配,且其增量计算时间为O(k^(2)).由此,建立了时间复杂度更低的最小增量模式回溯法.在含互斥和两种全局值势约束而授权比例约为1/4的扩展公开实例集上进行实验,结果表明:当n/k=10(及n/k=100),而k变化时,该方法较IPB有平均超过2(及5)倍、最低1.5(及2.9)倍的性能优势;当k=18(及k=36),而n/k=2~4096(及n/k=2~2048)时,该方法有平均超过2.6(及3.6)倍优势;而较2021年Minizinc挑战赛的冠军求解器Google OR-Tools CP-SAT,该方法最低有超过3倍优势.Workflow satisfiability problem is an elemental issue in the security planning of business process,and it is facing the performance challenge caused by high resource ratio(the number n of resources is significantly greater than the number k of steps).Under resource-independent constraints,its most efficient approach is incremental pattern backtracking(IPB)in the pattern space.To overcome the performance bottleneck of verifying whether a node is authentic,IPB computes the k-assignment(bipartite)graph of a pattern and its(left complete)matching in an incremental manner,which requires O(kn)and O(k^(2))time respectively.This study computes a full-assignment graph incrementally with only O(n)time by exploiting the atomic difference between a sub-pattern and its super one,and in particular its actual performance will increase rapidly with the size of a block in pattern.However,the size O(kn)of such a graph will result in the same incremental matching time.Further,this study introduces the concept of complete k core matching and shows that its existence is equivalent to a left complete matching and its incremental computation only costs O(k^(2))time.Therefore,this study proposes an algorithm of minimum incremental pattern backtracking(MIPB)that is superior to IPB in time complexity.Experiments are conducted on an extended public instance set with constraints of two global value-cardinality types and of the mutual exclusion,and with an authorization ratio of about 1/4.The results show that:when k varies at n/k=10(n/k=100,respectively),MIPB achieves averagely more than 2(5,respectively)times and at least 1.5(2.9,respectively)times advantage of performance compared to IPB;when k=18(k=36,respectively),and n/k belongs to 2~4096(2~2048,respectively),MIPB achieves averagely more than 2.6(3.6,respectively)times advantage.While compared to the champion solver OR-Tools CP-SAT in the 2018~2021 Minizinc Challenges,MIPB achieves at least more than 3 times advantage.

关 键 词：工作流 授权 约束 资源独立 资源分配 可满足 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]