...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Constraints >Efficient filtering for the Resource-Cost AllDifferent constraint
【24h】

Efficient filtering for the Resource-Cost AllDifferent constraint

机译：对资源成本AllDifferent约束进行高效过滤

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This paper studies a family of optimization problems where a set of items, each requiring a possibly different amount of resource, must be assigned to different slots for which the price of the resource can vary. The objective is then to assign items such that the overall resource cost is minimized. Such problems arise commonly in domains such as production scheduling in the presence of fluctuating renewable energy costs or variants of the Travelling Salesman Problem. In Constraint Programming, this can be naturally modeled in two ways: (a) with a sum of element constraints; (b) with a MinimumAssignment constraint. Unfortunately the sum of element constraints obtains a weak filtering and the MinimumAssignment constraint does not scale well on large instances. This work proposes a third approach by introducing the ResourceCostAllDifferent constraint and an associated incremental and scalable filtering algorithm, running in , where n is the number of unbound variables and m is the maximum domain size of unbound variables. Its goal is to compute the total cost in a scalable manner by dealing with the fact that all assignments must be different. We first evaluate the efficiency of the new filtering on a real industrial problem and then on the Product Matrix Travelling Salesman Problem, a special case of the Asymmetric Travelling Salesman Problem. The study shows experimentally that our approach generally outperforms the decomposition and the MinimumAssignment ones for the problems we considered.
机译：本文研究了一系列优化问题，其中一组项目（每个项目可能需要不同数量的资源）必须分配给不同的插槽，资源价格可能会有所不同。然后，目标是分配项目，以使总资源成本最小化。此类问题通常在诸如可调度的可再生能源成本波动或旅行推销员问题变型的生产调度等领域出现。在约束编程中，可以自然地以两种方式对其进行建模：（a）具有元素约束的总和； （b）具有MinimumAssignment约束。不幸的是，元素约束的总和获得了弱滤波，而MinimumAssignment约束在大型实例上无法很好地扩展。这项工作提出了第三种方法，方法是引入ResourceCostAllDifferent约束以及相关的增量和可伸缩筛选算法，该算法在中运行，其中n是未绑定变量的数量，m是未绑定变量的最大域大小。它的目标是通过处理所有分配必须不同的事实，以可扩展的方式计算总成本。我们首先评估针对实际工业问题的新过滤的效率，然后评估产品矩阵旅行商问题，这是非对称旅行商问题的特例。研究表明，对于所考虑的问题，我们的方法通常优于分解法和最小分配法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号