约束规划与全局约束

当决策天然是离散的、业务规则更适合表达为关系而不是大量线性行时，约束规划（Constraint Programming，CP）很有用。CP 模型声明有限域、全局约束和目标函数；求解器结合传播、搜索和目标界来寻找或证明排程、分配、装箱或路径方案。

本页是数学教程，说明 OSPF 模型需要保持的语义；它不是 Kotlin 或 Rust API 调用清单。

1. 何时适合使用有限域 CP

当决策具有较小或明确有界的离散备选集合时，可以考虑有限域 CP：

• 以整数分钟或班次表示的开始时间；
• 从有限集合中选择工人、房间、车辆或机器；
• 工序顺序、排列位置、颜色或排名；
• 带有存在性决策的可选活动。

当许多决策通过全局规则相互作用时，CP 尤其具有表现力。一个 AllDifferent 约束可以描述排列，NoOverlap 可以描述互斥机器，Cumulative 可以描述可再生资源的负载曲线。全局形式直接表达业务规则，也可能让 CP 求解器得到比临时拼接的线性编码更强的传播。

有限并不意味着必须逐个列出所有值。$\{0,1,\dots ,480\}$ 仍然是有限且紧凑的域。重要的是：下界、上界、整数性以及域中的空洞，都属于模型声明的语义。

2. 核心定义

2.1 有限域变量

有限域变量 $x$ 有一个声明的取值集合 $D_x$。例如：

$$x\in D_x=\{0,1,2,3,4\}.$$

像 $x\in \{0,1,\dots ,6\}$ 这样的区间表示整数值，而不是 $[0,6]$ 中的所有实数。布尔变量是 $\{0,1\}$ 的特殊情形。求解器在搜索过程中可能暂时缩小域，但搜索状态的缩小不等于修改业务模型。

2.2 AllDifferent

对于变量 $x_1,\dots ,x_n$，

$$\mathrm{AllDifferent}(x_1,\dots ,x_n)⟺\mathrm{\forall }i<j:x_i\ne x_j.$$

它常用于工人槽位、排列位置或一对一分配。它本身并不表示较大值域中的每个值都被使用，也不表示“每个任务恰好分配到一个资源”，除非变量域和其他约束共同赋予这种含义。

2.3 NoOverlap

对于持续时间为正的活动 $i$，设开始时间为 $s_i$、持续时间为 $p_i>0$，结束时间为

$$e_i=s_i+p_i.$$

通常把活动区间定义为半开区间 $[s_i,e_i)$。对同一互斥资源上的活动，

$$\mathrm{NoOverlap}(I_1,\dots ,I_n)⟺\mathrm{\forall }i<j:e_i\le s_j\vee e_j\le s_i.$$

因此，一个活动恰好在时刻 $t$ 结束，另一个活动可以在 $t$ 开始。如果模型允许零持续时间活动，应单独声明这种空区间是否参与先后关系或资源规则。如果活动是可选的，语义还要包含存在性二值量：两个不存在的活动不产生先后关系，不存在的活动也不占用资源。

2.4 Cumulative

设活动 $i$ 的资源需求为 $r_i\ge 0$，所有活动共享容量 $C$。每个时刻 $t$ 都必须满足：

$$\mathrm{Cumulative}(I_i,r_i,C)⟺\sum _{i:s_i\le t<e_i}{r}_i\le C.$$

对于整数时间，只需检查每个相关时间桶。累计资源允许活动重叠：容量为二时，两个需求为一的活动可以同时执行；若容量为二，一个需求为二的活动就不能与另一个需求为一的活动重叠。

3. 可手算的资源约束排程示例

3.1 业务描述与数据

需要安排四个作业，开始时间为整数时间单位。作业 $A$ 和 $B$ 共用一台机器，因此不能重叠。所有作业都消耗容量为 $3$ 的电力资源。作业 $A$ 必须在作业 $C$ 开始前完成。在这个教学示例中，每个作业还分配一个不同的工人槽位。目标是最小化总工期（makespan）。

