第 9 章：Farkas 引理与 LP/ILP 调度合成

直觉

第 8 章的合法性看起来包含无限多个条件。参数 $N$ 没有固定上界时，一条依赖关系可以含任意多实例；若逐点检查

$$ \theta_T(y,p)-\theta_S(x,p)\ge1, $$

就无法在编译期枚举完所有 $(x,y,p)$。但是调度差和依赖约束都是仿射的。Affine form of Farkas lemma 利用这一结构，把“某个仿射式在整个非空多面体上非负”改写为有限多个非负乘子和系数等式。

关键直觉是：若多面体由若干个已知非负式定义，那么这些非负式的任意非负线性组合仍在多面体上非负。Farkas 引理说明，在适当条件下，所有在该多面体上处处非负的仿射式都可这样取得，并允许再加一个非负常数 $\lambda_0$。于是全称量词消失，留下调度系数和乘子的有限线性系统。

这一步只建立合法解的可行域，并不自动选择最快的调度。编译器还要另设目标，例如缩短依赖距离、尽早暴露 coincident 维，或构造适合 tiling 的 permutable band。变量域和离散选择决定最终是 LP、ILP，还是更复杂的参数化/词典序优化问题。

还有一条不可跨越的边界：普通 Farkas 引理直接讨论实数或有理多面体，不是任意整数 Presburger 集合。整数程序可以走实松弛的保守路径，或先求 integer hull 取得精确路径；同余、析取和量词结构则不能原样塞进普通 Farkas。

形式定义

只够本章使用的 LP/ILP 背景

一组线性等式和不等式定义一个可行域。在线性规划（LP）中，未知量允许取实数或有理数；在整数线性规划（ILP）中，指定的未知量必须取整数。若另给线性目标函数，求解器在可行域中最小化或最大化它；没有目标时，问题只是可行性检查。

例如

$$ Q=\{(u,v)\in\mathbb R^2\mid u\ge0,\ v\ge0,\ 3-u-v\ge0\} $$

是顶点为 $(0,0),(3,0),(0,3)$ 的三角形：

v
3  *
   |\
   | \
   |  \
0  *---*  u
   0   3

要求 $f(u,v)=4-u-v$ “对所有 $(u,v)\in Q$ 非负”，表面上是连续无限多个点上的约束。实际上

$$ 4-u-v=1+(3-u-v), $$

即非负常数 1 与第三条面约束的非负组合，所以一张有限证书便覆盖整个三角形。这里没有在三个顶点上碰运气；证书代数地证明了所有点。

在调度问题中，LP/ILP 的未知量可包括调度系数、距离界和 Farkas 乘子；另行设计的模型还可含表示 band 或 fusion/distribution 选择的整数变量。对偶乘子可以直观理解为每条已知域约束在证书中使用多少权重；本章只需要这种证书直觉，不展开通用对偶理论。本章给出的多维有限化采用逐维求解，不把所有维的 residual 选择编码成一个联合 ILP。

Affine form of Farkas lemma

令

$$ P=\{z\in\mathbb R^d\mid Az+b\ge0\} $$

是非空多面体，其中 $A\in\mathbb R^{m\times d}$、$b\in\mathbb R^m$。令

$$ f(z)=c^Tz+d_0 $$

为仿射函数。则

$$ \forall z\in P:\ f(z)\ge0 $$

当且仅当存在常数乘子

$$ \lambda_0\ge0, \qquad \lambda=(\lambda_1,\ldots,\lambda_m)^T\ge0, $$

使以下关于 $z$ 的恒等式成立：

$$ \boxed{ f(z)\equiv\lambda_0+\lambda^T(Az+b) } $$

逐项对齐变量系数和常数项，得到有限条件

$$ \boxed{ c=A^T\lambda, \qquad d_0=\lambda_0+b^T\lambda, \qquad \lambda_0,\lambda\ge0. } $$

$\lambda_0$ 相当于恒真约束 $1\ge0$ 的乘子，不能随意删掉。例如 $P=\mathbb R^d$、$f\equiv1$ 时没有面约束可供组合，但 $\lambda_0=1$ 正好给出证书。

调度中使用这一形式的经典路线可追溯到 Feautrier Part I；多维逐层构造见 Part II。这里采用 $Az+b\ge0$ 号向；若资料改用 $Az\le b$，乘子和常数式必须随之重推，不能机械照抄。

非空、等式和参数条件

应用定理前必须处理以下边界。

