整数规划

整数规划（Integer Programming, IP）是数学建模中处理"决策变量只能取整数"的一类优化模型。现实世界中有大量不可分割的量：人数、台数、车辆数、班次数、选址的"建/不建"……这些问题无法用普通的线性规划（LP）直接求解——LP 求出的"2.25 台设备"没有任何实际意义，而把 2.25 简单四舍五入又可能违反约束或漏掉真正的最优解。本文从原理（LP 松弛、分支定界）、适用场景、评价指标、可视化诊断到可运行代码（手写分支定界 + scipy.milp 对照），完整梳理整数规划的竞赛实战用法。

一、算法含义

1.1 通俗理解

线性规划允许决策变量取任意实数，比如"生产 2.25 台设备"；整数规划则要求变量取整数，"生产 2 台或 3 台，不允许 2.25 台"。看起来只是多加了一个小小的限制，但它把问题从"多项式时间可解"（线性规划有内点法等高效算法）变成了 NP-hard（整数规划在最坏情况下需要指数级时间）——原因在于：连续可行域是一个"一整块"的凸多面体，而整数约束把可行域打散成一个个孤立的离散格点，最优解不再有"沿着边界走到顶点"的几何直觉可用。

整数规划的求解思路可以概括为一句话：不断求解"放松掉整数约束"的线性规划（LP 松弛）来逼近整数最优解，并用"上界/下界夹逼"的方法剪掉没希望的分支。其中最核心、最经典的算法就是分支定界法（Branch and Bound, BnB），也是各大商业求解器（CPLEX、Gurobi）和开源求解器（HiGHS、SCIP）的基石。

1.2 数学模型

纯整数规划（Pure Integer Programming, PIP）——所有决策变量都必须是整数：

$\min \; c^\top x \quad \text{s.t.} \quad Ax \le b, \quad x \in \mathbb{Z}_{+}^{n}$

其中 $c \in \mathbb{R}^n$ 为目标系数向量， $A \in \mathbb{R}^{m \times n}$ 为约束系数矩阵， $b \in \mathbb{R}^m$ 为资源向量， $\mathbb{Z}_{+}$ 表示非负整数集。写成展开形式：

$\min \sum_{j=1}^{n} c_j x_j \quad \text{s.t.} \quad \sum_{j=1}^{n} a_{ij} x_j \le b_i \ (i=1,\dots,m), \quad x_j \in \mathbb{Z}_{+} \ (j=1,\dots,n)$

两个重要的变体：

混合整数规划（Mixed Integer Linear Programming, MILP）：只有部分变量要求为整数，其余可连续。设 $p$ 个整数变量、 $n-p$ 个连续变量：

$\min \; c^\top x \quad \text{s.t.} \quad Ax \le b, \quad x_j \in \mathbb{Z}_{+}\ (j=1,\dots,p), \quad x_j \ge 0 \ (j=p+1,\dots,n)$

0-1 规划（Binary / 0-1 Programming）：整数变量只能取 0 或 1，即 $x \in \{0,1\}^n$ ，常用于"做/不做"型决策（选址、项目选择、指派）。它是整数规划的特例，本文下一篇（09）专题讲解。

1.3 与线性规划的本质区别

对比项	线性规划（LP）	整数规划（IP）
决策变量	$x \in \mathbb{R}_{+}^n$ ，连续	$x \in \mathbb{Z}_{+}^n$ ，离散
可行域	凸多面体：连续、连通、"一整块"	可行域内的格点：离散、非凸、互不连通
最优解位置	一定在可行域顶点上（极点定理）	是某个格点，不一定在 LP 松弛的顶点附近
计算复杂度	多项式时间（内点法/椭球法）	NP-hard：最坏情况需指数时间
经典算法	单纯形法、内点法	分支定界法、割平面法、隐枚举
灵敏度分析	有完善的对偶理论	没有直接对应的对偶理论

几何上看（见第四节图①）：LP 的最优解可能在可行域内部某条棱的中点，比如 $(2.25, 3.75)$ ；而 IP 的最优解必须是"落在多边形内的整数格点"，它完全可能出现在距离 LP 最优解很远的另一个角落——例如本文示例中 LP 最优解是 $(2.25, 3.75)$ ，而整数最优解是 $(0, 5)$ 。这正是"四舍五入法"不可靠的根源：LP 最优解附近往往根本没有好的整数点。

1.4 LP 松弛：整数规划的"瞭望塔"

**LP 松弛（LP Relaxation）**指去掉整数约束后得到的普通线性规划：

$z_{LP} = \min \; c^\top x \quad \text{s.t.} \quad Ax \le b, \quad x \ge 0$

其与整数规划的上下界关系（最重要的一条性质，一切剪枝的根基）：

对最小化问题： $z_{LP} \le z_{IP}$ ，即 LP 松弛最优值给出整数最优值的下界；
对最大化问题： $z_{LP} \ge z_{IP}$ ，即 LP 松弛最优值给出整数最优值的上界；
反过来，任意一个整数可行解提供另一侧的界：最大化问题中它是下界，最小化问题中它是上界。

直观理解：LP 松弛的可行域 $S_{LP} \supseteq S_{IP}$ （整数点是连续点的一部分），在更大的区域里找最优，自然"不差于"（最小化时）原问题。

LP 松弛的三个用途：

定界：最大化问题中，若某个分支的 LP 松弛最优值 $z \le$ 当前下界 $LB$ ，该分支整支剪掉（见 1.5 节）；
间隙度量：LP 松弛最优值与整数最优值之差（积分间隙，见 3.3 节）衡量"松弛得紧不紧"；
特判：若 LP 松弛的最优解恰好全为整数，则该解就是整数规划的全局最优解，直接结束，无需任何分支。

1.5 分支定界法（核心算法）

思想：分而治之 + 上下界夹逼。把整数规划"切"成越来越小的子问题（分支），每个子问题求解其 LP 松弛；利用"松弛最优值 ≤ 当前最好整数解"的判定，整片整片地剪掉不可能含有最优解的区域（定界/剪枝），直到上界与下界相遇。

算法步骤（最大化问题，伪代码）：

算法：分支定界法求解最大化整数规划  max c^T x,  s.t. Ax ≤ b,  x ∈ Z₊^n
输入：目标系数 c，约束 (A, b)
输出：全局最优解 x* 与最优值 z*

 1. 初始化：待展开集合 S ← {P₀}，其中 P₀ 为根问题（原问题去掉整数约束的 LP 松弛）；
    下界 LB ← -∞（尚无整数可行解），最优解 x* ← 空
 2. 若 S 为空：输出 x* 与 LB，停止（LB 即为全局最优值）
 3. 选择：从 S 中选出上界 UB 最大的子问题 P（最佳优先策略），S ← S \ {P}
 4. 求解 P 的 LP 松弛，得到最优值 z_P（即该子问题子树的上界 UB_P）：
    (a) 若 P 的 LP 松弛不可行        → 剪枝（不可行），转 2
    (b) 若 UB_P ≤ LB                 → 剪枝（定界），转 2
    (c) 若松弛解 x_P 全为整数：
        若 z_P > LB，则 LB ← z_P，x* ← x_P
        剪枝（整数解），转 2
 5. 分支：取 x_P 中离整数最远的变量 x_j（其值为 a_j），
    生成两个子问题 P₁、P₂，分别追加约束 x_j ≤ ⌊a_j⌋ 与 x_j ≥ ⌈a_j⌉，
    即 S ← S ∪ {P₁, P₂}，转 2

三种剪枝（Pruning）的作用：

剪枝（不可行）：分支约束越加越紧，某个子问题的 LP 松弛可能直接无解，整支无望；
剪枝（定界）：该子问题松弛最优值都不超过当前最好整数解，继续搜也不可能更好；
剪枝（整数解）：松弛解恰好全为整数，它已是该子问题的最优解——如果比当前下界好就更新下界，然后该分支不需要继续（分支只会越分越差）。

几个实现细节：

分支变量选择：常用"最分数规则"（选小数部分最大的变量，离整数最远）、"强分支"（试探各变量的分支效果再选）。本文代码用最分数规则（并列取下标较大者）。
节点选择：最佳优先（先展开上界最大的节点，收敛快但队列可能很长）、深度优先（省内存）。本文代码用最佳优先。
停止条件： $UB \le LB$ （上界与下界相遇）时，当前下界对应的整数解就是全局最优解。
正确性：分支步骤对整数解"既不重复也不遗漏"（ $x_j \le \lfloor a_j \rfloor$ 与 $x_j \ge \lceil a_j \rceil$ 恰好覆盖了除分数值 $a_j$ 外的全部整数），因此搜索结束时下界必为全局最优值——分支定界是精确算法，给出的是有保证的全局最优解，而非近似解。

1.6 其他求解方法

割平面法（Cutting Plane）：不分支，而是不断向 LP 松弛添加线性"割"约束（如 Gomory 割），每次把当前的分数最优解"切出去"，但保证不切掉任何整数可行点；反复求解加割后的 LP，直到最优解变整数。思想非常优美，但纯割平面法收敛慢，现代求解器把它与分支定界结合成分支-割平面（Branch-and-Cut）。
隐枚举（Implicit Enumeration）：针对小规模 0-1 规划，理论上枚举 $2^n$ 种组合，实际用定界手段"隐式地"跳过大量组合（分支定界在 0-1 问题上的特化形式）。
现代求解器：scipy 自带的 HiGHS（本文使用）以及 CPLEX、Gurobi 等，内部实现为"预处理 + 割平面 + 分支定界 + 启发式找初始解"的组合，能求解成千上万个整数变量的大规模问题。

1.7 优缺点

优点：

建模能力极强：人数、台数、班次、"建/不建"、先后次序等大量现实约束都能表达；配合"大 M 法"还可以把"若…则…"逻辑约束写成线性整数模型；
精确：分支定界给出的是有最优性保证的全局最优解（与启发式方法有本质区别），竞赛论文中"求得了全局最优解"是一句很有分量的话；
可证明松弛紧致：LP 松弛给出上下界，可以定量回答"我的解离最优有多远"（积分间隙），这是启发式算法做不到的；
工具成熟：scipy.optimize.milp、HiGHS、CPLEX、Gurobi 等求解器开箱即用。

缺点：

