《ERP高级计划》书的解读－ APS算法分析之四约束规划CP（上）（蔡颖）

约束规划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 和 Y。X 有域 [5 ... 20], Y 有域[0 ... 10]

图示：

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

约束传播的主要原则:

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

－这个算法总是中断的

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

(待续)

本文由作者向AMT提供

蔡颖 专栏