1. 非空性。 若 $P=\varnothing$，命题“对所有 $z\in P$”空真，但上面的非空版本不能直接套用。调度器应先删除空依赖分支，或把空性证书作为独立分支处理。
2. 闭的非严格线性约束。 普通形式接受 $Az+b\ge0$，不直接接受严格不等式、同余或非线性项。
3. 等式。 $Ez=e$ 可展开为 $Ez-e\ge0$ 与 $-Ez+e\ge0$，两条各配非负乘子；若保留为等式，其乘子应是自由变量，而不是强行非负。
4. 参数上下文。 对参数化依赖，令 $z=(x,y,p)$，并把 $C(p)$ 与 source/sink 域、依赖约束一并放入 $Az+b\ge0$。漏掉参数上下文会扩大或改变全称域。
5. 乘子是常数未知量。 $\lambda$ 可和调度系数一起求解，但不能依赖 $z$；否则出现未知量乘未知量，有限系统不再是这里的线性系统。

整数严格时间与尺度

若调度时间戳已经规定为整数，对 $(x,y)\in\Delta_{S\to T}$，严格先后

$$ \theta_S(x,p)<\theta_T(y,p) $$

等价于把

$$ f(x,y,p)=\theta_T(y,p)-\theta_S(x,p)-1 $$

要求为非负。Farkas 处理的是这个含常数 $-1$ 的仿射式；不能只证明差值 $\ge0$，那只能得到弱满足。

若 LP 阶段允许有理调度系数，则某个合法差值可能是 $1/3>0$。在尚未固定尺度时，$>0$ 与 $\ge1$ 并不等价。可在得到有限个有理系数后用所有分母的公倍数统一放大时间戳，或预先规定归一化的整数系数；只有完成这种尺度约定，才可使用单位间隔形式。

手算示例

从无限实例约束到有限线性系统：完整系数对齐

设 source 实例为 $S(i)$，sink 实例为 $T(j)$。先采用实松弛后的非空依赖多面体

$$ P=\{(i,j)\in\mathbb R^2\mid i\ge0,\ j-i-1\ge0,\ 3-j\ge0\}. $$

取 $z=(i,j)^T$，则

$$ A= \begin{bmatrix} 1&0\\ -1&1\\ 0&-1 \end{bmatrix}, \qquad b= \begin{bmatrix} 0\\-1\\3 \end{bmatrix}, \qquad Az+b\ge0. $$

待求的一维仿射调度是

$$ \theta_S(i)=\alpha_Si+\beta_S, \qquad \theta_T(j)=\alpha_Tj+\beta_T. $$

整数严格先后要求，对 所有 $(i,j)\in P$，

$$ \begin{aligned} f(i,j) &=\theta_T(j)-\theta_S(i)-1\\ &=-\alpha_Si+\alpha_Tj+(\beta_T-\beta_S-1)\ge0. \end{aligned} $$

这是一族随 $(i,j)$ 变化的无限约束。由于 $P$ 非空，affine Farkas 给出有限个乘子，使

$$ \begin{aligned} f(i,j)\equiv{}&\lambda_0 +\lambda_1 i +\lambda_2(j-i-1) +\lambda_3(3-j),\\ &\lambda_0,\lambda_1,\lambda_2,\lambda_3\ge0. \end{aligned} $$

右侧完整展开为

$$ (\lambda_1-\lambda_2)i +(\lambda_2-\lambda_3)j +(\lambda_0-\lambda_2+3\lambda_3). $$

分别对齐 $i$ 系数、$j$ 系数和常数项，得到

$$ \boxed{ \begin{aligned} -\alpha_S&=\lambda_1-\lambda_2,\\ \alpha_T&=\lambda_2-\lambda_3,\\ \beta_T-\beta_S-1 &=\lambda_0-\lambda_2+3\lambda_3,\\ \lambda_0,\lambda_1,\lambda_2,\lambda_3&\ge0. \end{aligned}} $$

左侧原本说“每个依赖实例都合法”，右侧只剩 3 个系数等式和 4 个非负条件。它们对调度未知数 $\alpha_S,\alpha_T,\beta_S,\beta_T$ 与 Farkas 乘子都是线性的，因为 $A,b$ 是依赖多面体的已知系数，乘子没有与调度未知量相乘。

现在完整复算 identity 解：

$$ \alpha_S=\alpha_T=1, \qquad \beta_S=\beta_T=0, $$

并取

$$ \lambda_2=1, \qquad \lambda_0=\lambda_1=\lambda_3=0. $$

三个等式逐条成为

