整数规划

一、直观理解：只能站在格子点上的线性规划

整数规划（Integer Programming, IP）是在线性规划基础上，要求部分或全部决策变量取整数值。二维示意图上，LP 的可行域是多边形，而纯整数规划只允许落在多边形内的格子点（整数坐标）上。

最优格子点不一定是把 LP 最优解四舍五入得到的点：圆整可能跑出可行域，也可能错失真正的整数最优。因此需要分支定界、割平面等专门算法，在保证整数可行的前提下逼近最优。

典型例子：开设的生产线数量、派遣的车辆数、购买的服务器台数——「半条线」「1.3 辆车」没有意义。若所有变量都是整数，称为纯整数规划（Pure IP）；若只有部分整数，则是混合整数规划（见 MILP 专页）。

整数规划仍属于数学规划首选工具箱：在能建成线性目标与线性约束时，应优先 intlinprog 等精确方法，而不是遗传算法。

二、适用场景与优缺点

类型	说明
适用场景	人数、台数、批次等必须为整数；选址数量、班次、机位分配；在 LP 松弛解分数不可接受时；逻辑关系已线性化后的计数变量。
核心优点	建模表达力强；中小规模可求全局最优（或证明间隙）；与 LP 共享对偶/松弛下界思想；求解器成熟。
局限与缺点	NP-hard，变量与约束增多时可能极慢；大 M 过松导致分支爆炸；数值与尺度问题比 LP 更敏感；建模质量强烈影响速度。

使用前确认：

1. 哪些变量必须整数，哪些可保持连续；
2. LP 松弛是否已可行、目标数量级是否合理；
3. 时间限制与可接受的最优性间隙；
4. 是否可用更紧的约束或不必要的整数放松。

三、核心原理：松弛、分支定界与割平面

1. 模型形式

$$\begin{aligned} \min\quad & c^\mathsf{T}x \\ \text{s.t.}\quad & Ax\le b,\quad A_{\mathrm{eq}}x=b_{\mathrm{eq}} \\ & \ell\le x\le u \\ & x_j\in\mathbb{Z},\quad j\in \mathcal{I} \end{aligned}$$

当 $\mathcal{I}$ 为全部下标时即为纯 IP。

2. LP 松弛

去掉整数约束得到 LP。松弛最优值是原问题的下界（最小化时）。若松弛解已满足整数约束，则它就是整数最优解。

间隙（gap）常定义为：

$$\text{gap}=\frac{|z_{\mathrm{UB}}-z_{\mathrm{LB}}|}{\max(1,|z_{\mathrm{UB}}|)}$$

其中 $z_{\mathrm{UB}}$ 是当前最好整数可行解目标，$z_{\mathrm{LB}}$ 是全局下界。

3. 分支定界（Branch and Bound）

若某变量 $x_j$ 在松弛解中为 $3.4$，则分裂为两个子问题：$x_j\le 3$ 与 $x_j\ge 4$。每个子节点再求 LP 松弛：

• 松弛不可行 → 剪枝；
• 松弛下界已不优于已知整数解 → 剪枝；
• 得到更好的整数可行解 → 更新上界。

4. 割平面

添加不切除任何整数可行点、但切除当前分数松弛解的线性不等式，收紧松弛。现代求解器常把分支与割平面结合（Branch-and-Cut）。

5. 与 0-1 规划的关系

变量仅取 $0$ 或 $1$ 是整数规划的重要子类，有更丰富的线性化技巧，见「0-1 规划」专页。一般整数变量可通过二进制展开表示，但会增加变量数。

四、关键决策

1. 尽量少用整数变量

能连续近似且业务可接受时不要强行取整。整数变量是计算成本的主要来源。

2. 上下界尽量紧

$x\le 1000$ 比 $x\le 10^{9}$ 更有利于定界。从业务给合理 bound。

3. 先求 LP 松弛作对照

报告整数最优与松弛最优的差距，有助于判断模型是否过松、是否值得继续收紧。

