临界约束自动分析

求解器回答“怎样得到最好的方案”，临界约束分析进一步回答“为什么不能更好”。它把当前解的边界特征、业务规则的调整收益，以及目标不可达的组合原因分开解释，适用于约束规划（CP）、混合整数线性规划（MILP）及具有精确线性化路径的模型。

本页介绍分析的数学含义、组织方式与报告解读。文中的流程与报告为概念示例，不是特定 Kotlin/Rust API 的调用说明。

1. 三层证据：活动性、有效性与组合阻塞性

阅读前可先了解求解结果中的解、界与状态。原模型本身无解时，先使用不可行性分析与约束放宽；本章重点是可行模型中更优目标受到的限制。

层级	回答的问题	分析方法	结论边界
活动性	哪些约束在当前解处达到或接近边界？	slack、边界距离、语义求值	当前解的特征，不是目标影响证明
有效性	放宽某条约束是否带来收益？	固定整数后的 LP、有限扰动、移除后重求解	区分局部整数配置与完整模型中的影响
组合阻塞性	哪些约束共同阻止指定目标？	目标可行性、冲突核、极小不可满足子集	相对于明确目标与背景条件的组合证据

通常先用便宜的分析安排候选优先级，再对重要候选执行重求解；需要解释目标不可达时，进入组合分析。前两层不是第三层的必要前提，不具备自然 slack 或 LP 对偶的 CP 约束可以直接进入目标可行性分析。

固定基线模型与目标
    → 当前解活动性
    → 局部敏感性 / 单约束扰动
    → 指定更优目标的可行性
    → 冲突核与极小化
    → 原始业务约束分组解释

2. 明确基线与目标方向

设原始模型的可行域为 $X$，目标为 $f(x)$，基线可行解为 $x^0$，其目标值为 $z_0=f(x^0)$。如果最优性已经得到证明，记最优值为 $z^{\ast }=z_0$；否则 $z_0$ 只是 incumbent 的值。

活动性分析只需要可信的可行解，但“不能更优”的解释必须限定到已经证明不可达的具体目标。对于尚未证明最优的 incumbent，更优目标可能可达；即使某个幅度的改善被证明不可达，也不能排除更小幅度的改善。

分析会话保留模型快照、目标身份与方向、基线解、求解状态、界和容差。固定整数、修改 RHS、临时移除约束及添加目标条件都发生在派生模型中，不修改业务模型。缓存也要区分模型指纹、目标、扰动量、背景约束及求解配置，避免跨场景复用结论。

多目标模型需要先明确分析哪个目标，以及其他目标是固定为条件、按字典序保留，还是合成为一个标量目标；不能把不同目标层级的收益直接混在一起。

3. 活动性：在当前解处是否贴边

对于 $a_i^{T}x\le b_i$，定义有符号余量：

$$s_i=b_i-a_i^T{x}^0.$$

对于 $a_i^{T}x\ge b_i$，改用 $s_i=a_i^T{x}^0-b_i$，使可行侧的余量为正。等式则记录残差 $a_i^T{x}^0-b_i$；满足等式不代表它一定影响目标。

给定与单位和数值尺度相适应的容差 ${\epsilon }_i$：

$$\begin{array}{rl}{s}_i<-{\epsilon }_i& \Rightarrow \text{violated},\\ |s_i|\le {\epsilon }_i& \Rightarrow \text{active},\\ s_i>{\epsilon }_i& \Rightarrow \text{positive slack}.\end{array}$$

可在正余量中另设“接近边界”的阈值，并记录阈值及归一化方式。若基线违反约束，应先处理可行性或数值一致性问题，不能把违反当成活动性。

例如 $x+y\le 10$ 在 $(4,6)$ 处的 slack 为 0；$x\le 100$ 在同一点的 slack 为 96。两者只说明这个点的位置，不说明放宽后的最优值变化。

AllDifferent、NoOverlap、Cumulative 等全局约束不一定有唯一自然的 slack。此时保留“满足／违反／无法判断”，或使用明确声明的语义指标，不把内部线性化行的余量伪装成原始全局约束的通用余量。

4. 有效性：放宽后是否真的改善

4.1 固定整数配置下的局部敏感性

对于 MILP，将整数变量固定为当前值：

$$x_I=x_I^0.$$

若剩余问题是 LP，可重求解并取得对偶值 ${\pi }_i$。在相应敏感性范围、目标符号约定与基保持条件下，RHS 的局部变化可以用 ${\pi }_i\mathrm{\Delta }{b}_i$ 解释。

这描述的是“整数配置不变时”的连续调整，不是 MILP 的全局影子价格。对偶值为零不排除其他整数结构在较大扰动后带来改善；退化时，对偶解也可能不唯一。