$$ -1=0-1, \qquad 1=1-0, \qquad 0-0-1=0-1+0. $$

即 $-1=-1$、$1=1$、$-1=-1$，且所有乘子非负。代回恒等式得到

$$ f(i,j)=j-i-1, $$

恰好是第二条依赖面约束。常数 $-1$、向量 $b$ 中的 $-1,3$，以及 $\lambda_0$ 都参与常数项对齐；省略其中任何一个都会得到另一套错误系统。

参数化依赖的有限化模式

若依赖分支写成

$$ P_{S\to T} =\{z=(x,y,p)\in\mathbb R^d\mid Az+b\ge0\}, $$

其中各行同时包括 $C(p)$、source/sink 域与依赖约束，而调度差减一写成

$$ f(z)=c(\gamma)^Tz+d_0(\gamma), $$

$\gamma$ 表示全部待求调度系数，那么对每个已确认非空的凸分支引入一组独立乘子并添加

$$ c(\gamma)=A^T\lambda, \qquad d_0(\gamma)=\lambda_0+b^T\lambda, \qquad \lambda_0,\lambda\ge0. $$

这就是量词到有限约束的完整链：

$$ \Delta_{S\to T} \longrightarrow \forall z\in P:\ f(z)\ge0 \longrightarrow \text{Farkas 乘子证书} \longrightarrow \text{有限 LP/ILP 约束}. $$

以上模式每次只要求全称域 $P$ 的约束矩阵 $A,b$ 已知。对多维调度，当前层可令 $f=d_r$，在已知 residual dependence 上证明弱满足；哪些整数实例严格满足 $d_r\ge1$，则要等当前维系数选定后再计算。前层距离为零的实例必须继续约束，不能因本层只证明 $d_r\ge0$ 就丢弃。

多维 residual 的顺序有限化

对一个固定候选调度，第 8 章的

$$ U_r=U_{r-1}\cap\{z\mid d_r(z)=0\} $$

只是集合定义，因为所有 $d_r$ 已知。合成未知调度时，本章明确采用以下顺序算法；对析取关系，步骤中的 Farkas 系统按每个非空凸分支分别建立。

1. 输入已知 residual。 第 $r$ 轮开始时，$U_{r-1}$ 已有只含程序变量 $z$ 和已知数值系数的表示。首轮 $U_0=\Delta_{S\to T}$ 来自依赖分析；后续各轮的表示来自已固定的前一维。若某个实松弛分支写成

   $$ U_{r-1}=\{z\mid A_{r-1}z+b_{r-1}\ge0\}, $$

   则 $A_{r-1},b_{r-1}$ 在本轮不是求解变量。

2. 求当前维。 令当前差值为

   $$ d_r(z)=c_r(\gamma_r)^Tz+e_r(\gamma_r), $$

   其中 $\gamma_r$ 收集第 $r$ 维未知调度系数。在已知 $U_{r-1}$ 上对 $d_r\ge0$ 应用 Farkas，得到

   $$ c_r(\gamma_r)=A_{r-1}^T\lambda^{(r)}, \qquad e_r(\gamma_r)=\lambda_0^{(r)}+b_{r-1}^T\lambda^{(r)}. $$

   因为 $A_{r-1},b_{r-1}$ 已知，这些式子对 $\gamma_r,\lambda^{(r)}$ 仍是线性的。调度器在该轮的进展、独立性与性能准则下选择一个解。

3. 固定当前维并计算新 residual。 固定所有语句的 $\gamma_r$ 后，$d_r$ 成为已知仿射式。整数时间下再计算

   $$ K_r=U_{r-1}\cap\{z\mid d_r(z)\ge1\}, \qquad U_r=U_{r-1}\cap\{z\mid d_r(z)=0\}. $$

   $K_r$ 由本维严格承载；$U_r$ 是下一轮的 residual dependence。若 $U_r$ 为空，构造结束。

4. 下一维重新建模。 若 $U_r\ne\varnothing$，先把这个已知集合化为所选实松弛、integer hull 或非空分支的有限描述，再为第 $r+1$ 维引入全新的 Farkas 乘子并重复步骤 1–3。

这个“已知 $U_{r-1}$ → 求并固定当前维 → 计算已知 $U_r$ → 下一维重新建模”的次序避免了双线性。若不固定 $\gamma_r$，把 $d_r(\gamma_r,z)=0$ 直接加入下一层前提，则下一层约束矩阵会成为 $A_r(\gamma_r)$。下一次系数对齐含

