提出基于地标上界的新方法，高效实现带成本的全局基数约束。
Efficient Implementation of the Global Cardinality Constraint with Costs
- 用地标法预计算最短路径上界，减少实时计算量。
- 实践中显著降低最短路径的显式求解次数。
- 适合需高效处理带成本约束的规划问题研究者。
约束编程的成功部分依赖于全局约束及其过滤算法的实现。近期，针对全不同约束的实现有了新进展。本文研究带成本的基数约束：该约束是全不同约束的推广，规定给定变量集合在解中每个值出现的次数；引入分配成本并限制总成本上限。其弧一致性过滤算法在实践中难用，因需系统搜索大量最短路径。本文提出一种新方法，基于地标预计算最短路径上界，作为预处理步骤。该方法快速，可有效避免大量显式最短路径计算，在实践中表现优越。
原文摘要 · Abstract (English)
The success of Constraint Programming relies partly on the global constraints and implementation of the associated filtering algorithms. Recently, new ideas emerged to improve these implementations in practice, especially regarding the all different constraint. In this paper, we consider the cardinality constraint with costs. The cardinality constraint is a generalization of the all different constraint that specifies the number of times each value must be taken by a given set of variables in a solution. The version with costs introduces an assignment cost and bounds the total sum of assignment costs. The arc consistency filtering algorithm of this constraint is difficult to use in practice, as it systematically searches for many shortest paths. We propose a new approach that works with upper bounds on shortest paths based on landmarks. This approach can be seen as a preprocessing. It is fast and avoids, in practice, a large number of explicit computations of shortest paths.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。