作业 $i$	持续时间 $p_i$	电力需求 $r_i$	工人域
$A$	$2$	$2$	$\{1,2,3,4\}$
$B$	$3$	$2$	$\{1,2,3,4\}$
$C$	$2$	$1$	$\{1,2,3,4\}$
$D$	$1$	$1$	$\{1,2,3,4\}$

开始时间域为 $s_i\in \{0,1,\dots ,6\}$，总工期采用安全的有限域 $T\in \{0,1,\dots ,10\}$。工人变量为 $w_i\in \{1,2,3,4\}$。

3.2 变量、中间值与约束

决策变量为：

$$s_i\in \{0,\dots ,6\},w_i\in \{1,2,3,4\},T\in \{0,\dots ,10\}.$$

结束时间中间值定义为：

$$e_A=s_A+2,e_B=s_B+3,e_C=s_C+2,e_D=s_D+1.$$

约束为：

$$\mathrm{AllDifferent}(w_A,w_B,w_C,w_D),$$$$e_A\le s_C,$$$$e_A\le s_B\vee e_B\le s_A,$$$$\sum _{i:s_i\le t<e_i}{r}_i\le 3\text{对每个相关的 }t,$$$$T\ge e_i(i\in \{A,B,C,D\}).$$

最后一组约束是对所有区间结束时间的上包络。在最小化目标下，$T$ 的最优值等于 $\underset{i}{max}{e}_i$；仅有可行性时，$T$ 可能大于这个值。目标函数为：

$$minT.$$

电力约束不是第二个机器顺序约束，而是按时间检查的容量约束：单看电力时，$A$ 和 $C$ 可以重叠，因为 $2+1=3$，但本例单独的前序约束 $e_A\le s_C$ 禁止了这种重叠。$A$ 和 $B$ 既受到 NoOverlap 约束，也不能在容量为 $3$ 时重叠，因为合计需求为 $4>3$。

3.3 一个可逐项检查的候选解

取下列数值：

作业	$s_i$	$e_i$	$w_i$	$r_i$
$A$	$0$	$2$	$1$	$2$
$B$	$2$	$5$	$2$	$2$
$C$	$2$	$4$	$3$	$1$
$D$	$0$	$1$	$4$	$1$

工人值为 $1,2,3,4$，所以 AllDifferent 成立。机器区间为 $A:[0,2)$、$B:[2,5)$，两者只在端点相接而不重叠。并且 $e_A=2=s_C$，所以先后约束也成立。

按时间桶检查资源曲线：

时间桶	活动作业	负载
$[0,1)$	$A,D$	$2+1=3$
$[1,2)$	$A$	$2$
$[2,3)$	$B,C$	$2+1=3$
$[3,4)$	$B,C$	$2+1=3$
$[4,5)$	$B$	$2$

所有负载都不超过 $3$。结束时间表明 $T=5$，且每个作业都在这个时刻之前完成。

3.4 为什么 $T=5$ 已经最优

机器活动存在二选一的先后关系。如果 $B$ 在 $A$ 之前，则 $B$ 需要三个时间单位，$A$ 需要两个时间单位，$C$ 还必须在 $A$ 之后执行两个时间单位。从不早于零开始，得到 $T\ge 3+2+2=7$。

如果 $A$ 在 $B$ 之前，则 $B$ 不能早于 $s_A+2$ 开始，因而不能早于 $s_A+5$ 结束。由于 $s_A\ge 0$，有 $T\ge 5$。上面的候选解实现了 $T=5$，因此它是最优解。这个证明不依赖求解器的搜索轨迹。

4. 全局形式的价值在于传播

求解器可能在分支之前先推导后果。在这个示例中，选择 $A$ 在 $B$ 前面会立即给出 $T$ 的下界 $5$；给一个作业分配工人值会从其他工人的域中删去该值；需求为二的作业不能和另一个需求为二的作业在容量三上同时执行。这些是传播效果，不是额外的业务规则。

应当区分：