$$ c_{r+1}(\gamma_{r+1}) =A_r(\gamma_r)^T\lambda^{(r+1)}, $$

右侧出现上一维未知系数 $\gamma_{r,a}$ 与下一层未知乘子 $\lambda_b^{(r+1)}$ 的乘积。无论把等式拆成两条不等式还是使用自由乘子，这种乘积都是双线性的，不是普通 LP/ILP 约束。联合求所有维需要另行给出有界的离散选择、indicator/big-M 或其他经过证明的线性化；本章没有构造这种编码，也不声称上述逐维公式组成一个联合 ILP。

整数语义的三条路径

真实依赖实例属于整数点。设某个凸分支的实描述为 $P\subseteq\mathbb R^d$，实际实例为 $P\cap\mathbb Z^d$。必须明确选择以下路径之一。

路径一：对实松弛使用 Farkas——可靠但仅充分

若证明 $f\ge0$ 对整个 $P$ 成立，它当然对 $P\cap\mathbb Z^d$ 成立，所以结果对整数程序安全。但反向未必成立。

最小反例是

$$ P=[0,\tfrac12], \qquad P\cap\mathbb Z=\{0\}, \qquad f(x)=-x. $$

在唯一整数点 $x=0$ 上，$f(0)=0\ge0$；但在分数点 $x=1/2$ 上，$f=-1/2<0$。因此要求实松弛上非负会排除一个在所有整数实例上合法的候选。除非已知 $P$ 是 integral polyhedron，否则不能把这条路径称为整数精确。

路径二：先取 integer hull——仿射检查的精确路径

定义整数凸包

$$ H=\operatorname{conv}(P\cap\mathbb Z^d). $$

对仿射 $f$，

$$ f\ge0\text{ on }P\cap\mathbb Z^d \iff f\ge0\text{ on }H. $$

正向成立是因为非负半空间是凸集，包含所有整数点就包含它们的凸包；反向由 $P\cap\mathbb Z^d\subseteq H$ 立即得到。若取得

$$ H=\{z\mid A_Hz+b_H\ge0\} $$

的有限有理描述并确认它非空，就可在 $H$ 上应用普通 affine Farkas，精确刻画该整数点集上的仿射非负性。对有理多面体，integer hull 仍是有理多面体；但计算它的 H-representation 及其描述规模本身可能很昂贵。若整数点集为空，也仍须先处理空关系。

路径三：一般 Presburger 集合——不能直接套普通 Farkas

一般 Presburger 关系可以含同余、析取、非凸空洞和尚未消去的整数存在量词，例如

$$ (x\equiv1\pmod3\land x\ge0) \quad\lor\quad (x\equiv2\pmod5\land x\le20). $$

它不是单个 $Az+b\ge0$ 实多面体。普通 Farkas 不理解“只取某些剩余类”，也不编码析取。可选策略是：先分解为有限个非空可处理分支；对同余引入整数变量或按剩余类参数化；计算实际整数集合的凸包并取得 H-representation；或者保留 Presburger 结构，改用 Omega/整数线性算术/量词消去方法。不能删除同余与析取后，假装得到的实松弛仍是原集合的精确表示。

调度优化目标：合法域之上再选择

合法性、可行性与目标函数是三层不同问题

完整逻辑顺序是：

1. 合法性条件规定每条 source → sink 依赖必须严格词典序向前；
2. 有限化在选定的实松弛或 integer hull 上，把全称非负条件变为有限线性约束；
3. LP/ILP 可行域询问是否存在满足这些约束的调度系数和乘子；
4. 性能目标在合法可行解中按延迟、并行性、同步、通信、局部性、tileability 或系数大小选择候选。

因此，“Farkas 求出了最优调度”不准确；Farkas 只提供非负性的有限证书。“ILP 解可行”也不自动等于程序语义合法；只有当 ILP 完整编码了全部依赖、分支、严格性和整数尺度时，那个可行域才对应所声称的合法域。

为什么会形成 LP 或 ILP

• 若调度系数、距离界和乘子允许取有理数，所有约束与目标均线性，可形成 LP；求解后还须按既定尺度清分母并复核严格性。
• 若要求调度系数直接为整数，当前维的有限系统可形成 ILP。Band、fusion/distribution 或跨维承载等离散决策也可进入 ILP，但前提是另行给出有效界和正确的 indicator/big-M/析取线性化；本章没有给出这种联合编码。
• 参数化最优值可能需要 parametric LP/ILP；优先并行、再最小通信之类层级偏好常用 lexicographic optimization，不能在没有权重界证明时随意折成一个加权和。

