...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>RAIRO Operation Research >INEQUALITY-SUM: A GLOBAL CONSTRAINT CAPTURING THE OBJECTIVE FUNCTION
【24h】

INEQUALITY-SUM: A GLOBAL CONSTRAINT CAPTURING THE OBJECTIVE FUNCTION

机译：不平等和：获得目标函数的全局约束

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

摘要

This paper introduces a new method to prune the domains of the variables in constrained optimization problems where the objective function is defined by a sum y = ∑x_i, and where the integer variables x_i are subject to difference constraints of the form x_j - x_i ≤ c. An important application area where such problems occur is deterministic scheduling with the mean flow time as optimality criteria. This new constraint is also more general than a sum constraint defined on a set of ordered variables. Classical approaches perform a local consistency filtering after each reduction of the bound of y. The drawback of these approaches comes from the fact that the constraints are handled independently. We introduce here a global constraint that enables to tackle simultaneously the whole constraint system, and thus, yields a more effective pruning of the domains of the x_i when the bounds of y are reduced. An efficient algorithm, derived from Dijkstra's shortest path algorithm, is introduced to achieve interval consistency on this global constraint.
机译：本文介绍了一种新方法来修剪约束优化问题中的变量域，其中目标函数由和y = ∑x_i定义，并且整数变量x_i受到x_j-x_i≤c形式的差分约束。发生此类问题的重要应用领域是确定性调度，以平均流动时间作为最优标准。此新约束也比在一组有序变量上定义的和约束更通用。 y的每次减小后，经典方法都会执行局部一致性过滤。这些方法的缺点来自约束是独立处理的事实。我们在这里介绍一个全局约束，该约束可以同时处理整个约束系统，因此，当y的边界减小时，可以对x_i的域进行更有效的修剪。引入了一种有效的算法，该算法是从Dijkstra的最短路径算法派生而来的，以在此全局约束下实现区间一致性。

著录项

  • 来源
    《RAIRO Operation Research》 |2005年第2期|p.123-139|共17页
  • 作者

    JEAN-CHARLES REGIN; MICHEL RUEHER;

  • 作者单位

    ILOG Les Taissounieres HB2 1681, route des Dolines Sophia-Antipolis, 06560 Valbonne, France;

  • 收录信息 美国《科学引文索引》(SCI);美国《工程索引》(EI);
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 运筹学;
  • 关键词

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号