ITPub博客

《ERP高级计划》书的解读- APS算法分析之四约束规划CP(蔡颖)(转)

原创 Linux操作系统 作者:urinator 时间:2007-08-04 00:00:00 0 删除 编辑

《ERP高级计划》书的解读- APS算法分析之四约束规划CP(蔡颖)

http://www.amteam.org/static/51/51380.html

http://www.amteam.org/k/Board/2004-11/485000.html


约束规划Constrained Programming (CP)

算法过程的每一步, CP 检查硬约束,创建第一个可行方案Z 和下一个带着增加约束的方案 Z‘ :

Z‘
的质量> Z
的质量

事先请求: 变量有一上界 (是从上面限制。如 X > 0 作为X的唯一约束 是不可能的)

 

CP 使用约束来规则出不可行方案和消减大量的搜索空间。约束被开发出来减少其它约束和 来发现不连续的可行方案。这个用约束的建设性的方法就是有名的约束传播。

案例:: 两个顺序的工序 A B ,持续时间DA DB. 资源是从 1小时到10小时. 于是我们由一时间间隔 [1,10]. 问题是决定开始时间 SA SB, 工序A 必须在B开始之前完成,如. SB=SA+DA. 假设 DA 5. 那么, 在约束程序里,任何分配给变量SA (SA=3)会引起一个分配给 SB (. SB=8). 同样约束也可以在其它方向工作:任何分配给 SB (. SB=10) 会导致分配给SA (. SA=5): 这就会导致一个搜索空间的减少: SB = [6,10], SA = [1,5].

硬约束, 如资源能力, 最小化和最大化时间约束.相反: 软约束是和目标函数连在一起,如延迟和没有交货的成本。

 

一个变量有一个限制可能值的域:

:

X 可以等于所有整数值 [0, 5]的间隔

X 可以等于这些整数值的之一: {1, 2, 5, 7}

X 可以等于这些符号值的之一: {a, b, c}

X 可以等于所有整数值在[0.5, 5.7]里。

X 可以等于这些值之一 {TRUE, FALSE}

X 可以等于这些符号集之一 : {{a}, {b}, {c}, {a,b}, {b,c}, {a,c}, {a,b,c}}

一个值的域是和每一约束变量联系的

域减少 (1)

:

2 约束整数变量 X YX 有域 [5 ... 20], Y 有域[0 ... 10]

图示:

所以 新的X 和 Y域 :X 在 [5, 10], Y 在 [5, 10]

约束传播的主要原则:

每一次,一个变量被修改, 这次约束传播影响到其它变量 。其特性

-这个算法总是中断的

-在被考虑的约束里,不考虑顺序, 这个域总是用同样的方法减少

所有变量都被界定了,所有约束都满意了,一个方案就被找到。

CP就是一个搜索的方案,基于约束问题主要有以下组成:
-具有给定值的域的几种变量
-在这些变量的几种约束

基本上, 我们要找到方案, 就是要给一值,对所有变量来满足所有约束或找到最佳方案,给一值对所有变量来满足所有约束,及来优化一给定的准则。

约束传播的优点:
约束解决问题的理论复杂性,约束程序的理论复杂性是指数的。给定V 具有N大小的域的变量, 有 N^V 可能分配给变量的值

CP的优点:
1.搜寻树在传播的每一步是减少。
2.传播可以尽早触发一个失败
3.在减少变量域之前, 传播使得启发更好的运作

CP-总结
1.一个约束程序专注有限域约束变量和约束.
2.当已标出后,约束触发初始域减少.
3.当变量得到修正, 改变其它变量的影响是被约束传播的。
4.专注于复杂排程问题
5.CP应该用于非常复杂约束限制排程问题如很难找到任何可行的方案。
6.基于
约束传播
分枝和定界

注意: CP 是启发搜索方法,它不能保证是找到的是最优化的方案

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/7942439/viewspace-20264/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2007-12-06

  • 博文量
    3875
  • 访问量
    1799677