NP-hard，规模受限：求解时间随整数变量个数最坏情况指数增长，变量一多（成百上千个 0-1 变量）就可能解不动；
对"坏"结构敏感：同样的变量个数，不同结构（系数矩阵、约束松紧）求解难度天差地别，难以事前精确估计耗时；
没有 LP 那样的灵敏度分析：某个系数变化 1%，最优解可能完全不同（最优解在格点上"跳跃"）；
建模有陷阱：大 M 取值不当会使 LP 松弛变得极松（间隙巨大、分支爆炸），整数约束的表达需要经验（见 7.3 节）。

二、何时使用（适用场景与条件）

2.1 适用场景

任何"决策变量本质上是离散的、且目标与约束是变量的线性函数"的优化问题都适合整数规划：

不可分割量：人数分配、设备台数、车辆数、班次数、订购次数（"派 3.7 个人"没有意义）；
选址问题：在候选点中选若干个建仓库/基站/服务站， $x_j \in \{0,1\}$ ，约束"最多建 $k$ 个""至少覆盖全部需求点"；
排班问题：护士/乘务/工人排班，班次与人数均为整数，还有"每人每周工作不超过 5 天"等逻辑约束；
生产批量问题：按批生产（一批 100 件），产量只能是批量的整数倍；
背包与项目选择：从 $n$ 个项目中选若干个使收益最大且总投入不超预算（0-1 背包）；
指派问题： $n$ 个人分配 $n$ 项任务（经典指派问题的变量恰好"自动"为整数，LP 松弛即可精确求解——见 2.5 节）。

2.2 竞赛典型题目

资源分配类：" $m$ 种资源分配给 $n$ 个部门/任务，求最大收益"——变量为整数份数；
选址-分配类："在哪几个城市建配送中心，使建造成本 + 运输成本最小"（0-1 变量 + 连续流量变量，典型 MILP）；
排班/调度类："某车间 $n$ 台机器加工 $m$ 个订单，求最短完工时间"（小型题目可直接 IP，大型题目需结合启发式）；
志愿者/人员调度类：各时段需求人数不同，志愿者报可选时段，求最少总人数或最均衡方案。

2.3 使用前提（建模前检查清单）

检查项	具体要求
线性性	目标函数与所有约束都是决策变量的线性函数（有 $x_1 x_2$ 、 $x^2$ 等乘积项时属于非线性整数规划 MINLP，难度陡增）
离散本质	变量确实不可分割：人数、台数、开关决策——而非"为了凑模型硬取整"
规模可控	整数变量个数 $n$ 在求解器能力范围内（一般纯 IP 几十到几百个变量较稳妥；大规模 0-1 问题要谨慎评估）
数据确定	所有系数（利润、资源量）已知或可用期望值代替（含随机性时考虑随机规划/鲁棒优化）

2.4 不适用 / 慎用的情形

规模过大：0-1 变量成百上千、结构复杂的选址/调度问题，分支定界可能几天都解不完。应对：改用启发式/元启发式（遗传算法、模拟退火、贪心 + 局部搜索，见第八节）、列生成（变量本身都枚举不完时）、或"LP 松弛 + 修复"（求 LP 解再就近找整数解，但必须说明是近似解，见 3.5 节）；
存在非线性：目标或约束含乘积、平方项时，应改用非线性整数规划（MINLP，可用分支定界 + 非线性求解器）或先做线性化变换（如乘积项换元）；
仅需"大致方案"：如果问题本身不要求最优、只要求"够好且快"，不必动用精确算法；
约束是"软"的：某些约束（如"最好不超过"）可以少量违反时，精确 IP 反而僵硬，可考虑罚函数 + 启发式。

2.5 与线性规划、0-1 规划、动态规划的选择

方法	适用情形	与整数规划的关系
线性规划	变量连续（资金、时间、面积）	直接求连续最优即可；勿对"本质连续"的量强行取整
整数规划（一般）	变量为一般非负整数	本文主角
0-1 规划	变量只能取 0/1（选/不选）	IP 的特例，用 $x_j \in \{0,1\}$ 建模，求解同用分支定界（见下一篇 09）
混合整数规划 MILP	部分整数、部分连续	IP 的推广，scipy.milp 同样支持（integrality 数组里标 0/1）
动态规划	问题有最优子结构且状态维度低（如背包、最短路径）	多阶段决策问题中 DP 常比 IP 更快；但状态空间大时 DP 也会"维数灾难"，此时 IP 更好

两个经典的"意外"结论（竞赛面试/答辩高频考点）：

指派问题：约束矩阵是全幺模矩阵（Totally Unimodular, TU），其 LP 松弛的每个顶点自动就是整数点，因此直接解 LP 就等于解 IP，无需分支定界；
运输问题同理（TU 矩阵），LP 最优解自动为整数（当供应量、需求量都是整数时）。

三、算法指标

下面每个指标都给出：中文名、公式（LaTeX）、含义与解读。约定：最大化问题记为 $\max$ 问题，最小化问题对称理解；符号定义见第五节。所有指标在第六节代码中都会打印（示例问题见 6.1 节）。

3.1 整数最优目标值 $z_{IP}$ （整数最优值）

$z_{IP} = \max \; c^\top x \quad \text{s.t.} \quad Ax \le b, \ x \in \mathbb{Z}_{+}^{n}$

含义：整数规划的真正答案，即最优整数解对应的目标值。本文示例 1 中 $z_{IP} = 40$ （ $x^* = (0,5)$ ）；
解读：这是分支定界最终输出的"全局最优值"。若同时给出最优解 $x^*$ ，应写" $x^* = (0,5)$ ， $z^* = 40$ "。最优解可能不唯一（示例 2 有两个最优解 $(0,3,0)$ 与 $(1,2,1)$ ，目标值均为 21），但最优值唯一。

3.2 LP 松弛最优值 $z_{LP}$

$z_{LP} = \max \; c^\top x \quad \text{s.t.} \quad Ax \le b, \ x \ge 0 \quad \text{（去掉 } x \in \mathbb{Z}_{+}^n \text{ 约束）}$

含义：放松整数约束后连续问题的最优值。示例 1 中 $z_{LP} = 41.25$ （在 $(2.25, 3.75)$ 处取得）；
解读：最大化问题中恒有 $z_{LP} \ge z_{IP}$ ， $z_{LP}$ 是整数最优值的上界（最小化问题中为下界）。它单独用处不大，但与 $z_{IP}$ 相减即得到下一个指标——积分间隙。特例：若 LP 松弛最优解恰好全为整数，则 $z_{LP} = z_{IP}$ ，直接收工。

3.3 积分间隙 / LP 松弛间隙（Integrality Gap, IG）

$\text{绝对间隙} = \left| z_{LP} - z_{IP} \right|, \qquad \text{IG（相对量）} = \frac{\left| z_{LP} - z_{IP} \right|}{\left| z_{LP} \right|} \times 100\%$

取值范围： $[0, +\infty)$ ，通常以百分比计；
方向：越小越好。IG 越小说明 LP 松弛"贴得越紧"，分支定界需要搜索的空间越小、收敛越快；
解读：示例 1 中 $\text{IG} = |41.25 - 40| / 41.25 = 3.03\%$ ——松弛只高估了 3%，很紧；示例 2 中 $\text{IG} = 10\%$ 。IG = 0 意味着 LP 松弛直接给出整数最优解。竞赛论文中"积分间隙仅 3%，说明松弛紧致、求解可靠"是标准的加分话术。

3.4 分支定界过程指标（节点数与上下界收敛）

搜索节点数 $N$ ：

$N = \text{分支定界创建过的节点（子问题）总数} = N_{\text{展开}} + N_{\text{剪枝}}$

含义：求解器实际求解过的 LP 松弛个数，反映搜索工作量。示例 1 中 $N = 7$ （展开 3 次、剪枝 4 次：整数解 2 次、定界 1 次、不可行 1 次）；
解读： $N$ 与整数变量个数 $n$ 之间最坏是指数关系（ $N$ 可到 $O(2^n)$ ），所以节点数是衡量"这题难不难"最直接的指标。剪枝越猛（间隙越小、松弛越紧）， $N$ 越小。

上下界序列与收敛过程（最大化问题）：设第 $t$ 轮展开一个节点后， $UB_t$ 为所有未剪枝节点 LP 松弛最优值的最大值（全局上界）， $LB_t$ 为当前最优整数解的目标值（全局下界）：

$UB_t = \max\{\text{待展开节点的松弛最优值}\}, \qquad LB_t = \max\{\text{已发现整数可行解的目标值}\}$

收敛性质： $UB_t$ 单调不增、 $LB_t$ 单调不减，两者从两侧夹逼 $z_{IP}$ ；当 $UB_t \le LB_t$ 时停止， $LB_t = z_{IP}$ ；
解读：示例 1 中 $UB: 41.25 \to 41 \to 40.56 \to 40$ ， $LB: -\infty \to 39 \to 39 \to 40$ （见图③）。若求解被迫中断（超时），仍可报告"当前解的相对间隙 $(UB_t - LB_t)/|UB_t|$ "作为质量保证。

3.5 与"LP 解四舍五入"方案的对比误差

设 $\hat{x} = \text{round}(x_{LP})$ （或 floor / ceil 等取整方案）：

$\text{可行性检查}: \quad A\hat{x} \le b \; ? \qquad \text{相对误差 RE} = \frac{\left| z(\hat{x}) - z_{IP} \right|}{\left| z_{IP} \right|} \times 100\%$

含义：把 LP 松弛解按某种规则取整后，看它是否可行、离整数最优有多远；
解读：示例 1 中四舍五入得 $(2,4)$ ，直接违反约束（ $5 \times 2 + 9 \times 4 = 46 > 45$ ）；向上取整得 $(3,4)$ 同样不可行（ $3+4=7>6$ ）；向下取整得 $(2,3)$ 可行但 $z=34$ ，相对误差 $\text{RE} = |34-40|/40 = 15\%$ 。注意：取整方案"有时碰巧"得到最优解（示例 2 中向下取整恰好最优），但它没有任何最优性保证，只能当作快速获得初始下界的技巧，论文中绝不能把它当成最优解报告。

3.6 求解时间 $T$

$T = \text{从开始求解到返回最优解（或超时）的墙钟时间}$

取值范围： $(0, +\infty)$ ，单位 ms / s / min；
解读：受变量个数、约束结构、分支策略影响极大，同类问题规模翻倍可能耗时变成平方、指数。竞赛中应报告时间并设置超时保护（如 milp 的 time_limit 参数），超时后转报"最好解 + 间隙"。示例 1、2 的规模极小，均在毫秒级求解。

3.7 求解器内部间隙 mip_gap（可选，参考指标）

$\text{mip\_gap} = \frac{\left| UB - LB \right|}{\left| UB \right|}$