4. 控制求解终止条件

竞赛与工程中常设 MaxTime 与 RelativeGapTolerance。超时返回的是「当前最好整数解 + 间隙」，不是失败，但必须如实报告。

5. 对称性

多个完全相同的整数对象会导致大量对称最优，拖慢搜索。可加排序约束破对称，例如 $x_1\le x_2\le\cdots$。

五、MATLAB 示例

用整数变量决定生产台数（必须为整数）：

$$\begin{aligned} \max\quad & 8x_1+5x_2 \\ \text{s.t.}\quad & 2x_1+x_2\le 14 \\ & x_1+2x_2\le 11 \\ & x_1,x_2\ge 0,\ \text{整数} \end{aligned}$$

f = [-8; -5];          % 最大化 -> 最小化负利润
A = [2, 1; 1, 2];
b = [14; 11];
lb = [0; 0];
ub = [20; 20];         % 合理上界
intcon = [1, 2];       % 两个变量都是整数

options = optimoptions("intlinprog", ...
    "Display", "iter", ...
    "MaxTime", 30, ...
    "RelativeGapTolerance", 1e-4);

[x, fval, exitflag, output] = intlinprog( ...
    f, intcon, A, b, [], [], lb, ub, options);

fprintf("exitflag = %d\n", exitflag);
fprintf("整数最优产量：x1=%g, x2=%g\n", x(1), x(2));
fprintf("最大利润 = %g\n", -fval);
fprintf("相对间隙 = %g\n", output.relativegap);

% 对照 LP 松弛
[xLP, fLP] = linprog(f, A, b, [], [], lb, ub);
fprintf("LP 松弛解：x1=%.4f, x2=%.4f，利润=%.4f\n", ...
    xLP(1), xLP(2), -fLP);

检查「圆整 LP 解」是否可行且是否最优：

xRound = round(xLP);
feasible = all(A * xRound <= b + 1e-9) && all(xRound >= lb);
fprintf("圆整解可行？ %d，利润 = %g\n", ...
    feasible, -f' * xRound);

六、如何解释结果

应报告：

1. 哪些变量被声明为整数及业务理由；
2. 最优整数解与目标值；
3. exitflag 与 output.relativegap（是否证明最优）；
4. LP 松弛解与整数解的差异；
5. 活跃约束与资源剩余；
6. 若未关间隙：当前最好解、下界、运行时间；
7. 敏感性：关键整数变量取邻近值时目标如何变化（可固定再优化）。

表述示例：「在 30 秒时限内得到利润 52 的整数方案，相对间隙 0，故为全局最优；LP 松弛利润为 53.5，整数性代价约为 1.5。」

七、常见误区

1. 以为四舍五入就是整数最优

圆整可能不可行，即便可行也未必最优。必须用整数求解器或可证明的枚举。

2. 把所有变量都设成整数「更保险」

多余的整数约束只会更慢。连续即可的量保持连续。

3. 上界过大或未设界

默认巨大上界使分支定界难以收紧。结合业务给紧 bound。

4. 忽略求解状态

间隙很大时仍宣称「最优方案」属于不严谨。应写明终止条件。

5. 用智能优化替代中小规模 IP

在变量几十、约束结构良好时，intlinprog 通常更可靠。启发式应留到精确法超时或模型高度非凸时。

6. 目标与约束中的隐藏非线性

$x_1 x_2$、$\min(x_1,x_2)$ 等不是 IP 自带的；需要线性化或改模型，不能直接丢进 intlinprog。

八、小结

整数规划的核心思想可以概括为：

在线性约束下优化线性目标，并强制指定变量取整；通过 LP 松弛提供界，用分支定界与割平面在整数点中搜索并证明最优。

它是处理「可数决策」的首选精确方法。建模时控制整数变量数量、收紧界与约束、报告间隙与松弛对照，比盲目增加启发式重要得多。若同时存在连续物流与整数开关，应转向混合整数线性规划。