混合整数线性规划

混合整数线性规划（mixed-integer linear programming，简称 MILP）是在有限个线性等式、不等式和变量界约束下，优化线性目标函数，并要求指定变量取整数的数学规划。它把设备数量、是否启用等离散决策，与产量、流量等连续决策放在同一模型中。与线性规划相比，整数限制改变了可行域的几何结构，也改变了求解和证明最优性的方式。

数学形式与术语

一种常用形式为 $$\begin{array}{cc}min& c^{𝖳}x\\ \text{s.t.}& Ax\le b,\\ & \ell \le x\le u,\\ & x_j\in \mathbb{Z}(j\in I).\end{array}$$ 其中 $x\in {ℝ}^n$ 为决策向量，$A\in {ℝ}^{m\times n}$、$b\in {ℝ}^m$、$c\in {ℝ}^n$ 为给定数据；$I\subseteq \{1,\dots ,n\}$ 是整数变量的索引集合。上下界允许包含表示无界的无穷值。等式可用一对反向不等式表示；最大化可通过目标函数取负转为最小化。二元变量是满足 $0\le x_j\le 1$ 的整数变量，只能取零或一。

当 $I=\varnothing$ 时，上式是连续线性规划；当所有变量均要求为整数时，是纯整数线性规划，通常简称整数线性规划（ILP）。严格区分时，“混合”指同时存在整数变量和连续变量；求解器文献也常用 MILP 统称允许部分或全部变量为整数的线性模型。整数规划关注整数限制这一更广的概念；混合整数规划（MIP）还可包括非线性目标或约束，不能在所有语境下与 MILP 等同。

连续线性约束的交集是凸多面体，而加入整数限制后的可行集一般不凸。例如，$x\in \{0,1\}$ 的两个可行值的中点 $1/2$ 不可行。“一般不凸”并不排除空集、单点或整数坐标已被固定等特殊情形。存在连续变量时，可行集也不必是一群孤立格点，而可能是多个线段或多面体切片的并。

线性松弛与上下界

删除整数限制、保留其他约束，所得问题称为线性规划松弛。记原可行集为 $F$，松弛可行集为 $P$，则 $F\subseteq P$。假定两者最优值均有限，最小化时有 $$z_{\mathrm{L}\mathrm{P}}\le z_{\mathrm{M}\mathrm{I}\mathrm{L}\mathrm{P}}\le c^{𝖳}\hat{x}(\hat{x}\in F).$$ 证明只需比较搜索范围：在较大的集合上取最小值，不可能比在子集上更大；而最优值又不会超过任意可行解的目标值。最大化时不等号方向相反：松弛最优值给出上界，已知可行解给出下界。

因此，若某个松弛最优解恰好满足全部整数要求，它同时就是原问题的最优解。若松弛不可行，原问题也不可行；若松弛无界，则不能仅据此断言原问题可行或无界。例如，约束 $x=1/2$、$y\ge 0$ 下最大化 $y$ 的松弛无界，但加上 $x\in \mathbb{Z}$ 后不可行。线性松弛的作用及这些集合关系，是分支定界构造界限的基础。

一个可完整求解的二维例子

以下为说明方法而构造的算例，其中只有 $x$ 必须取整数： $$\begin{array}{cc}max& 4x+3y\\ \text{s.t.}& 2x+y\le 4,\\ & x+2y\le 4,\\ & x\ge 0,y\ge 0,\\ & x\in \mathbb{Z},y\in ℝ.\end{array}$$

线性松弛的可行域与整数横坐标上的可行切片。松弛最优点为 (4/3,4/3)，混合整数最优点为 (1,3/2)。

松弛中两条资源边界交于 $(4/3,4/3)$。将第一条不等式乘 $5/3$，第二条乘 $2/3$ 后相加，可得 $$4x+3y\le \frac{5}{3}\cdot 4+\frac{2}{3}\cdot 4=\frac{28}{3}.$$ 交点达到这一界限，故它是松弛最优解，最优值为 $28/3$，但其 $x$ 非整数。

原问题中 $2x+y\le 4$ 与非负性给出 $x\in \{0,1,2\}$。固定 $x$ 后，由于目标中 $y$ 的系数为正，应取 $$y=min\{4-2x,\frac{4-x}{2}\}.$$ 三个整数横坐标分别给出 $(0,2)$、$(1,3/2)$、$(2,0)$，目标值依次是 $6$、$17/2$、$8$。因此混合整数最优解为 $(1,3/2)$，最优值为 $17/2=8.5$。

若仅把松弛解的 $x$ 四舍五入到一，保留 $y=4/3$，得到的方案虽可行，目标值却只有八；固定 $x=1$ 后重新优化连续变量，才能得到本例的最优值。若把 $x$ 向上取整到二并保持原来的 $y$，则第一条约束被违反。舍入可能损失目标值，也可能破坏可行性；固定部分整数变量后重新求解只是构造候选解的办法，一般不构成全局最优性证明。

这个例子也显示了“混合”的几何含义：在 $x=0$ 和 $x=1$ 上分别保留一整段连续可行值，在 $x=2$ 上只剩一个点。$(0,2)$ 与 $(1,3/2)$ 都可行，但其中点的横坐标为 $1/2$，不满足整数要求。最优点的纵坐标 $3/2$ 则完全合法，因为它不在整数索引集合内。把所有变量都取整，会把本题改成另一个问题。

