通过推导新约束提升调度求解效率，避免搜索时反复试探。
On inferring cumulative constraints
- 将任务占用向量建模为线性不等式，发现不可并行的任务集
- 对发现的约束集进行强化，生成更紧的可行不等式
- 在标准测试集上显著提升求解性能，8个新下界来自推导约束
累积约束是约束规划中调度的核心，但传统方法按约束逐个传播，忽略多资源交互，导致部分基准测试严重变慢。本文提出一种预处理方法，通过分析任务占用向量的线性不等式，推导出额外的累积约束以捕捉资源间交互关系，无需搜索时探查。该方法包括：(i) 发现无法并行执行的任务集合（覆盖集），(ii) 对这些集合的约束进行提升强化，(iii) 将生成的新约束注入原问题实例。在标准 RCPSP 与 RCPSP/max 测试集上的实验表明，这些推导约束能有效提升求解性能并收紧目标边界，在有利实例上表现突出，不利实例上开销极小。此外，共发现 25 个新下界和 5 个新最优解，其中 8 个下界直接源于推导的约束。
原文摘要 · Abstract (English)
Cumulative constraints are central in scheduling with constraint programming, yet propagation is typically performed per constraint, missing multi-resource interactions and causing severe slowdowns on some benchmarks. I present a preprocessing method for inferring additional cumulative constraints that capture such interactions without search-time probing. This approach interprets cumulative constraints as linear inequalities over occupancy vectors and generates valid inequalities by (i) discovering covers, the sets of tasks that cannot run in parallel, (ii) strengthening the cover inequalities for the discovered sets with lifting, and (iii) injecting the resulting constraints back into the scheduling problem instance. Experiments on standard RCPSP and RCPSP/max test suites show that these inferred constraints improve search performance and tighten objective bounds on favorable instances, while incurring little degradation on unfavorable ones. Additionally, these experiments discover 25 new lower bounds and five new best solutions; eight of the lower bounds are obtained directly from the inferred constraints.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。