整数规划建模技巧
本文整理混合整数规划（MIP）中常用的建模技巧，主要包括逻辑约束与非线性项的线性化等，可持续增补其他专题。
1. 逻辑约束
在数学规划中，经常需要把逻辑关系写成线性（或混合整数）约束。下面分三类：二选一约束、指示约束，以及布尔逻辑与门电路的线性化。
1.1 二选一约束（Either–Or）
设有两条约束：
若要求至少满足其中一条（逻辑上的“或”），则称为二选一约束。
Big-M 线性化：引入 – 变量 和充分大的正数 ，将条件写为：
直观说明：
- 当 时：（3.3）为 ，（3.4）为 ，在 足够大时后者基本不收紧，故强制 。
- 当 时：（3.3）为 （通常不收紧），（3.4）为 ，故强制 。
无论 取 还是 ，（3.1）与（3.2）中至少有一条被满足。
软件实现
在 Gurobi 等求解器中，此类关系也可用通用约束（General Constraints，如 And/Or、指示类 API，如 addGenConstrOr 等）直接描述，避免手写 Big-M 或减轻调 的负担。
1.2 指示约束（Indicator）
有时需要刻画条件蕴含：例如，当 成立时，必须同时有 ；当 时，对 没有强制要求。
引入 与充分大的 ，可写为：
其中 需取得足够大，使得在可行域内恒有 、（或按问题重新界定更紧的界）。
验证思路：
- 若 ，为使（3.6）可行，必须有 ；此时（3.5）给出 ，即 。
- 若 ，则（3.6）允许 或 ；取 时（3.5）变为 ，通常不限制 ，即对 无额外要求。
现代求解器中的 Indicator Constraint（指示约束）可直接写“ 某不等式”等形式，不必显式使用大 ，数值上往往更稳。
1.3 逻辑运算的线性化
设 均为 – 变量。下表给出常见逻辑关系、符号、等价的线性约束及直观解释（在 – 域内）。
| 逻辑关系 | 符号表达 | 等价线性约束 | 逻辑直觉 |
|---|---|---|---|
| 非（NOT） | （或写成 ） | 为 时 必为 ，反之亦然。 | |
| 与（AND） | 不能超过任一 ；仅当全部为 时，下界才迫使 。 | ||
| 或（OR） | 只要有一个 ， 就至少为 ；全为 时上界迫使 。 | ||
| 蕴含（If–Then） | 若 ，则 必须为 ； 时对 无限制。 | ||
| 等价（IFF） | （或 与两条不等式） | 两变量同 同 。 | |
| 异或（XOR） | 两输入相同则 ，不同则 （两变量互斥情况）。 | ||
| 与非（NAND） | 仅当 时，上界与下界同时迫使 。 | ||
| 或非（NOR） | 只要有一个为 ，上界使 ；全为 时下界使 。 |
上表第三列在格内已分多行；还可将同一逻辑关系单独排成竖式（每条约束一行），例如：
与（AND） ：
或（OR） ：
异或（XOR） ：
与非（NAND） ：
或非（NOR） ：
注：上表中 AND/OR 的 与多变量 的联合定义，在 – 整数规划下与布尔代数一致；XOR 等写法针对两个二元变量，推广到多变量需另行构造。
2. 线性化
当目标或约束中出现分段线性、绝对值、乘积、分式、/ 等非线性（或非凸）项时，常通过引入辅助变量与额外约束将其改写为线性或混合整数线性形式。下面分述常见情形。
2.1 分段线性函数线性化
设 为分段线性函数，已知断点 。可用非负权变量 与 – 区间指示变量 将 与 同时线性化。
第 1 步：在模型中凡出现 之处，用下式替换：
第 2 步增加以下约束（使 落在某一段上， 为端点值凸组合，即分段线性插值）：
直观理解： 的取值唯一激活一段区间， 的系数结构使仅有相邻断点权可同时非零，从而 位于某一子区间上， 为两端点 的线性插值。许多商业求解器也提供 SOS2 等专用结构，可替代上述显式 表示。
2.2 含绝对值形式的线性化
含绝对值的目标（如 ）可通过对每个变量引入一正一负辅助量完成线性化。
原问题示例（非光滑）：
定义（对每个 ）：
则有 、。上述问题等价于下列线性规划：
2.3 含乘积形式的线性化
若出现 ，可引入 并令 ，再按 、 类型分别处理。
情形 1： 均为 – 变量
等价于对 的线性化：
情形 2：，（连续或整数且有上界 ）
情形 3：，
（具体整数/连续与模型其余部分一致即可。）
情形 4： 均为一般连续变量时， 一般不能在保持等价的前提下完全线性化；仅能做紧近似或松弛（可参见 Sherali & Alameddine, 1992 等文献）。
2.4 含分式形式的线性化
以下记法与 Gurobi 等文档中常见分式目标线性化一致。设原问题为（分母在可行域上为正，属常见的「分式目标」形式）：
第 1 步：令 ，原目标可写为关于 的双线性目标；与 联立。此时仍未对原线性约束作 Charnes–Cooper 式改写，可显式写为
上式在目标与「归一化」行上含 ；在尚未引入 时，即通常所说的含双线性项的中间形式（未把 改写成对 的线性行；该改写见下一步）。
第 2 步：再令 ，将模型化为对 线性的形式：
（若需严格 LP/MILP 表述，可结合对 下界的处理及约束类型按求解器要求微调。）
2.5 含 / 形式的线性化
要表达 为若干可比数量 （决策变量、线性式或常数）的最大值或最小值，可配合 – 指示变量 与大 写成通用的线性组；也可直接使用 Gurobi 等提供的 addGenConstrMax / addGenConstrMin 等接口。下面为常用的 Big-M 竖式，其中 应取得足够大，使在可行域上各不等式在逻辑上恒可成立，且有界时应取尽可能紧的 以改善数值性。
通用形式 1：
对 ，有 – 变量 与常数 ：
第一组要求 不低于任一项，第二组在至少一个 时让对应 从下方“顶住”；与第一组合并得到 的可行刻画。（若需恰好一个指标为 ，可将 加强为 ，视模型与唯一性需要而定。）
通用形式 2：
第一组要求 不高于任一项，第二组在至少一个 时让对应 从上方“压住”；合起来刻画 。
例（ 的特例）
即 、、，取 与足够大 ：
的写法为通用形式 2 在 、、 时展开，例如：
备忘
（在此补充：特殊有序集、多面体松弛、二次规划/二阶锥在 MIP 中的处理，以及 Gurobi/CPLEX 的 API 速查等。）