如果通过精确 MIP 转换得到 LP，需要交代固定了哪些整数变量，包括转换引入的离散选择。内部行的对偶值必须通过原始参数的依赖关系解释，不能随意相加为一条 CP 全局约束的影子价格。没有合适 LP 表示时，跳过这一层。

4.2 有限扰动与完整模型重求解

对上界约束的放宽是 $b_i\mapsto b_i+\delta$；对下界约束则是 $b_i\mapsto b_i-\delta$，其中 $\delta \ge 0$。等式或全局约束需要单独定义具有业务含义的修改，如容量增加、时间窗延长，不能统一理解为“RHS 加一个数”。

令扰动后最优值为 $z_i(\delta )$，统一把正数定义为收益：

$$G_i(\delta )=\{\begin{array}{ll}{z}_i(\delta )-z^{\ast },& \text{maximize},\\ z^{\ast }-z_i(\delta ),& \text{minimize}.\end{array}$$

整数变量在重求解中可以重新选择，因此该结果不局限于原来的整数配置。$G_i(\delta )/\delta$ 是该幅度上的平均收益，不是全局导数。

只有在基线与扰动最优值均已证明时，才能把数值差称为最优值变化。若只找到扰动后的可行解，可以报告已观察到的收益和求解界，但没有观察到收益不能证明无效。若基线本身未证明最优，新解比旧 incumbent 好，也不一定是放宽约束造成的。

4.3 自适应扰动与移除

可依次尝试 ${\delta }_0,2{\delta }_0,4{\delta }_0,\dots$，直到发现收益或到达业务允许的范围和分析预算。对嵌套扩大的可行域、可靠的求解结论和明确的收益容差，可进一步缩小有效阈值的区间：

$${\delta }_i^{\ast }=inf\{\delta \ge 0:G_i(\delta )>{\epsilon }_z\}.$$

离散参数按可取值搜索；连续参数只能报告所用精度下的区间。超时的重求解不能作为“该侧无收益”的二分依据，收益随扰动的变化也不必光滑。

完全移除某条约束是更强的对照，但不一定是允许执行的业务动作。移除后无收益只能说明单独移除不足以改善；移除后无界应单独报告，不能记成普通有限收益。

4.4 例子：不活动也可能阻止改善

考虑整数产量 $q$：

$$\begin{array}{rl}max& q\\ \text{s.t.}& q\in {\mathbb{Z}}_{\ge 0},\\ c_1:& q\le 10,\\ c_2:& 2q\le 21.\end{array}$$

最优值是 10。$c_1$ 活动，$c_2$ 的 slack 为 1，因此不活动。但仅删除 $c_1$，整数产量仍不能超过 10；仅删除 $c_2$ 也一样。将两条上界分别放宽到 $q\le 11$ 和 $2q\le 22$ 后，才可以生产 11。

所以“不活动”“单独移除没有收益”都不能推出“不参与瓶颈”。活动性与局部对偶可以用来排序，但不应永久排除非活动约束。

5. 把目标突破转成可行性问题

不对多变量解随意做 $x^0+ϵ$，而是指定业务所需的目标改善量 $\mathrm{\Delta }>0$：

$${\tau }_{\mathrm{\Delta }}(x)=\{\begin{array}{ll}f(x)\ge z_0+\mathrm{\Delta },& \text{maximize},\\ f(x)\le z_0-\mathrm{\Delta },& \text{minimize}.\end{array}$$

随后求解满足性问题 $x\in X\wedge {\tau }_{\mathrm{\Delta }}(x)$。例如“至少多运输 100 千克”比含义不明确的“提高一点”更容易解释。相对改善量可用 $r|z_0|$ 定义，但基线为零时必须另选绝对尺度；整数目标还要考虑其实际可取步长和容差。

结果	可以得出的结论
可达（SAT）	有满足目标的可行方案，可返回该方案
不可达（UNSAT / Infeasible）	在指定模型与背景条件下，该目标被证明不可行
未知（Unknown）	时间或资源不足等原因导致尚无结论
不支持（Unsupported）	所选路径不能表达或处理所需语义

没有找到解不等于不可达。基线模型若本来就不可行，应先做不可行性诊断，而不是解释最优性。

6. 从冲突核得到极小阻塞集合

把始终保留的变量类型、不可放宽规则等记为背景 $B$，可诊断约束集合记为 $C$，目标条件记为 $\tau$。对不可达目标，从 $B\wedge C\wedge \tau$ 中提取冲突，再缩减得到 $M\subseteq C$。

目标相对的极小阻塞集合满足：

$$B\wedge \underset{c\in M}{\bigwedge }c\wedge \tau \text{is UNSAT},$$$$\mathrm{\forall }c\in M:B\wedge \underset{d\in M\setminus \{c\}}{\bigwedge }d\wedge \tau \text{is SAT}.$$

这里的“极小”是按包含关系不可再删，不是约束数量全局最少，也不保证唯一。背景若已单独阻止目标，则 $M$ 可以为空；报告必须同时展示背景与目标，不能只列约束名。

后端返回的 unsat core 或冲突集合不一定极小。IIS 也要明确它是在原始业务约束、变量界还是底层求解行的粒度上不可约，不能只靠映射名称就宣称得到原始约束层面的 MUS。

删除式缩减保持目标和背景不动，每次试删一条候选约束：

M = 一个已确认的阻塞集合
对 M 中的每个候选 c：
    求解 B ∧ (M 去掉 c) ∧ 目标
    若确认 UNSAT：从 M 删除 c
    若确认 SAT：保留 c，并记录可行见证
    若 Unknown：保留 c，标记极小性尚未确认

因未知状态或预算停止时，可以报告有效冲突，但不能报告已证明极小。诊断激活条件必须真正控制对应原始约束；求解器生成的辅助约束不能在停用原始规则后仍无意中约束模型。

6.1 例子：两条容量约束共同阻塞

设 $x,y\in {\mathbb{Z}}_{\ge 0}$，两条生产线各有容量约束 $c_A:x\le 5$、$c_B:y\le 5$，目标为最大化 $x+y$。最优值为 10，要求 $\tau :x+y\ge 11$ 时不可行。

相对于背景“$x,y$ 为非负整数”，$M=\{c_A,c_B\}$ 是极小阻塞集合：移除 $c_A$ 后 $(6,5)$ 满足剩余条件，移除 $c_B$ 后 $(5,6)$ 满足剩余条件。解释是“两条生产线的容量合起来限制了总产量”，而不是把每条约束各自标为独立阻塞原因。

7. 阻塞解释不等于放宽建议

从一个极小阻塞集合删除任意成员，只能解除这一组条件对目标的阻塞，不保证完整模型马上可达：其他约束仍可能形成另一组冲突。

在前面的整数产量例子中，目标 $q\ge 11$ 分别被 $\{c_1\}$ 和 $\{c_2\}$ 阻塞，因此存在两个单元素阻塞集合。只移除其中一个仍无济于事。这与两条生产线容量构成的双元素阻塞集合具有不同的业务含义。

极小修正集合（MCS）关注的是“从完整模型移除哪些允许修改的约束，能够恢复目标可行性，且移除集合不能再缩减”。它与 MUS 是不同对象；数量最少、代价最小和按包含关系极小也不同。生成建议还要加入业务可放宽范围、代价和审批条件，不能把诊断结果直接执行为规则修改。

8. OSPF 中的分析组织与业务解释

分析以 solver-neutral 模型语义为中心，根据后端能力选择 LP 对偶、完整模型重求解、原生冲突核或重复满足性求解。原生 CP 全局约束没有合适的 LP 路径时，可以直接使用目标可行性和冲突分析；采用精确转换时，也应保留原始语义身份。

使用稳定的 ConstraintId、ObjectiveId 和约束分组连接不同派生模型。公共证据描述原始约束、变量界、稀疏域和目标条件，而不是 solver row、辅助变量或 native handle。一个全局约束转换成多条底层约束后，仍应回到原始业务规则解释。

报告可以先按领域／约束组展示，再展开到实例，但实例级极小集合的分组汇总不自动成为组级极小集合。Kotlin 与 Rust 接入遵循相同的目标方向、状态、容差和证据语义，不把某个后端的可选能力当成所有路径的共同能力。

两条生产线示例的概念报告可以写成：

基线：总产量 10，已证明最优
目标：总产量至少 11
背景：两条生产线的产量均为非负整数
活动性：生产线 A 容量、生产线 B 容量均活动
目标结论：不可达
阻塞集合：{生产线 A 容量 <= 5，生产线 B 容量 <= 5}
极小性：相对于所列背景与目标，已证明按包含关系极小
业务解释：两条生产线的容量共同限制总产量达到 11

实际报告还应保留模型与目标身份、扰动参数、求解状态、局部敏感性的适用范围，以及任何未完成分析的不确定性。对多个目标幅度重复分析，可以观察哪些约束持续出现，但有限次观察不等于对所有目标幅度的结构性证明。

这使分析结果既能回答“当前方案卡在哪里”，又能明确区分“已观察到的收益”“指定目标的不可达证据”和“仍需业务决策的调整方向”。如何将这些原始约束组织到业务上下文中，可参阅使用领域驱动设计架构。