含义：HiGHS/CPLEX/Gurobi 等求解器在停止时刻报告的相对间隙（上下界之差的相对量）；
解读：正常求解到最优时 $\text{mip\_gap} = 0$ ；若因超时而停止，mip_gap 即"当前最好解离最优可能还差多少"的质量保证。 $< 1\%$ 通常被认为足够好。

3.8 指标汇总表

指标	中文名	公式	方向	一句话解读
$z_{IP}$	整数最优值	$\max c^\top x,\ Ax \le b,\ x \in \mathbb{Z}_{+}^n$	—	整数规划最终答案（示例 1：40）
$z_{LP}$	LP 松弛最优值	$\max c^\top x,\ Ax \le b,\ x \ge 0$	—	整数最优值的上界（max 问题）
IG	积分间隙	$\lvert z_{LP} - z_{IP} \rvert / \lvert z_{LP} \rvert$	越小越好	松弛紧致程度；0 即 LP 直接给出整数解
$N$	搜索节点数	$N = N_{\text{展开}} + N_{\text{剪枝}}$	越小越好	搜索工作量，最坏随 $n$ 指数增长
$UB_t, LB_t$	上下界序列	见 3.4 节定义	收敛越快越好	夹逼 $z_{IP}$ ；相遇即最优
RE	四舍五入相对误差	$\lvert z(\hat{x}) - z_{IP} \rvert / \lvert z_{IP} \rvert$	越小越好	取整方案离最优多远；无最优性保证
可行性	取整解可行性	$A\hat{x} \le b$ 是否成立	必须成立	示例 1 四舍五入 $(2,4)$ 违反约束
$T$	求解时间	墙钟时间	越短越好	与规模、结构、分支策略相关
mip_gap	求解器相对间隙	$\lvert UB-LB \rvert / \lvert UB \rvert$	越小越好	停止时刻的质量保证，最优时为 0

四、可视化图表

整数规划不是"调包出个数就完事"，画图诊断和算指标同等重要。以下 4 张图覆盖"松弛与整数解的关系 + 搜索过程 + 收敛过程 + 取整方案对比"，全部代码见第六节，图片自动保存到 figures/ 目录（文件名统一前缀 ilp_）。

4.1 四张图速查表

图名（输出文件）	用途	关键解读点
① LP 松弛可行域 + 整数格点 + 两类最优解（`ilp_lattice.png`）	直观展示"连续可行域 vs 离散格点"，以及 LP 最优解与整数最优解可能相距很远	蓝色多边形是 LP 可行域；深色点是可行整数格点（候选方案）；星形是 LP 松弛最优解 $(2.25, 3.75)$ ；青绿圆是整数最优解 $(0,5)$ ——两者距离很远，且四舍五入点 $(2,4)$ 落在可行域之外
② 分支定界搜索树（`ilp_bnb_tree.png`）	展示分支、定界、剪枝全过程	每个盒子是一个节点（LP 松弛子问题）；边上标注分支方向（ $x_2 \le 3$ 等）；青绿盒子 = 更新了下界的整数解；灰盒子 = 定界剪枝；红盒子 = 不可行剪枝
③ 上界/下界收敛曲线（`ilp_bnb_convergence.png`）	展示上下界夹逼最优值的过程	蓝线（上界 UB）单调下降、橙线（下界 LB）单调上升；两条线之间的浅色带 = 最优值还可能在的区间；最终 UB = LB = 40 相遇，最优性得证
④ 四舍五入 vs 整数最优对比图（`ilp_rounding.png`）	定量对比"取整方案"与"真正最优"的差距	LP 松弛值 41.25 是不可达到的上界；整数最优 40；向下取整只有 34（低 15%）；四舍五入方案不可行（红条标注原因）

4.2 每张图"好"与"异常"的特征

图① 可行域 + 格点图

好图特征：可行域多边形清晰；LP 最优解与整数最优解都能看到；取整点若不可行会明显落在多边形外。本示例即"教科书级"好图：LP 最优解在内部、整数最优解在角落，一眼看懂"整数约束改变了最优解"。
异常特征 / 警示：若整数最优解紧挨着 LP 最优解（间隙小），图上看不出差距——此时改用图④的数值对比；变量超过 3 维时无法直接画，只能投影到某两个变量画"切片图"（论文中注明投影方式）。

图② 搜索树

好图特征：每个节点标注松弛解与结果；三种剪枝类型齐备；节点数少（说明剪枝有效）。
异常特征：搜索树呈"满二叉树"疯长（节点数随深度指数爆炸）→ 说明 LP 松弛太松（IG 大）、大 M 取值过松或分支策略差，应改进模型或换启发式。

图③ 收敛曲线

好图特征：上界快速下降、下界快速上升，两条线在少量轮次内相遇；上下界之间的带子越收越窄。
异常特征一：上界迟迟不降（LP 松弛太松，剪不掉分支）——典型的"大 M 灾难"；异常特征二：下界长期为 $-\infty$ （一直找不到整数可行解）→ 应先用启发式/取整方案喂一个初始下界。

图④ 取整方案对比

好图特征：能一眼看出 LP 值（不可达到）与整数最优的差距、以及各取整方案的损失。
异常特征：若"四舍五入"恰好可行且等于最优，别高兴太早——这是碰巧（示例 2 即如此），论文中仍应说明"取整方案无最优性保证，本例碰巧一致"。

五、符号说明

符号	含义	示例/单位
$x$	决策变量向量	示例 1： $x = (x_1, x_2)$ ，产量/台
$x_j$	第 $j$ 个决策变量（整数）	$x_2 = 5$ 台
$n$	决策变量个数	示例 1： $n = 2$
$m$	约束个数	示例 1： $m = 2$
$c$	目标系数向量	$c = (5, 8)$ ，万元/台
$A$	约束系数矩阵（ $m \times n$ ）	$A = \begin{bmatrix} 1 & 1 \\ 5 & 9 \end{bmatrix}$
$b$	资源上限向量	$b = (6, 45)$ ，小时/吨
$\mathbb{Z}_{+}$	非负整数集 $\{0,1,2,\dots\}$	$x \in \mathbb{Z}_{+}^n$
$\{0,1\}^n$	0-1 变量取值集合	选址问题：建 = 1，不建 = 0
$z$	目标函数值	$z = 5x_1 + 8x_2$ ，万元
$z_{IP}$	整数规划最优值	示例 1： $z_{IP} = 40$
$z_{LP}$	LP 松弛最优值	示例 1： $z_{LP} = 41.25$
IG	积分间隙（Integrality Gap）	示例 1： $\text{IG} = 3.03\%$
UB	上界（Upper Bound）	max 问题： $UB = z_{LP}$ 或子树松弛值
LB	下界（Lower Bound）	max 问题：当前最优整数解的值
$N$	分支定界搜索节点数	示例 1： $N = 7$
$\lfloor a \rfloor$	向下取整（floor）	$\lfloor 3.75 \rfloor = 3$
$\lceil a \rceil$	向上取整（ceil）	$\lceil 3.75 \rceil = 4$
$\hat{x}$	对 LP 解的取整方案	$\hat{x} = (2,3)$ （floor）
RE	取整方案相对误差	示例 1： $\text{RE} = 15\%$
$T$	求解时间	ms
mip_gap	求解器报告的相对间隙	最优时为 0
MILP	混合整数线性规划	部分变量连续
BnB	分支定界法（Branch and Bound）	本文核心算法
B&C	分支-割平面法（Branch-and-Cut）	BnB + 割平面的现代组合

六、可运行程序（完整代码）

环境要求：Python 3.12，依赖 numpy、scipy、matplotlib（pip install numpy scipy matplotlib）。注意：代码只使用 scipy 自带的 HiGHS 求解器（scipy.optimize.milp 与 scipy.optimize.linprog），不依赖 pulp / cvxpy 等未安装的库。以下所有代码块按顺序拼接保存为 ilp_demo.py，在本文档所在目录运行即可：控制台打印分支定界全过程、第三节列出的全部指标与 milp 对照结果，并在 figures/ 子目录生成 4 张图。若运行环境无图形界面（如服务器），可用 MPLBACKEND=Agg python ilp_demo.py 方式运行（代码保留 plt.show()，Agg 后端下它自动跳过）。

6.1 两个示例问题

示例 1（二维、可图解，专门设计成"LP 松弛为小数、四舍五入踩坑"的典型情形——生产计划）：

$\max \; z = 5x_1 + 8x_2 \quad \text{s.t.} \quad \begin{cases} x_1 + x_2 \le 6 & \text{（装配工时）} \\ 5x_1 + 9x_2 \le 45 & \text{（原料）} \end{cases}, \quad x_1, x_2 \in \mathbb{Z}_{+}$

该问题的"坑"：LP 松弛最优解为 $(2.25, 3.75)$ （ $z = 41.25$ ），不是整数；四舍五入得 $(2,4)$ 违反原料约束（ $46 > 45$ ）；向下取整得 $(2,3)$ 只有 $z = 34$ ；而真正的整数最优解是 $(0,5)$ ， $z = 40$ 。

示例 2（三维、多变量，展示通用流程）：

$\max \; z = 4x_1 + 7x_2 + 3x_3 \quad \text{s.t.} \quad \begin{cases} 3x_1 + 2x_2 + x_3 \le 9 \\ 2x_1 + 3x_2 + 2x_3 \le 10 \end{cases}, \quad x_1, x_2, x_3 \in \mathbb{Z}_{+}$

LP 松弛最优解为 $(0, 10/3, 0)$ （ $z = 70/3 \approx 23.333$ ），整数最优值为 21（有两个最优解： $(0,3,0)$ 与 $(1,2,1)$ ）。

# -*- coding: utf-8 -*-
"""
============================================================
整数规划（Integer Programming）完整示例：
手写分支定界法（scipy linprog 解节点 LP 松弛） + scipy.optimize.milp 对照
------------------------------------------------------------
实例 1（二维，可图解，演示"LP 松弛为小数、四舍五入踩坑"）：
    max z = 5x1 + 8x2
    s.t.   x1 + x2 <= 6      （装配工时，小时）
           5x1 + 9x2 <= 45   （原料，吨）
           x1, x2 ∈ Z+       （台数，非负整数）
    LP 松弛最优 (2.25, 3.75)，z = 41.25 —— 分数，不可执行；
    四舍五入 (2, 4) 违反原料约束（46 > 45）；向下取整 (2, 3) 只有 z = 34；
    真正的整数最优解是 (0, 5)，z = 40 —— 与 LP 最优解相距很远。
实例 2（三维，多变量，展示通用流程）：
    max z = 4x1 + 7x2 + 3x3
    s.t.   3x1 + 2x2 + x3 <= 9
           2x1 + 3x2 + 2x3 <= 10
           x1, x2, x3 ∈ Z+
    LP 松弛最优值 70/3 ≈ 23.333（x2 = 10/3 为分数），整数最优值 21。
输出：控制台打印分支定界全过程、第三节全部指标、milp 对照结果；
      figures/ 目录下生成 4 张图（ilp_lattice / ilp_bnb_tree /
      ilp_bnb_convergence / ilp_rounding）。
依赖：numpy、scipy、matplotlib（不依赖 pulp/cvxpy）
============================================================
"""

