基于模式回溯的#WS(≠)快速定界算法

摘要：

#WS(≠)是互斥约束工作流可满足性的量化问题,与第三方环境中有重要意义的资源弹性密切相关.为克服其求解性能瓶颈,本文利用模式回溯法的解空间压缩特性和两层求解机制,提出了一种真实可行解的数量定界方法.它对模式回溯法的结构进行扩展,实现完全可行模式的遍历和统计.对其中每个模式,计算其资源指派二分图上匹配数量的界.再汇总二者,给出#WS(≠)的上、下界.随机生成数据集上的实验表明,在高资源配比和低约束密度条件下,本文算法相对现有算法有比较突出的时间和空间性能,且其给出的上界相当接近于准确值.

关键词：工作流、授权、互斥约束、资源分配、可满足性、模型计数

所属期刊栏目：41

分类号：TP309(计算技术、计算机技术)

资助基金：国家自然科学基金面上项目;浙江省重点研发计划项目;浙江省教育厅科研项目

在线出版日期：2020-12-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：2494-2499