• 原始全局约束，例如 NoOverlap；
• 为求解而使用的后端表示；
• 返回给用户的证据，例如占用区间和最大资源负载。

如果全局约束被展开成成对约束或辅助变量，展开后的行属于实现细节。诊断报告仍应指出原始的机器规则或电力规则。

5. 在 OSPF 中的概念性组织

OSPF 模型可以按语义职责组织这个问题：

1. 输入或排程上下文拥有作业持续时间、资源需求、工人可用性以及时间单位。
2. 决策上下文拥有开始时间、结束时间、分配、可选存在性和使决策有意义的有限域。
3. 规则上下文拥有先后关系、机器析取关系、AllDifferent 和累计容量约束，并保留每条原始业务规则的身份。
4. 目标上下文拥有总工期的定义和优化方向。
5. 结果上下文记录解的变量值、目标值、可行性或最优性状态，以及解释所用的界或容差。

编译边界可以在后端支持时把全局约束转换为后端原生表示，也可以在适合时使用精确的等价转换。转换必须保持区间端点、存在性语义、域以及约束身份。编译器架构 介绍语义模型与后端机制的更广泛分离；求解结果 介绍结果应该证明什么、又应该明确保留哪些未知项。这里的列表是概念上的职责划分，不表示每一项当前都有同名公共类。

在临界约束解释中，应报告原始的 NoOverlap、Cumulative 或先后关系，而不是任意的内部行。全局规则可能没有单一的标量 slack。关于活动性、有效性和相对于目标的阻塞解释之间的区别，参见临界约束分析。

6. 常见建模陷阱

6.1 混用闭区间与半开区间

在 $[s,e)$ 约定下，活动在时刻 $t=10$ 结束后不占用时间桶 $10$。如果模型的一部分使用 $s\le t<e$，另一部分却把端点也算作占用，排程可能看起来多占用一个时间单位。应明确写出一次约定并在各处统一使用。

6.2 域太小或误声明为连续

把开始时间域的上界写成 $6$ 会排除实际需要在 $7$ 开始的方案；声明实数区间 $[0,6]$ 则会允许原本不想要的分数开始时间。域界是模型数据，而不只是搜索提示。如果时间以分钟表示，应先把持续时间、截止时间和容差统一转换成分钟再声明域。

6.3 忘记可选活动的存在性语义

可选区间需要一个存在性决策。其结束时间关系、先后关系、机器占用和累计需求都应受存在性条件控制。仅仅把标签写成可空，却让约束仍然无条件生效，可能使不存在的作业继续占用容量。

6.4 把 AllDifferent 误认为分配覆盖

AllDifferent(w_i) 只表示选择的工人值彼此不同。五个作业可以使用十个工人时，它不要求每个工人都接到作业。如果一个工人可以处理多个不重叠作业，那么 AllDifferent 可能过强，应改用每个工人的资源或 NoOverlap 语义。

6.5 把累计容量当成成对不重叠

成对不重叠在某些情况下比容量曲线更强，在另一些情况下又可能漏掉容量限制。容量三允许三个需求为一的作业同时执行，但成对规则会错误地禁止它们。反过来，需求二的作业和需求一的作业可以在容量三上重叠，即使两道机器工序因为另一个业务原因仍必须使用 NoOverlap。

6.6 用目标函数补齐缺失的约束

最小化 $T$ 会使最优解中的总工期趋紧，但不会使遗漏的先后关系或资源规则自动成立。必须精确的派生量应有定义关系，或有可证明的目标作用。不能依赖一个“通常有利”的目标函数来实现业务不变量。

6.7 假设每条全局约束都有有用的 slack

某条内部线性化行的数值残差不是 AllDifferent 或 NoOverlap 的通用 slack。应使用成对冲突、最大资源负载或域违规等语义证据，并把当前解的活动性与目标影响分开标记。

7. 相关页面

• 临界约束分析
• 不等式指示函数
• Slack
• If-Then
• 求解结果
• 编译器架构
• 运筹学语言
• 建模工作流
• 符号表达式
• 滚动优化
• 不可行性分析
• 场景分析