# ========== 0. 导入库与全局设置 ==========
import os
import time
import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import linprog, milp, LinearConstraint, Bounds

# ---- matplotlib 中文显示设置（防止图内中文乱码）----
plt.rcParams["font.sans-serif"] = ["PingFang SC", "Arial Unicode MS", "SimHei"]
plt.rcParams["axes.unicode_minus"] = False   # 让负号"-"正常显示

# ---- 图片输出目录（相对当前工作目录的 figures/ 子目录）----
FIG_DIR = "figures"
os.makedirs(FIG_DIR, exist_ok=True)

# ---- 画图配色（固定类别色、色盲友好；全套图保持一致的"角色-颜色"映射）----
C_LP   = "#2a78d6"   # 蓝色 = LP 松弛 / 上界 UB
C_LB   = "#eb6834"   # 橙色 = 下界 LB / 向下取整方案
C_IP   = "#1baf7a"   # 青绿 = 整数最优解
C_BAD  = "#d03b3b"   # 红色 = 不可行（四舍五入踩坑）
C_PINK = "#e87ba4"   # 品红 = 其他整数候选解
C_INK  = "#0b0b0b"   # 主文字颜色
C_INK2 = "#52514e"   # 次要文字颜色
C_GRID = "#e1e0d9"   # 网格线颜色

# ========== 1. 问题建模（两个自包含实例，无外部数据文件） ==========

# ---- 实例 1：二维生产计划（可图解）----
# 决策变量：x1 = 产品甲产量（台），x2 = 产品乙产量（台）
# 目标：总利润 z = 5x1 + 8x2（万元）最大化
# 约束：装配工时 x1 + x2 <= 6（小时）；原料 5x1 + 9x2 <= 45（吨）
c1 = np.array([5.0, 8.0])                       # 目标系数（利润：万元/台）
A1 = np.array([[1.0, 1.0],                      # 装配工时系数（小时/台）
               [5.0, 9.0]])                     # 原料系数（吨/台）
b1 = np.array([6.0, 45.0])                      # 资源上限

# ---- 实例 2：三维生产计划（多变量，展示通用流程）----
c2 = np.array([4.0, 7.0, 3.0])                  # 三种产品的单位利润
A2 = np.array([[3.0, 2.0, 1.0],                 # 资源一消耗系数
               [2.0, 3.0, 2.0]])                # 资源二消耗系数
b2 = np.array([9.0, 10.0])                      # 两种资源上限

# ========== 2. 手写分支定界法（每个节点用 scipy linprog 求解 LP 松弛） ==========

def fmt_x(x):
    """把解向量格式化成 "(2.25, 3.75)" 这类字符串：整数分量显示为整数。"""
    parts = []
    for v in x:
        if abs(v - round(v)) < 1e-6:
            parts.append(str(int(round(v))))
        else:
            parts.append(f"{v:.4g}")
    return "(" + ", ".join(parts) + ")"


def solve_node_lp(c, A, b, extra):
    """求解某个节点的 LP 松弛：max c^T x，s.t. A x <= b、extra 中的分支约束、
    x >= 0（注意：整数约束被"松弛"掉了，这正是 LP 松弛的含义）。

    参数 extra: 分支约束列表，每个元素为 (系数行向量, 右端项, 文字描述)。
    返回 (status, x, z, ub)：
        status = "integer"    —— LP 松弛最优解恰好全为整数（该节点可剪枝）
        status = "fractional" —— LP 松弛最优解含分数分量（需要继续分支）
        status = "infeasible" —— LP 松弛无可行解（该节点可剪枝）
        ub = z = 该节点 LP 松弛最优值（最大化问题中即该节点子树的上界）
    """
    n = len(c)
    if extra:
        # 把分支约束拼到原约束矩阵后面：每条分支约束形如 row·x <= bound
        A_ub = np.vstack([A] + [row[None, :] for row, _, _ in extra])
        b_ub = np.concatenate([b, [bd for _, bd, _ in extra]])
    else:
        A_ub, b_ub = A, b
    # linprog 默认求最小化，最大化问题取负目标系数；method="highs" 用 scipy 自带求解器
    res = linprog(c=-c, A_ub=A_ub, b_ub=b_ub,
                  bounds=[(0, None)] * n, method="highs")
    if res.status == 2:                          # HiGHS 状态码 2 = 不可行
        return "infeasible", None, -np.inf, -np.inf
    if res.status != 0:                          # 其他异常状态（本例正常不会出现）
        return "failed", None, -np.inf, -np.inf
    x = np.maximum(res.x, 0.0)                   # 把 -1e-12 之类的小负数钳为 0
    z = float(c @ x)
    # 整数判定：所有分量与最近整数的距离都小于容差（LP 数值解有舍入误差）
    if np.all(np.abs(x - np.round(x)) < 1e-6):
        return "integer", np.round(x), z, z
    return "fractional", x, z, z


def branch_and_bound(c, A, b, tol=1e-6):
    """手写分支定界法（求解最大化整数规划），打印全过程。

    返回 (最优解 x*, 最优值 z*, 节点列表, 上下界收敛记录)。
    · 分支规则：选离整数最远（小数部分最大）的变量，并列时取下标较大者；
    · 节点选择：最佳优先——每次展开上界 UB 最大的节点；
    · 剪枝：不可行剪枝 / 定界剪枝（UB <= LB）/ 整数解剪枝。
    """
    n = len(c)
    print("=" * 72)
    print("【手写分支定界法】求解最大化整数规划")
    print(f"  目标系数 c = {c}")
    print(f"  约束矩阵 A = {A.tolist()}")
    print(f"  右端项 b = {b}，整数约束 x ∈ Z+^{n}")
    print("-" * 72)

    nodes, open_nodes = [], []                   # 全部节点 / 待展开队列
    lb, incumbent = -np.inf, None                # 全局下界 / 当前最优整数解
    nid = [0]                                    # 节点编号计数器

    def make_node(parent, extra, branch_desc):
        """创建节点：求解其 LP 松弛并登记、打印。"""
        status, x, z, ub = solve_node_lp(c, A, b, extra)
        node = dict(id=nid[0], parent=parent, extra=extra,
                    branch=branch_desc, status=status, x=x, z=z, ub=ub)
        nid[0] += 1
        nodes.append(node)
        pid = "根" if parent is None else str(parent)
        print(f"[节点 {node['id']}] 父节点 {pid}，分支条件: {branch_desc}")
        if status == "infeasible":
            print("    LP 松弛无可行解")
        elif status == "integer":
            print(f"    LP 松弛解: x = {fmt_x(x)}（恰好为整数），z = {z:.4g}")
        else:
            print(f"    LP 松弛解: x = {fmt_x(x)}，上界 UB = {z:.4g}（含分数分量）")
        return node

    # ---- 根节点：不带任何分支约束的 LP 松弛 ----
    root = make_node(None, [], "根节点（无分支约束）")
    if root["status"] == "integer":
        print("根节点 LP 松弛解即为整数解 → 直接得到全局最优，无需分支！")
        return root["x"], root["z"], nodes, []
    if root["status"] != "fractional":
        print("根节点 LP 松弛不可行 → 原问题无可行解")
        return None, None, nodes, []
    open_nodes.append(root)
    print(f"  初始状态：全局上界 UB = {root['ub']:.4g}，下界 LB = -∞（尚无整数可行解）")

    # ---- 上下界收敛记录（第 0 轮 = 根节点刚求解完）----
    convergence = [dict(iter=0, ub=root["ub"], lb=-np.inf)]
    iteration = 0

    # ---- 主循环 ----
    while open_nodes:
        iteration += 1
        # ① 选择：最佳优先——展开上界最大的节点（最可能藏着最优解）
        open_nodes.sort(key=lambda nd: (-nd["ub"], nd["id"]))
        node = open_nodes.pop(0)
        # ② 定界：该节点子树的最好情况都不如当前解 → 整支剪掉
        if node["ub"] <= lb + tol:
            node["pruned"] = "bound"
            node["conclusion"] = f"UB = {node['ub']:.4g} <= LB = {lb:.4g}，剪枝（定界）"
            print(f"[展开节点 {node['id']}] UB = {node['ub']:.4g} <= LB = {lb:.4g} "
                  f"→ 剪枝（定界）")
            continue
        # ③ 分支：选小数部分最大的变量（离整数最远），并列时取下标较大者
        xr = np.round(node["x"], 6)
        j = max(range(n), key=lambda jj: (abs(xr[jj] - round(xr[jj])), jj))
        xj = xr[j]
        lo, hi = int(np.floor(xj)), int(np.ceil(xj))
        node["conclusion"] = f"UB = {node['ub']:.4g} → 分支 x{j + 1}"
        print(f"[展开节点 {node['id']}] LP 解 x = {fmt_x(node['x'])}，UB = {node['ub']:.4g}")
        print(f"    分支变量 x{j + 1} = {xj:.4g}（小数部分最大）"
              f"→ 两支: x{j + 1} <= {lo} 与 x{j + 1} >= {hi}")
        # ④ 生成两个子节点，立即求解并判定剪枝
        for sign, k in (("<=", lo), (">=", hi)):
            row = np.zeros(n)
            if sign == "<=":                      # x_j <= k 直接写成 row·x <= k
                row[j], rhs = 1.0, float(k)
            else:                                 # x_j >= k 需写成 -x_j <= -k（约束形式统一为 <=）
                row[j], rhs = -1.0, -float(k)
            desc = f"x{j + 1} {sign} {k}"
            child = make_node(node["id"],
                              node["extra"] + [(row, rhs, desc)], desc)
            if child["status"] == "infeasible":
                child["pruned"] = "infeasible"
                child["conclusion"] = "LP 松弛无可行解，剪枝（不可行）"
                print("      → 剪枝（不可行：LP 松弛无可行解）")
            elif child["status"] == "integer":
                if child["z"] > lb + tol:        # 比当前最优更好 → 更新下界
                    lb, incumbent = child["z"], child
                    child["pruned"] = "integrality"
                    child["conclusion"] = (f"z = {child['z']:.4g} → 更新 LB = "
                                           f"{lb:.4g}，剪枝（整数解）")
                    print(f"      → 整数解 z = {child['z']:.4g} 优于当前下界："
                          f"更新 LB = {lb:.4g}，候选解 x = {fmt_x(child['x'])}；"
                          f"剪枝（整数解）")
                else:                            # 不优于当前最优 → 定界剪枝
                    child["pruned"] = "bound"
                    child["conclusion"] = (f"z = {child['z']:.4g} <= LB = {lb:.4g}，"
                                           f"剪枝（定界）")
                    print(f"      → 整数解 z = {child['z']:.4g} <= 当前 LB = "
                          f"{lb:.4g}：不更新；剪枝（定界）")
            else:                                # 分数解 → 加入待展开队列
                child["conclusion"] = f"UB = {child['ub']:.4g} → 待展开"
                open_nodes.append(child)
                print(f"      → 分数解，加入待展开队列（UB = {child['ub']:.4g}）")
        # ⑤ 记录本轮之后的全局上下界
        global_ub = max((nd["ub"] for nd in open_nodes), default=lb)
        convergence.append(dict(iter=iteration, ub=global_ub, lb=lb))
        print(f"    [收敛] 第 {iteration} 轮后：全局上界 UB = {global_ub:.4g}，"
              f"下界 LB = {lb:.4g}")
        if global_ub <= lb + tol:                # 上下界相遇 → 已找到全局最优
            print("    → 上界与下界相遇：剩余节点不可能更好，停止搜索！")
            break

    # ---- 汇总 ----
    print("-" * 72)
    print("【分支定界结果】")
    print(f"  最优解 x* = {fmt_x(incumbent['x'])}")
    print(f"  最优值 z* = {incumbent['z']:.4g}")
    n_pruned = sum(1 for nd in nodes if "pruned" in nd)
    print(f"  搜索节点总数 = {len(nodes)}（其中展开 {iteration} 次、剪枝 {n_pruned} 次）")
    for k, name in (("integrality", "整数解"), ("bound", "定界"), ("infeasible", "不可行")):
        cnt = sum(1 for nd in nodes if nd.get("pruned") == k)
        print(f"    剪枝-{name}: {cnt} 次")
    return incumbent["x"], incumbent["z"], nodes, convergence