Feautrier Part I 的一维路线把因果约束与 latency/delay 等选取准则连接起来，Part II 则递归构造多维时间。Pluto 类方法进一步用整数优化选择独立、可 tile 的超平面，兼顾并行性与局部性；一手工程论文入口见 Pluto 项目/作者资料页与 Pluto+。这些方法的具体目标并不相同，不能统称成同一个算法。

两个都合法但性能不同的调度

仍取逐元素依赖 $P(i)\to C(i)$。

分阶段调度

$$ \Theta_P(i)=(0,i), \qquad \Theta_C(i)=(1,i) $$

与融合调度

$$ \Theta_P(i)=(i,0), \qquad \Theta_C(i)=(i,1) $$

的依赖距离分别是 $(1,0)$ 和 $(0,1)$，所以都合法。后者常缩短 producer–consumer 距离，降低中间数组工作集；前者可能让两个规则阶段分别向量化、批处理或映射到不同设备。合法性可行域必须同时容纳二者，性能目标和机器代价模型才决定选谁。

常见线性化目标包括：引入变量 $L$ 作为依赖距离或延迟的上界并最小化 $L$，让 producer 与 consumer 更接近；优先让更多依赖在较早维被严格承载，以暴露后续 coincident 维；约束 band 内距离分量非负，以获得可置换、可 tile 的结构。每一种都是合法域上的附加选择，不能替代 $\theta_T-\theta_S$ 的因果约束。

编译器用途

1. 消去全称实例枚举。 对每个非空凸依赖分支建立 Farkas 乘子，将无限多个实例约束变成有限系数等式与非负条件。
2. 构造多维调度。 每轮只在已知 residual dependence 上建立弱满足约束；求解并固定当前维后计算新的 $U_r$，再为下一维重新建立 Farkas 系统，直到残余为空。
3. 选择精度路径。 快速保守实现可对实松弛求证；需要整数精确时可计算 integer hull；同余和析取明显时必须分解或调用 Presburger/Omega 能力。
4. 连接求解器。 连续变量形成 LP；整数系数和离散结构形成 ILP。求解状态“可行”只说明编码过的系统有解，不能补回遗漏的依赖或参数条件。
5. 实现层级性能目标。 编译器可先最大化并行/承载，再最小化通信或系数，并保留每层目标的优先级语义。
6. 生成可审计证书。 调度系数与 Farkas 乘子可代回恒等式，逐项检查变量系数、常数项、乘子非负和依赖分支非空性。

常见误区

1. 漏掉非空条件。 空依赖分支上的全称命题只是空真，不能无条件引用非空版 affine Farkas 表示。
2. 删掉 $\lambda_0$。 非负常数本身需要恒真生成元；只组合面约束会丢失合法证书。
3. 只对齐变量系数。 $d_0=\lambda_0+b^T\lambda$ 与变量等式同样必要；调度严格性中的 $-1$ 不能消失。
4. 混用不等式号向。 本章固定 $Az+b\ge0$；换成 $Az\le b$ 必须重新推导乘子形式。
5. 给等式只配一个非负乘子。 等式应拆为两个反向不等式，或使用自由乘子。
6. 让乘子依赖实例变量。 这会产生未知量乘积，不再是当前有限线性系统。
7. 漏掉参数上下文。 $C(p)$ 必须进入 $z=(x,y,p)$ 的全称域。
8. 把实松弛称为整数精确。 它总是安全充分条件，却可能因分数点排除整数上合法的候选。
9. 把 integer hull 和整数点集混为一物。 前者是连续凸集，后者是离散集合；仿射非负性在二者上的等价需要明确论证。
10. 把一般 Presburger 公式直接交给 Farkas。 同余、析取和整数存在量词必须先分解、参数化、求凸包，或改用整数方法。
11. 对有理时间无条件使用差至少 1。 单位间隔依赖整数时间戳或清分母后的归一化尺度。
12. 把 Farkas、LP/ILP 与性能目标混成一步。 Farkas 有限化合法约束，求解器建立可行解，目标函数才作性能选择。
13. 把含未知 $d_r$ 的 residual 当成下一层已知域。 这样会让下一层 Farkas 乘子乘上上一维调度系数，形成双线性项。本文必须先固定第 $r$ 维并计算已知 $U_r$，再为下一维建模。

练习

练习 EX09-B01｜三角形上的仿射非负性（基础）