分支定界

分支定界把整数选择逐步划分成子问题，并用松弛界限排除不可能改善当前解的部分。若节点松弛解中某个整数变量取非整数值 ${\overline{x}}_j$，可建立两个子节点： $$x_j\le \lfloor {\overline{x}}_j\rfloor \text{或}{x}_j\ge \lceil {\overline{x}}_j\rceil .$$ 每个整数可行解恰好属于其中一支，所以该划分不会遗漏原问题的整数解。以最大化为例，记当前最佳可行解的目标值为 $L$。若某节点的松弛不可行，或其有效上界不超过 $L$，就可剪去该节点；若其松弛最优解满足整数限制，则已求出该节点的最优解，可据此更新当前最佳解并结束该节点。

示例的分支定界树。根节点松弛上界为 28/3；按 x≤1 与 x≥2 分支后，上界分别为 17/2 与 8。

在上述算例中，对 $x=4/3$ 分支。左支增加 $x\le 1$，由 $y\le (4-x)/2$ 可得 $$4x+3y\le 6+\frac{5}{2}x\le \frac{17}{2},$$ 且 $(1,3/2)$ 达到此界。右支增加 $x\ge 2$，原约束与非负性共同迫使 $x=2,y=0$，上界为八。两支覆盖全部整数可行解，且都不能超过已有解的 $17/2$，从而证明全局最优。

在精确算术、节点问题正确处理且搜索树有限的前提下，处理完全部节点即可证明最优或不可行。整数变量均有有限取值范围时，逐步缩小整数范围提供了有限枚举的基础；不应把这种结论直接推广成任意无界模型的朴素分支策略都必然有限终止。节点数仍可能极大。实际求解器还结合预处理、有效割平面和启发式方法：割平面收紧松弛而保留所需整数解，启发式寻找更好的可行解，两者分别改善界限和当前解。

启用决策与有限界限

设连续产量为 $q$，启用状态为 $z\in \{0,1\}$，经过验证的产量上界为有限常数 $U\ge 0$。约束 $$0\le q\le Uz$$ 使得停用时产量必为零，并使正产量必然要求启用；它不保证启用后产量严格为正。若存在真实的最低开机产量 $q_{min}>0$，可另加 $q\ge q_{min}z$。固定启用成本 $F>0$ 与单位成本 $v$ 可写成线性目标项 $Fz+vq$。在最小化且没有其他约束迫使启用时，零产量方案会选择 $z=0$ 以节省固定成本。

例如，某设备最多生产十单位，启用成本为十二，每单位成本为二，且需满足四单位需求，可写成 $min12z+2q$，约束为 $4\le q\le 10z$、$z\in \{0,1\}$。最优方案为 $z=1,q=4$，成本二十。若把二元变量松弛到区间 $[0,1]$，便允许 $z=0.4,q=4$，成本只有 $12.8$；这个更低的成本只是松弛下界，不能解释为现实中支付了部分启用费。

这里的 $U$ 必须来自产能、需求或其他约束所给出的有效界，而非任意巨大常数。取值过小会误删可行方案；过大则允许松弛中的微小启用比例支持较大产量，削弱界限，并可能放大数值容差的影响。这类以常数界联系逻辑与连续变量的写法常称为大 M 建模。

最优性差距与数值计算

对已有有限上下界 $L\le z^{\ast }\le U$ 的最大化问题，绝对最优性差距为 $U-L$。相对差距的分母约定并不统一。以 Gurobi 的约定为例，若当前最佳可行值为 $z_P$，有效界为 $z_D$，则 $$g=\frac{|z_P-z_D|}{|z_P|}.$$ 两者都为零时定义差距为零；仅 $z_P=0$ 时定义为无穷。差距容限是允许的停止阈值，不是实际差距本身；相对差距还会受到目标函数常数平移的影响。

在二维例子中，若已找到目标值 $17/2$ 的方案，却暂时只使用根节点上界 $28/3$，绝对差距仍为 $5/6$，上述约定下的相对差距为 $5/51$，约为百分之九点八。此时事实上已找到最优解，但所维护的界尚不足以证明这一点。分支后全局上界降到 $17/2$，才闭合了精确算例中的差距。这区分了“找到最优方案”和“知道它已经最优”。

浮点求解还使用约束可行性与整数可行性容差。达到正的差距容限只说明在相应界限和数值约定下达到规定精度，不能据此宣称精确算术下的最优值已被证明。建模时应选择合适单位、避免不必要的系数量级悬殊，并检查返回解的约束残差、整数偏差和终止状态。时间限制结束时，有可行解不等于已证最优；没有找到可行解也不等于已证不可行。

应用与计算特点

MILP 可表达设施选址中的开设决策与运输量、生产计划中的设备启停与产量，以及排班中的人员指派与工作时间。具体模型能否保持线性，取决于成本、资源消耗和逻辑条件的表达方式。一般整数线性优化属于 NP 难问题，因而不能把连续线性规划的多项式时间可解性直接推广到 MILP。实际难度也不能只按变量数判断：松弛强弱、对称性和约束结构都很重要。应用报告通常应同时记录模型假设、可行解目标值、最佳界、差距及终止原因，使方案质量与求解证据能够被分别检验。

参见

• 线性规划
• 整数规划
• 0-1背包问题