# ========== 3. 运行手写分支定界（实例 1） ==========
t_start = time.perf_counter()
x_bnb, z_bnb, nodes_bnb, conv_bnb = branch_and_bound(c1, A1, b1)
t_bnb = time.perf_counter() - t_start

# ========== 4. scipy.optimize.milp 对照求解（HiGHS 求解器） ==========
print("=" * 72)
print("【scipy.optimize.milp 对照】（HiGHS 求解器，integrality=1 表示整数变量）")


def solve_milp(c, A, b):
    """调用 scipy.optimize.milp 求解 max c^T x, s.t. A x <= b, x 全整数且 >= 0。"""
    res = milp(c=-c,                               # milp 同样是求最小化，最大化取负
               constraints=LinearConstraint(A, -np.inf, b),
               integrality=np.ones(len(c)),       # 1 = 整数变量，0 = 连续变量
               bounds=Bounds(0, np.inf))          # 非负
    return res


# ---- 实例 1 ----
t_start = time.perf_counter()
res_m1 = solve_milp(c1, A1, b1)
t_m1 = time.perf_counter() - t_start
x_m1 = np.round(res_m1.x, 6)
z_m1 = float(c1 @ x_m1)
print(f"  实例 1: x* = {fmt_x(x_m1)}，z* = {z_m1:.4g}，success = {res_m1.success}")

# ---- 实例 2 ----
t_start = time.perf_counter()
res_m2 = solve_milp(c2, A2, b2)
t_m2 = time.perf_counter() - t_start
x_m2 = np.round(res_m2.x, 6)
z_m2 = float(c2 @ x_m2)
print(f"  实例 2: x* = {fmt_x(x_m2)}，z* = {z_m2:.4g}，success = {res_m2.success}")
# 实例 2 有两个最优解 (0,3,0) 与 (1,2,1)，目标值均为 21：检查求解器返回的是哪一个
is_a = np.allclose(x_m2, [0, 3, 0])
is_b = np.allclose(x_m2, [1, 2, 1])
print(f"    最优解验证: 与 (0,3,0) 一致 = {is_a}，与 (1,2,1) 一致 = {is_b}"
      f"（两者目标值均为 21，说明整数规划可以有多个最优解）")

# ---- 一致性对比：手写分支定界 vs milp（实例 1）----
same_x = np.allclose(x_bnb, x_m1)
same_z = np.isclose(z_bnb, z_m1, atol=1e-6)
print("-" * 72)
print("【一致性对比】（实例 1：手写分支定界 vs scipy.milp）")
print(f"  手写分支定界: x* = {fmt_x(x_bnb)}，z* = {z_bnb:.4g}")
print(f"  scipy.milp  : x* = {fmt_x(x_m1)}，z* = {z_m1:.4g}")
print(f"  最优解一致: {same_x}，最优值一致: {same_z}")

# ========== 5. 指标计算与汇总打印（对应第三节的全部指标） ==========
# ---- 5.1 指标：LP 松弛最优值与积分间隙（实例 1）----
print("=" * 72)
print("【指标 1：LP 松弛与积分间隙】（实例 1）")
res_lp1 = linprog(c=-c1, A_ub=A1, b_ub=b1,
                  bounds=[(0, None)] * 2, method="highs")
x_lp1 = np.maximum(res_lp1.x, 0.0)
z_lp1 = float(c1 @ x_lp1)
print(f"  LP 松弛最优解 x_LP = ({x_lp1[0]:.4g}, {x_lp1[1]:.4g})")
print(f"  LP 松弛最优值 z_LP = {z_lp1:.4g}")
print(f"  整数最优值   z_IP = {z_bnb:.4g}")
gap1 = abs(z_lp1 - z_bnb) / abs(z_lp1) * 100
print(f"  积分间隙 IG = |z_LP - z_IP| / |z_LP| = ({z_lp1:.4g} - {z_bnb:.4g}) "
      f"/ {z_lp1:.4g} = {gap1:.2f}%")

# ---- 5.2 指标：LP 松弛与积分间隙（实例 2）----
print("【指标 1：LP 松弛与积分间隙】（实例 2）")
res_lp2 = linprog(c=-c2, A_ub=A2, b_ub=b2,
                  bounds=[(0, None)] * 3, method="highs")
x_lp2 = np.maximum(res_lp2.x, 0.0)
z_lp2 = float(c2 @ x_lp2)
print(f"  LP 松弛最优解 x_LP = ({x_lp2[0]:.4g}, {x_lp2[1]:.4g}, {x_lp2[2]:.4g})")
print(f"  LP 松弛最优值 z_LP = {z_lp2:.4f}")
print(f"  整数最优值   z_IP = {z_m2:.4g}")
gap2 = abs(z_lp2 - z_m2) / abs(z_lp2) * 100
print(f"  积分间隙 IG = ({z_lp2:.4f} - {z_m2:.4g}) / {z_lp2:.4f} = {gap2:.2f}%")

# ---- 5.3 指标：四舍五入方案 vs 整数最优解（实例 1）----
print("-" * 72)
print("【指标 2：四舍五入方案 vs 整数最优解】（实例 1）")
x_round1 = np.round(x_lp1).astype(int)            # 四舍五入 → (2, 4)
feas_r1 = np.all(A1 @ x_round1 <= b1 + 1e-9)
print(f"  四舍五入: x_LP ({x_lp1[0]:.4g}, {x_lp1[1]:.4g}) → ({x_round1[0]}, "
      f"{x_round1[1]})")
print(f"    约束检验 A·x = {A1 @ x_round1} <= b = {b1}？→ 可行: {feas_r1}")
x_floor1 = np.floor(x_lp1).astype(int)            # 向下取整 → (2, 3)
feas_f1 = np.all(A1 @ x_floor1 <= b1 + 1e-9)
z_floor1 = float(c1 @ x_floor1)
re1 = abs(z_floor1 - z_bnb) / abs(z_bnb) * 100
print(f"  向下取整: → ({x_floor1[0]}, {x_floor1[1]})，可行: {feas_f1}，"
      f"目标值 z = {z_floor1:.4g}")
print(f"    相对误差 RE = |z_floor - z_IP| / |z_IP| = |{z_floor1:.4g} - "
      f"{z_bnb:.4g}| / {z_bnb:.4g} = {re1:.2f}%")
x_ceil1 = np.ceil(x_lp1).astype(int)              # 向上取整 → (3, 4)
feas_c1 = np.all(A1 @ x_ceil1 <= b1 + 1e-9)
print(f"  向上取整: → ({x_ceil1[0]}, {x_ceil1[1]})，可行: {feas_c1}")

# ---- 5.4 指标：四舍五入方案 vs 整数最优解（实例 2）----
print("【指标 2：四舍五入方案 vs 整数最优解】（实例 2）")
x_floor2 = np.floor(x_lp2).astype(int)
feas_f2 = np.all(A2 @ x_floor2 <= b2 + 1e-9)
z_floor2 = float(c2 @ x_floor2)
re2 = abs(z_floor2 - z_m2) / abs(z_m2) * 100
print(f"  LP 解 ({x_lp2[0]:.4g}, {x_lp2[1]:.4g}, {x_lp2[2]:.4g}) 向下取整 "
      f"→ ({x_floor2[0]}, {x_floor2[1]}, {x_floor2[2]})，可行: {feas_f2}，"
      f"z = {z_floor2:.4g}")
print(f"    相对误差 RE = {re2:.2f}%（本例取整恰好得到最优解——四舍五入有时"
      f"碰巧，有时全错，不能当作通用方法）")

# ---- 5.5 指标：分支定界搜索过程与求解时间 ----
print("-" * 72)
print("【指标 3：分支定界搜索过程】（实例 1）")
print(f"  搜索节点总数: {len(nodes_bnb)}")
print("  上下界收敛过程（每轮展开一个节点后记录）:")
for rec in conv_bnb:
    lb_s = "-∞" if rec["lb"] == -np.inf else f"{rec['lb']:.4g}"
    print(f"    第 {rec['iter']} 轮: UB = {rec['ub']:.4g}，LB = {lb_s}")

