改进软弧一致性算法，提升线性约束下的求解效率。
Virtual Arc Consistency for Linear Constraints in Cost Function Networks
- 将软弧一致性算法扩展至处理线性约束
- 在多个基准测试中显著提高下界估计精度
- 适合需要高效求解带线性约束的优化问题的研究者
在约束规划中，求解具有硬约束和软约束的离散最小化问题可通过软全局约束、线性规划重构或局部代价函数重构实现。方法（i）虽有丰富约束库，但软约束传播仅通过变量域通信，导致下界较弱；方法（ii）提供全局视角，下界较强，但重构规模可能过大。本文聚焦方法（iii），即局部代价函数建模，其中软弧一致性（SAC）算法可生成中等质量的下界。近期引入线性约束作为局部代价函数提升了建模表达力。本文将现有SAC算法适配以处理线性约束，在多个基准测试上显著改善了下界，部分情况下缩短了求解时间。
原文摘要 · Abstract (English)
In Constraint Programming, solving discrete minimization problems with hard and soft constraints can be done either using (i) soft global constraints, (ii) a reformulation into a linear program, or (iii) a reformulation into local cost functions. Approach (i) benefits from a vast catalog of constraints. Each soft constraint propagator communicates with other soft constraints only through the variable domains, resulting in weak lower bounds. Conversely, the approach (ii) provides a global view with strong bounds, but the size of the reformulation can be problematic. We focus on approach (iii) in which soft arc consistency (SAC) algorithms produce bounds of intermediate quality. Recently, the introduction of linear constraints as local cost functions increases their modeling expressiveness. We adapt an existing SAC algorithm to handle linear constraints. We show that our algorithm significantly improves the lower bounds compared to the original algorithm on several benchmarks, reducing solving time in some cases.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。