对本章三角形 $Q$，用 $f(u,v)=5-2u-v$ 判断它是否处处非负。若是，给出 $\lambda_0,\lambda_1,\lambda_2,\lambda_3$；若否，给出反例点。

答案索引： ANS-EX09-B01

练习 EX09-D01｜一维 Farkas 系数对齐（推导）

对 $P=\{x\in\mathbb R\mid x\ge1\land4-x\ge0\}$ 和 $f(x)=ax+b$，按 $Az+b\ge0$ 号向写出含 $\lambda_0$ 的恒等式，并完整对齐 $x$ 与常数项。

答案索引： ANS-EX09-D01

练习 EX09-D02｜候选调度的直接检查与证书（推导）

在本章 $(i,j)$ 依赖例中检验候选 $\theta_S(i)=0,\theta_T(j)=j$。先直接求严格合法性仿射式 $f=\theta_T-\theta_S-1$，再找一组非负乘子验证有限系统。

答案索引： ANS-EX09-D02

练习 EX09-D03｜等式乘子的两种编码（推导）

把约束 $j=i+1$ 分别用两条反向不等式及非负乘子、一个等式及自由乘子表示，说明两种写法如何互相转换。

答案索引： ANS-EX09-D03

练习 EX09-C01｜实松弛与 integer hull（综合）

用 $P=[0,1/2]$、$f(x)=-x$ 解释实松弛为何只给充分条件；再求 $H=\operatorname{conv}(P\cap\mathbb Z)$，说明在 $H$ 上检查为何对仿射式精确。

答案索引： ANS-EX09-C01

练习 EX09-C02｜同余集合的 Farkas 边界（综合）

给集合 $S=\{x\in\mathbb Z\mid0\le x\le10\land x\equiv1\pmod3\}$ 引入整数变量 $k$ 写成 $x=3k+1$，解释为何不能直接删除同余后在区间 $[0,10]$ 上声称整数精确。

答案索引： ANS-EX09-C02

练习 EX09-C03｜合法调度上的性能代理（综合）

为 $P(i)\to C(i)$ 的两个合法调度各设计一个线性性能代理：一个偏好较短依赖距离，一个偏好阶段分离。说明目标与合法约束各自负责什么，并指出必要的归一化或有界性前提。

答案索引： ANS-EX09-C03

练习 EX09-C04｜Residual 合成的顺序有限化（综合）

假设一个两维调度第一维只满足 $d_1\ge0$。按“已知 $U_0$ → 求并固定 $d_1$ → 计算 $U_1$ → 为 $d_2$ 重新建模”写出四步输入输出；再说明若不固定 $d_1$，下一层 Farkas 系数对齐中哪两个未知量会相乘。

答案索引： ANS-EX09-C04

练习 EX09-D04｜空依赖分支与空真（推导）

检查空多面体 $P=\{x\mid x\ge0\land-x-1\ge0\}$。说明任意 $f$ 的全称非负命题为何空真，以及调度器应如何处理该依赖分支。

答案索引： ANS-EX09-D04

本章小结

• 对非空 $P=\{z\mid Az+b\ge0\}$，affine Farkas 把 $f\ge0$ 的全称条件等价改写为 $f\equiv\lambda_0+\lambda^T(Az+b)$，其中 $\lambda_0,\lambda\ge0$。
• 系数对齐必须同时包含 $c=A^T\lambda$ 和 $d_0=\lambda_0+b^T\lambda$；等式需拆成双向不等式或使用自由乘子。
• 整数严格调度用 $\theta_T-\theta_S-1\ge0$，但单位间隔依赖整数时间或清分母后的尺度归一化。
• 完整手算把对所有 $(i,j)$ 的无限约束化为三个系数等式和四个乘子非负条件，identity 解逐项复算成立，常数 $-1$ 未被省略。
• 多维有限化是顺序过程：每轮 residual 已知，求并固定当前维后才计算 $U_r$；直接联合下一层会产生调度系数与 Farkas 乘子的双线性积，本文不提供联合 ILP 编码。
• 对整数实例有三条明确路径：实松弛给可靠充分条件；integer hull 给仿射检查的精确路径；一般含同余或析取的 Presburger 集合不能直接套普通 Farkas。
• Farkas 负责有限化，LP/ILP 负责可行性或优化，性能目标负责在合法解中选择；三者不能混为一谈。
• Feautrier Part I/II 和 Pluto 类方法都以合法性为底线，再分别组织多维时间及并行、同步、局部性与 tileability 的优化。