print("【指标 4：求解时间】")
print(f"  手写分支定界（实例 1）: {t_bnb * 1e3:.2f} ms")
print(f"  scipy.milp（实例 1）   : {t_m1 * 1e3:.2f} ms")
print(f"  scipy.milp（实例 2）   : {t_m2 * 1e3:.2f} ms")
print(f"  milp 返回的求解器相对间隙 mip_gap = {res_m1.mip_gap:.3g}")

# ========== 6. 可视化：4 张图 ==========
# ---- 图 ① LP 松弛可行域 + 整数格点 + 两类最优解 ----
fig, ax = plt.subplots(figsize=(8.4, 7.0))
# 可行域多边形（顶点依次为 (0,0)、(6,0)、(2.25,3.75)、(0,5)）
poly_x = [0, 6, 2.25, 0]
poly_y = [0, 0, 3.75, 5]
ax.fill(poly_x, poly_y, color=C_LP, alpha=0.10, zorder=1,
        label="LP 松弛可行域（连续凸多边形）")
ax.plot(poly_x + [0], poly_y + [0], color=C_LP, lw=2.2, zorder=2)
# 两条约束直线（画出整条线，多边形边界内的部分才是"起作用的"约束）
ax.plot([0, 6], [6, 0], color=C_INK2, lw=1.1, ls="--", zorder=2)
ax.plot([0, 9], [5, 0], color=C_INK2, lw=1.1, ls="--", zorder=2)
ax.text(4.55, 2.0, "x₁ + x₂ = 6（装配工时）", rotation=-45, fontsize=9,
        color=C_INK2, zorder=6, ha="center",
        bbox=dict(fc="white", ec="none", alpha=0.85, pad=1))
ax.text(5.6, 2.5, "5x₁ + 9x₂ = 45（原料）", rotation=-29, fontsize=9,
        color=C_INK2, zorder=6, ha="center",
        bbox=dict(fc="white", ec="none", alpha=0.85, pad=1))
# 整数格点（0 <= x1 <= 6, 0 <= x2 <= 5 的整数点）：深色 = 可行，浅灰 = 不可行
feas_pts, infeas_pts = [], []
for i in range(7):
    for j in range(6):
        if i + j <= 6 + 1e-9 and 5 * i + 9 * j <= 45 + 1e-9:
            feas_pts.append((i, j))
        else:
            infeas_pts.append((i, j))
feas_pts = np.array(feas_pts)
infeas_pts = np.array(infeas_pts)
ax.scatter(feas_pts[:, 0], feas_pts[:, 1], s=22, color=C_INK, zorder=3,
           label="可行整数点（整数规划的候选方案）")
ax.scatter(infeas_pts[:, 0], infeas_pts[:, 1], s=16, color="#d9d7d0", zorder=3,
           label="不可行整数点")
# 关键解标注
ax.scatter([x_lp1[0]], [x_lp1[1]], marker="*", s=280, color=C_LP,
           edgecolor="white", linewidth=0.8, zorder=5, label="LP 松弛最优解")
ax.annotate("LP 松弛最优解\n(2.25, 3.75)   z = 41.25\nx₂ 不是整数 → 不可执行",
            xy=(x_lp1[0], x_lp1[1]), xytext=(2.0, 4.9), fontsize=9,
            color=C_INK, ha="center", zorder=6,
            arrowprops=dict(arrowstyle="->", color=C_INK2, lw=1.0))
ax.scatter([0], [5], s=170, color=C_IP, edgecolor="white", linewidth=1.2,
           zorder=5, label="整数最优解")
ax.annotate("整数最优解\n(0, 5)   z = 40\n（与 LP 松弛解相距很远！）",
            xy=(0, 5), xytext=(2.2, 5.55), fontsize=9, color=C_INK,
            ha="center", zorder=6,
            arrowprops=dict(arrowstyle="->", color=C_INK2, lw=1.0))
ax.scatter([2], [4], marker="x", s=130, color=C_BAD, linewidth=2.8, zorder=5,
           label="四舍五入 (2, 4)：不可行")
ax.annotate("四舍五入 → (2, 4)\n违反原料约束：5×2 + 9×4 = 46 > 45",
            xy=(2, 4), xytext=(4.3, 4.0), fontsize=9, color=C_BAD,
            ha="center", zorder=6,
            arrowprops=dict(arrowstyle="->", color=C_BAD, lw=1.0))
ax.scatter([2], [3], s=100, color=C_LB, edgecolor="white", linewidth=1.0,
           zorder=5, label="向下取整 (2, 3)：可行但 z = 34")
ax.annotate("向下取整 → (2, 3)\n可行，但 z = 34\n比最优 40 低 15%",
            xy=(2, 3), xytext=(3.6, 0.6), fontsize=9, color=C_INK,
            ha="center", zorder=6,
            arrowprops=dict(arrowstyle="->", color=C_INK2, lw=1.0))
ax.scatter([3], [3], s=100, color=C_PINK, edgecolor="white", linewidth=1.0,
           zorder=5, label="可行整数点 (3, 3)：z = 39，非最优")
ax.annotate("(3, 3) 也是可行整数点\nz = 39 < 40（非最优）",
            xy=(3, 3), xytext=(4.5, 0.7), fontsize=9, color=C_INK2,
            ha="center", zorder=6,
            arrowprops=dict(arrowstyle="->", color=C_INK2, lw=1.0))
ax.set_xlabel("x₁（甲产品台数）", fontsize=11)
ax.set_ylabel("x₂（乙产品台数）", fontsize=11)
ax.set_title("图 ① LP 松弛可行域、整数格点与两类最优解", fontsize=12)
ax.set_xlim(-0.5, 7.6)
ax.set_ylim(-0.5, 6.3)
ax.set_xticks(range(0, 8))
ax.set_yticks(range(0, 7))
ax.grid(True, color=C_GRID, lw=0.8, zorder=0)
for spine in ("top", "right"):
    ax.spines[spine].set_visible(False)
ax.legend(fontsize=8, loc="lower left", framealpha=0.95)
fig.tight_layout()
fig.savefig(os.path.join(FIG_DIR, "ilp_lattice.png"), dpi=150)
print("图 ① 已保存: figures/ilp_lattice.png")

# ---- 图 ② 分支定界搜索树 ----
fig, ax = plt.subplots(figsize=(9.5, 6.8))
# 手工布局：节点 id → (x, y)（y 表示深度，根在最上）
pos = {0: (0.0, 0.0), 1: (-3.6, -1.6), 2: (3.4, -1.6),
       3: (1.6, -3.2), 4: (6.2, -3.2),
       5: (-0.6, -4.8), 6: (3.4, -4.8)}


def box_style(nd):
    """按节点结局给盒子配色：整数解(更新下界)/定界剪枝/不可行/被展开的分支节点。"""
    if nd.get("pruned") == "integrality":
        return dict(fc="#e9f7f0", ec=C_IP, lw=1.8)
    if nd.get("pruned") == "bound":
        return dict(fc="#f4f3f0", ec="#b9b7b0", lw=1.2)
    if nd.get("pruned") == "infeasible":
        return dict(fc="#fdecea", ec=C_BAD, lw=1.5)
    return dict(fc="white", ec=C_LP, lw=1.5)      # 被展开、产生子节点的节点


# 先画边（父节点 → 子节点），边上标注分支方向
for nd in nodes_bnb:
    if nd["parent"] is not None:
        p = pos[nd["parent"]]
        ch = pos[nd["id"]]
        ax.annotate("", xy=ch, xytext=p,
                    arrowprops=dict(arrowstyle="-", color=C_INK2, lw=1.1))
        mx, my = (p[0] + ch[0]) / 2, (p[1] + ch[1]) / 2
        ax.text(mx + 0.18, my + 0.05, nd["branch"], fontsize=9, color=C_INK,
                ha="center", va="center",
                bbox=dict(fc="white", ec=C_GRID, lw=0.8, pad=1.5))
# 再画节点盒子（每条一行：节点号与分支条件 / LP 松弛解 / 结论）
for nd in nodes_bnb:
    x, y = pos[nd["id"]]
    head = (f"节点 {nd['id']}（根）" if nd["parent"] is None
            else f"节点 {nd['id']}: {nd['branch']}")
    if nd["status"] == "infeasible":
        lines = [head, "LP 松弛: 无可行解", nd["conclusion"]]
    else:
        lines = [head, f"LP 松弛: x = {fmt_x(nd['x'])}", nd["conclusion"]]
    ax.text(x, y, "\n".join(lines), fontsize=7.8, color=C_INK, ha="center",
            va="center", zorder=5,
            bbox=dict(boxstyle="round,pad=0.42", **box_style(nd)))
# 最终结论标注
ax.text(0.6, -6.15,
        "最优解 x* = (0, 5)，z* = 40（节点 6 更新下界后，全局上界 = 下界 = 40，停止搜索）",
        fontsize=10, color=C_INK, ha="center")
ax.set_title("图 ② 分支定界搜索树（共 7 个节点：展开 3 次、剪枝 4 次）", fontsize=12)
ax.set_xlim(-5.6, 8.2)
ax.set_ylim(-6.7, 0.55)
ax.axis("off")
fig.tight_layout()
fig.savefig(os.path.join(FIG_DIR, "ilp_bnb_tree.png"), dpi=150)
print("图 ② 已保存: figures/ilp_bnb_tree.png")

# ---- 图 ③ 上界/下界收敛曲线 ----
fig, ax = plt.subplots(figsize=(7.6, 5.2))
iters = [r["iter"] for r in conv_bnb]
ubs = [r["ub"] for r in conv_bnb]
lbs = [r["lb"] if r["lb"] != -np.inf else np.nan for r in conv_bnb]
ax.step(iters, ubs, where="post", color=C_LP, lw=2.0, marker="o", ms=7,
        label="上界 UB（未剪枝节点的 LP 松弛最优值）")
ax.step(iters[1:], lbs[1:], where="post", color=C_LB, lw=2.0, marker="o", ms=7,
        label="下界 LB（当前最优整数解的目标值）")
# 两条线之间的浅色带 = 最优值还可能存在的区间（下界初值 -∞ 画到底边）
lb_full = [34.5, 39, 39, 40]
ax.fill_between(iters, ubs, lb_full, step="post", color=C_LP, alpha=0.07)
ax.annotate("初始 LB = -∞（尚无整数可行解）", xy=(0, 34.6), xytext=(0.05, 35.0),
            fontsize=9, color=C_INK2)
