...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Constraints >A Cost-Regular Based Hybrid Column Generation Approach
【24h】

A Cost-Regular Based Hybrid Column Generation Approach

机译：基于成本规则的混合列生成方法

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

摘要

Constraint Programming (CP) offers a rich modeling language of constraints embedding efficient algorithms to handle complex and heterogeneous combinatorial problems. To solve hard combinatorial optimization problems using CP alone or hybrid CP-ILP decomposition methods, costs also have to be taken into account within the propagation process. Optimization constraints, with their cost-based filtering algorithms, aim to apply inference based on optimality rather than feasibility. This paper introduces a new optimization constraint, cost-regular. Its filtering algorithm is based on the computation of shortest and longest paths in a layered directed graph. The support information is also used to guide the search for solutions. We believe this constraint to be particularly useful in modeling and solving Column Generation subproblems and evaluate its behaviour on complex Employee Timetabling Problems through a flexible CP-based column generation approach. Computational results on generated benchmark sets and on a complex real-world instance are given.
机译：约束编程（CP）提供了丰富的约束建模语言，可以嵌入有效的算法来处理复杂的异构组合问题。为了使用单独的CP或混合CP-ILP分解方法解决硬组合优化问题，在传播过程中还必须考虑成本。优化约束及其基于成本的过滤算法，旨在基于最优性而非可行性来应用推理。本文介绍了一种新的优化约束，即常规成本。它的过滤算法基于分层有向图中最短和最长路径的计算。支持信息还用于指导寻找解决方案。我们认为此约束对于建模和解决“列生成”子问题以及通过基于CP的灵活列生成方法评估其在复杂的员工时间表问题上的行为特别有用。给出了在生成的基准集和复杂的实际实例上的计算结果。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号