ax.annotate("第 1 轮：节点 1 给出整数解 (3,3)\n下界升到 39",
            xy=(0.55, 39), xytext=(0.15, 40.35), fontsize=9, color=C_INK2,
            arrowprops=dict(arrowstyle="->", color=C_INK2, lw=1.0))
ax.annotate("最终 UB = LB = 40\n→ 找到全局最优解 (0,5)",
            xy=(2.9, 40), xytext=(1.5, 40.55), fontsize=9, color=C_INK,
            arrowprops=dict(arrowstyle="->", color=C_INK2, lw=1.0))
ax.set_xticks(iters)
ax.set_xlabel("分支定界迭代轮次（每轮展开一个节点）", fontsize=11)
ax.set_ylabel("目标值 z（最大化）", fontsize=11)
ax.set_title("图 ③ 分支定界上下界收敛过程（实例 1）", fontsize=12)
ax.set_ylim(34.5, 42.4)
ax.grid(True, color=C_GRID, lw=0.8, zorder=0)
for spine in ("top", "right"):
    ax.spines[spine].set_visible(False)
ax.legend(fontsize=9, loc="center right")
fig.tight_layout()
fig.savefig(os.path.join(FIG_DIR, "ilp_bnb_convergence.png"), dpi=150)
print("图 ③ 已保存: figures/ilp_bnb_convergence.png")

# ---- 图 ④ 四舍五入 vs 整数最优对比 ----
fig, ax = plt.subplots(figsize=(8.2, 4.8))
names = ["LP 松弛解 (2.25, 3.75)", "整数最优解 (0, 5)", "向下取整 (2, 3)",
         "四舍五入 (2, 4)"]
vals = [41.25, 40, 34, 0]
colors = [C_LP, C_IP, C_LB, C_BAD]
y = np.arange(len(names))[::-1]
ax.barh(y, vals, height=0.55, color=colors)
for yi, vi in zip(y, vals):                       # 数值标签用文字色，不用系列色
    if vi > 0:
        ax.text(vi + 0.6, yi, f"{vi:.4g}", va="center", fontsize=10, color=C_INK)
ax.text(0.6, y[-1], "不可行：5×2 + 9×4 = 46 > 45", va="center", fontsize=9.5,
        color=C_BAD)
ax.annotate("积分间隙\n41.25 − 40 = 1.25（3.03%）", xy=(40.6, 0.62),
            xytext=(43.2, 0.85), fontsize=9, color=C_INK2,
            arrowprops=dict(arrowstyle="->", color=C_INK2, lw=1.0))
ax.annotate("向下取整比最优低 15%", xy=(34, 0.72), xytext=(37.6, 0.9),
            fontsize=9, color=C_INK2,
            arrowprops=dict(arrowstyle="->", color=C_INK2, lw=1.0))
ax.set_yticks(y)
ax.set_yticklabels(names, fontsize=10)
ax.set_xlabel("目标值 z（利润，万元）", fontsize=11)
ax.set_title("图 ④ LP 松弛 / 整数最优 / 四舍五入方案对比", fontsize=12)
ax.set_xlim(0, 48)
ax.grid(True, axis="x", color=C_GRID, lw=0.8, zorder=0)
for spine in ("top", "right"):
    ax.spines[spine].set_visible(False)
fig.tight_layout()
fig.savefig(os.path.join(FIG_DIR, "ilp_rounding.png"), dpi=150)
print("图 ④ 已保存: figures/ilp_rounding.png")

plt.show()                                        # 弹窗显示 4 张图（Agg 后端下自动跳过）

print("=" * 72)
print("4 张图已保存到 figures/ 目录：")
for f in ("ilp_lattice.png", "ilp_bnb_tree.png", "ilp_bnb_convergence.png",
          "ilp_rounding.png"):
    print(f"  {os.path.join(FIG_DIR, f)}")

七、结果解读与注意事项

7.1 运行输出解读（以第六节两个示例为例）

运行 ilp_demo.py，控制台输出（关键部分）如下（求解时间为毫秒级，随机器略有波动）：

========================================================================
【手写分支定界法】求解最大化整数规划
  目标系数 c = [5. 8.]
  约束矩阵 A = [[1.0, 1.0], [5.0, 9.0]]
  右端项 b = [ 6. 45.]，整数约束 x ∈ Z+^2
------------------------------------------------------------------------
[节点 0] 父节点 根，分支条件: 根节点（无分支约束）
    LP 松弛解: x = (2.25, 3.75)，上界 UB = 41.25（含分数分量）
  初始状态：全局上界 UB = 41.25，下界 LB = -∞（尚无整数可行解）
[展开节点 0] LP 解 x = (2.25, 3.75)，UB = 41.25
    分支变量 x2 = 3.75（小数部分最大）→ 两支: x2 <= 3 与 x2 >= 4
[节点 1] 父节点 0，分支条件: x2 <= 3
    LP 松弛解: x = (3, 3)（恰好为整数），z = 39
      → 整数解 z = 39 优于当前下界：更新 LB = 39，候选解 x = (3, 3)；剪枝（整数解）
[节点 2] 父节点 0，分支条件: x2 >= 4
    LP 松弛解: x = (1.8, 4)，上界 UB = 41（含分数分量）
      → 分数解，加入待展开队列（UB = 41）
    [收敛] 第 1 轮后：全局上界 UB = 41，下界 LB = 39
[展开节点 2] LP 解 x = (1.8, 4)，UB = 41
    分支变量 x1 = 1.8（小数部分最大）→ 两支: x1 <= 1 与 x1 >= 2
[节点 3] 父节点 2，分支条件: x1 <= 1
    LP 松弛解: x = (1, 4.444)，上界 UB = 40.56（含分数分量）
      → 分数解，加入待展开队列（UB = 40.56）
[节点 4] 父节点 2，分支条件: x1 >= 2
    LP 松弛无可行解
      → 剪枝（不可行：LP 松弛无可行解）
    [收敛] 第 2 轮后：全局上界 UB = 40.56，下界 LB = 39
[展开节点 3] LP 解 x = (1, 4.444)，UB = 40.56
    分支变量 x2 = 4.444（小数部分最大）→ 两支: x2 <= 4 与 x2 >= 5
[节点 5] 父节点 3，分支条件: x2 <= 4
    LP 松弛解: x = (1, 4)（恰好为整数），z = 37
      → 整数解 z = 37 <= 当前 LB = 39：不更新；剪枝（定界）
[节点 6] 父节点 3，分支条件: x2 >= 5
    LP 松弛解: x = (0, 5)（恰好为整数），z = 40
      → 整数解 z = 40 优于当前下界：更新 LB = 40，候选解 x = (0, 5)；剪枝（整数解）
    [收敛] 第 3 轮后：全局上界 UB = 40，下界 LB = 40
    → 上界与下界相遇：剩余节点不可能更好，停止搜索！
------------------------------------------------------------------------
【分支定界结果】
  最优解 x* = (0, 5)
  最优值 z* = 40
  搜索节点总数 = 7（其中展开 3 次、剪枝 4 次）
    剪枝-整数解: 2 次
    剪枝-定界: 1 次
    剪枝-不可行: 1 次
========================================================================
【scipy.optimize.milp 对照】（HiGHS 求解器，integrality=1 表示整数变量）
  实例 1: x* = (0, 5)，z* = 40，success = True
  实例 2: x* = (0, 3, 0)，z* = 21，success = True
    最优解验证: 与 (0,3,0) 一致 = True，与 (1,2,1) 一致 = False（两者目标值均为 21，说明整数规划可以有多个最优解）
------------------------------------------------------------------------
【一致性对比】（实例 1：手写分支定界 vs scipy.milp）
  手写分支定界: x* = (0, 5)，z* = 40
  scipy.milp  : x* = (0, 5)，z* = 40
  最优解一致: True，最优值一致: True
========================================================================
【指标 1：LP 松弛与积分间隙】（实例 1）
  LP 松弛最优解 x_LP = (2.25, 3.75)
  LP 松弛最优值 z_LP = 41.25
  整数最优值   z_IP = 40
  积分间隙 IG = |z_LP - z_IP| / |z_LP| = (41.25 - 40) / 41.25 = 3.03%
【指标 1：LP 松弛与积分间隙】（实例 2）
  LP 松弛最优解 x_LP = (0, 3.333, 0)
  LP 松弛最优值 z_LP = 23.3333
  整数最优值   z_IP = 21
  积分间隙 IG = (23.3333 - 21) / 23.3333 = 10.00%
------------------------------------------------------------------------
【指标 2：四舍五入方案 vs 整数最优解】（实例 1）
  四舍五入: x_LP (2.25, 3.75) → (2, 4)
    约束检验 A·x = [ 6 46] <= b = [ 6. 45.]？→ 可行: False
  向下取整: → (2, 3)，可行: True，目标值 z = 34
    相对误差 RE = |z_floor - z_IP| / |z_IP| = |34 - 40| / 40 = 15.00%
  向上取整: → (3, 4)，可行: False
【指标 2：四舍五入方案 vs 整数最优解】（实例 2）
  LP 解 (0, 3.333, 0) 向下取整 → (0, 3, 0)，可行: True，z = 21
    相对误差 RE = 0.00%（本例取整恰好得到最优解——四舍五入有时碰巧，有时全错，不能当作通用方法）
------------------------------------------------------------------------
【指标 3：分支定界搜索过程】（实例 1）
  搜索节点总数: 7
  上下界收敛过程（每轮展开一个节点后记录）:
    第 0 轮: UB = 41.25，LB = -∞
    第 1 轮: UB = 41，LB = 39
    第 2 轮: UB = 40.56，LB = 39
    第 3 轮: UB = 40，LB = 40
【指标 4：求解时间】
  手写分支定界（实例 1）: 5.21 ms
  scipy.milp（实例 1）   : 2.34 ms
  scipy.milp（实例 2）   : 2.15 ms
  milp 返回的求解器相对间隙 mip_gap = 0

逐项解读（实例 1）：

根节点 LP 松弛解 $(2.25, 3.75)$ ， $z = 41.25$ ：生产 2.25 台甲、3.75 台乙"在纸面上"利润最高，但2.25 台设备无法执行——这就是整数规划的出发点。41.25 成为整个搜索的初始上界。
节点 1 剪枝（整数解）：分支 $x_2 \le 3$ 后 LP 解恰好是整数 $(3,3)$ ，立即得到一个可行的整数方案（下界 $LB = 39$ ）并剪掉该分支——因为再往下分支只会更差。
节点 4 剪枝（不可行）： $x_2 \ge 4$ 且 $x_1 \ge 2$ 时原料至少需要 $5 \times 2 + 9 \times 4 = 46 > 45$ 吨，整支无望。
节点 5 剪枝（定界）： $(1,4)$ 是整数解，但 $z = 37 \le LB = 39$ ，不如已有的 $(3,3)$ ，整支剪掉。
节点 6 更新下界： $(0,5)$ 给出 $z = 40 > 39$ ，取代 $(3,3)$ 成为新的最优候选。随后待展开队列清空， $UB = LB = 40$ ，最优性得证—— $(0,5)$ 不是"碰巧找到的好解"，而是有证明的全局最优。
最优解 $(0,5)$ 与 LP 最优解 $(2.25, 3.75)$ 相距很远：整数约束把最优解"逼"到了可行域的另一个角落。若你只盯着 LP 解做取整， $(2,4)$ 违反原料约束、 $(3,4)$ 违反工时约束、 $(2,3)$ 只到 34——三种常见取整全部失败，而真正的答案 40 需要系统搜索才能找到。这正是整数规划必须用专门算法的原因。
积分间隙 3.03%：松弛只高估 3%，非常紧致，因此分支定界只用 7 个节点就完成了证明。
手写 BnB 与 scipy.milp 结果一致： $(0,5)$ 、 $z=40$ ，验证了手写实现的正确性；milp 的 mip_gap = 0 表示求解器也证明了最优性。
实例 2：LP 松弛 $(0, 3.333, 0)$ （生产 3.33 台乙同样不可执行），整数最优 21（两个最优解之一），间隙 10%；本例向下取整恰好得到最优解——这是碰巧，取整方案没有任何最优性保证。

7.2 四张图的解读（本例）

图①：蓝色多边形是 LP 可行域，深色格点是整数候选方案。星形 LP 最优解 $(2.25, 3.75)$ 悬浮在可行域内部，青绿整数最优解 $(0,5)$ 在另一个顶点上；红色 X 号 $(2,4)$ 落在多边形外——一眼看懂"LP 最优解不可执行、取整不可行、整数最优在远处"三个要点。
图②：7 个节点的搜索树展示了全部三种剪枝（青绿 = 更新下界的整数解、灰 = 定界、红 = 不可行），树形很小，说明剪枝高效（根因：积分间隙只有 3.03%）。
图③：上界（蓝） $41.25 \to 41 \to 40.56 \to 40$ 单调下降，下界（橙） $-\infty \to 39 \to 40$ 单调上升，第 3 轮相遇于 40——两条线之间的浅色带即"最优值可能区间"，肉眼可见地在收窄。
图④：41.25（LP，不可达到）与 40（整数最优）之间的 1.25 就是积分间隙；向下取整 34 明显矮一截（低 15%）；四舍五入干脆不可行。

7.3 常见坑与应对

对 LP 解四舍五入：最经典的错误。取整后的点可能违反约束（本例 $(2,4)$ ）、可能不是最优（本例 $(2,3)$ 低 15%）。整数最优解与 LP 最优解可以相距任意远，取整没有任何保证。应对：老老实实用分支定界/求解器；若一定要取整，必须检验可行性并声明"启发式方案，无最优性保证"。
大 M 取值不当：用"大 M 法"表达逻辑约束（"若 $x=0$ 则 $y=0$ "）时， $M$ 取得过大会让 LP 松弛极松，积分间隙巨大，分支定界几乎剪不动枝、节点爆炸。应对： $M$ 取满足逻辑的最小值（如约束中该变量的实际最大可能值，越紧越好）。
变量过多时组合爆炸：求解时间随整数变量个数最坏指数增长。 $n$ 个 0-1 变量理论上 $2^n$ 种组合；当 $n$ 达到数百且结构差时，精确求解可能不可行。应对：先缩小模型（聚合变量、消除对称性）；设置时间上限；必要时改用启发式/元启发式（见第八节），并在论文中如实报告"近似解 + 与松弛界的间隙"。
忽略对称性：大量对称解（如"哪台机器干哪个活"不可区分）会让分支定界重复搜索等价分支。应对：加"对称破缺"约束（如强制 $x_1 \ge x_2 \ge \dots$ ）。
最优解不唯一却只报一个：实例 2 有两个最优解。论文中可写"最优值为 21，其中一组最优解为 $(0,3,0)$ "，不要写"唯一最优解"。
求解时间不可控：同一规模的不同问题耗时可能差几个数量级。竞赛中必须设置 time_limit 并利用 mip_gap 汇报"最好解 + 间隙"，避免"跑不出来"的尴尬。
把整数约束当成"小事"：建模时顺手给连续变量加整数约束，会让问题从"毫秒可解"变成"解不出来"。只有本质离散的量才该是整数变量。
数值容差：LP 解可能是 2.9999998 而非精确的 3，判断"是否为整数"要用容差（本文代码用 $10^{-6}$ ），论文中报最优值时做合理的四舍五入。

7.4 竞赛论文写作建议（话术模板）

建模段（先讲为什么离散、再建模型、再报结果）：

由于决策变量为设备台数/人员人数，具有不可分割性，将问题建立为整数规划模型： $\max z = 5x_1 + 8x_2$ ，约束条件为 $x_1 + x_2 \le 6$ 、 $5x_1 + 9x_2 \le 45$ ， $x_1, x_2 \in \mathbb{Z}_{+}$ 。采用分支定界法求解，得到全局最优解 $x^* = (0, 5)$ ，最优值 $z^* = 40$ 。

松弛与质量保证段（评审加分点）：

为评估模型的紧致性与解的质量，求解其 LP 松弛问题，得松弛最优值为 41.25，与整数最优值 40 相比，积分间隙仅 $3.03\%$ ，说明松弛紧致、分支定界收敛迅速（共搜索 7 个节点），最优性得以保证。

为什么不能四舍五入段（体现对方法理解）：

若将 LP 松弛解 $(2.25, 3.75)$ 直接四舍五入为 $(2, 4)$ ，将违反原料约束（ $5 \times 2 + 9 \times 4 = 46 > 45$ ）；向下取整为 $(2, 3)$ 虽可行但目标值仅为 34，较最优值低 15%。可见取整方案无最优性保证，必须采用精确求解算法。

求解器说明段：

模型使用 HiGHS 求解器（scipy.optimize.milp）求解，最优性相对间隙 mip_gap = 0，即所得解为可证明的全局最优解；求解耗时在毫秒级，满足题目对计算时间的约束。

与启发式对比段（若论文同时用了启发式）：

同时采用遗传算法对同一问题求解，得到的目标值为 39（近似最优），与整数规划精确最优值 40 的相对误差为 2.5%；但遗传算法耗时更短，适用于更大规模问题的快速近似求解。

八、延伸阅读

割平面法（Gomory 割）：与分支定界并列的第二大精确算法思想——每次向 LP 松弛添加一个"切掉当前分数最优解但不切掉任何整数点"的线性割，反复迭代直至得到整数解。现代求解器的 分支-割平面法（Branch-and-Cut） 就是两者的融合。入门可读 Wolsey《Integer Programming》第 8 章。
混合整数规划（MILP）：部分变量整数、部分连续，是实际建模中最常用的形式（如选址问题：0-1 选址变量 + 连续流量变量）。scipy.milp 的 integrality 数组即可表达（0 = 连续，1 = 整数），大 M 法、逻辑约束建模都是 MILP 建模的核心技巧。
0-1 规划（Binary Programming）： $x \in \{0,1\}^n$ 的整数规划，覆盖选址、指派、背包、集合覆盖等一大类竞赛题；分支定界、隐枚举、以及 0-1 变量特有的线性化技巧（乘积项替换、逻辑条件转线性约束）是重点。本系列下一篇（09）专题讲解。
启发式与元启发式：规模大到精确求解不可行时的替代方案——贪心 + 局部搜索、遗传算法、模拟退火、禁忌搜索、蚁群算法等，通常能在可接受时间内给出"不错的"解，但没有最优性保证；实践中常用"启发式给出初始下界 + 精确算法收尾"的混合策略。
动态规划求解整数规划：0-1 背包、最短路径、资源分配等具有最优子结构的问题可用 DP 精确求解（伪多项式时间），状态空间小的时候常比分支定界更快；DP 与 IP 的对比（何时 DP 优于 IP）是竞赛答辩高频问题。
其他进阶主题：列生成（变量多到枚举不完，如切割、排班问题）、Benders 分解（大规模混合整数）、随机整数规划与鲁棒优化（系数不确定）、非线性整数规划 MINLP。
推荐资源：Wolsey《Integer Programming》（理论入门首选）；Conforti 等《Integer Programming》（研究生教材）；姜启源等《数学模型》（竞赛经典，含整数规划建模案例）；scipy.optimize.milp 官方文档（API 与 integrality/约束写法）；HiGHS 求解器官网（了解其支持的问题类型与求解状态码）。

一、算法含义​

1.1 通俗理解​

1.2 数学模型​

1.3 与线性规划的本质区别​

1.4 LP 松弛：整数规划的"瞭望塔"​

1.5 分支定界法（核心算法）​

1.6 其他求解方法​

1.7 优缺点​

二、何时使用（适用场景与条件）​

2.1 适用场景​

2.2 竞赛典型题目​

2.3 使用前提（建模前检查清单）​

2.4 不适用 / 慎用的情形​

2.5 与线性规划、0-1 规划、动态规划的选择​

三、算法指标​

3.1 整数最优目标值 zIPz_{IP}zIP​（整数最优值）​

3.2 LP 松弛最优值 zLPz_{LP}zLP​​

3.3 积分间隙 / LP 松弛间隙（Integrality Gap, IG）​

3.4 分支定界过程指标（节点数与上下界收敛）​

3.5 与"LP 解四舍五入"方案的对比误差​

3.6 求解时间 TTT​

3.7 求解器内部间隙 mip_gap（可选，参考指标）​

3.8 指标汇总表​

四、可视化图表​

4.1 四张图速查表​

4.2 每张图"好"与"异常"的特征​

五、符号说明​

六、可运行程序（完整代码）​

6.1 两个示例问题​

七、结果解读与注意事项​

7.1 运行输出解读（以第六节两个示例为例）​

7.2 四张图的解读（本例）​

7.3 常见坑与应对​

7.4 竞赛论文写作建议（话术模板）​

八、延伸阅读​