3.2 整数规划与分支定界

3.2 整数规划与分支定界

本节摘要：整数规划（IP）处理取值必须为整数的决策变量，虽只比线性规划多一个"取整"要求，却跨过了 NP 难的门槛。本节以仓库选址为战例，演示分支定界法"松弛求界、分支分割、剪枝加速"的完整搜索过程，并讨论取整近似为何危险、建模中 0-1 变量的三种惯用法。

为什么不能四舍五入

区域配送公司要在 5 个候选点位中选建仓库，建库有固定成本，各点位到 6 个客户的运输成本不同，目标是最小化"建库费 + 运输费"。这是典型的选址问题：建或不建是 0-1 决策，没有"建 0.7 个仓库"这回事。

先看偷懒方案的代价。把 0-1 变量放松成 0 到 1 的连续变量（线性松弛），求出最优解再四舍五入：松弛解可能是"点位 1 取 0.6、点位 3 取 0.4"，舍入后选了点位 1，总成本比真正的整数最优高出一截；更糟的场景里，舍入解直接违反约束——比如两个仓库必须共选一个的约束，舍入后变成了两个。取整近似既可能次优，也可能不可行，这正是整数规划必须作为独立兵器的理由。

分支定界：聪明的穷举

分支定界搜索树示意

分支定界（branch and bound）是整数求解器的核心框架，思路两步走。定界：先解线性松弛，得到的成本是所有整数解的成本下界（最小化问题里，放松了约束只会更优不会更差）。若松弛解恰好全是整数，运气好，它就是原问题最优解。分支：否则挑一个分数变量（比如取 0.6 的选址变量），把问题劈成两半——该变量 ≤ 0 与 ≥ 1 两个子问题，各自再解松弛、再定界。搜索树如此生长，剪枝靠两条规则：子问题的界已经比已知可行整数解差（不可能反超，剪掉）；子问题不可行（剪掉）。

import numpy as np
from scipy.optimize import milp, LinearConstraint, Bounds

# 5 个点位建库成本，6 个客户由最近可用仓库服务（简化为指派成本矩阵）
build = np.array([120.0, 150.0, 90.0, 130.0, 110.0])
trans = np.array([[20, 34, 16, 28, 22],
                  [24, 18, 30, 26, 20],
                  [12, 26, 22, 18, 30],
                  [30, 14, 26, 24, 16],
                  [26, 22, 14, 32, 18],
                  [18, 28, 24, 12, 26]], dtype=float)

n, m = 5, 6
# 变量：x(5个0-1建库) + y(6x5个0-1指派)，共 35 个
c = np.concatenate([build, trans.ravel()])
integrality = np.ones(n + n * m)          # 全部取整
bounds = Bounds(lb=np.zeros(n + n * m), ub=np.ones(n + n * m))

rows, lb, ub_ = [], [], []
for j in range(m):                        # 每客户恰好指派一个仓库
    r = np.zeros(n + n * m)
    r[n + j*n:n + (j+1)*n] = 1.0
    rows.append(r); lb.append(1.0); ub_.append(1.0)
for k in range(n):                        # 指派给某仓库则该仓库必建
    for j in range(m):
        r = np.zeros(n + n * n)
        r[n + j*n + k] = 1.0; r[k] = -1.0
        rows.append(r); lb.append(-np.inf); ub_.append(0.0)

from scipy.sparse import vstack
import scipy.sparse as sp
A = sp.csr_matrix(np.array(rows))
con = LinearConstraint(A, np.array(lb), np.array(ub_))
res = milp(c=c, constraints=con, integrality=integrality, bounds=bounds)
x = res.x[:n]
print("选中点位:", np.where(x > 0.5)[0] + 1, f" 总成本 {res.fun:.0f}")
​

求解器返回的不只是解，还有 mip_gap（整数解与下界的相对间隙）。间隙为 0 表示证书齐全的最优；间隙 3% 表示"这个解距离理论最优最多差 3%"——大规模问题常设一个可接受的间隙提前收兵，这是 NP 难问题的标准工程姿势。

0-1 变量的三种惯用法

整数规划的建模力大部分来自 0-1 变量的修辞术。选择：选中与否，如选址、机型选择。蕴含："若选 A 必须选 B"，写成 x_A ≤ x_B。互斥与门槛："A、B 至多选一"是 x_A + x_B ≤ 1；"投资 B 的前提是 A 已投产"是 x_B ≤ x_A；"产量超过 50 才允许开第二条产线"这类分段逻辑，也靠 0-1 变量与大 M 常数拼接。掌握这几招，大部分离散决策都能落进 IP 框架。

⚠️ 常见坑：大 M 取值随手写个天文数字。M 过大会让线性松弛极度松垮，分支定界要在搜索树里挣扎很久。工程原则是 M 取"能让约束有意义的最小值"，比如产量的现实上限，而不是 10 的九次方。

建模升维：逻辑约束的组合术

整数规划的威力在 0-1 变量的组合术，值得再补三个高频句式。选且至少选若干个："从候选项目里选至少三个"写成各项目变量之和大于等于三。蕴含链："选了配送中心甲才能服务东区"写成服务变量小于等于建站变量，一条不等式完成条件逻辑。互斥与配对："航线一与航线二不能同时开，但开了航线三就必须开其一"，多句线性不等式拼出任意布尔逻辑——任何与或非表达式都可以化为线性约束组。掌握这套句式后你会发现，离散决策世界里几乎没有逻辑是表达不了的；瓶颈从来不在表达力，而在表达之后的求解难度——这也是为什么有经验的建模者会刻意"少用变量、用紧的公式"，同一个逻辑的不同线性写法，松弛质量可能天差地别。

本节要点回顾

• 取整近似有双重风险：次优与不可行，离散决策必须用整数规划正面处理；
• 分支定界 = 松弛定界 + 分支分割 + 界剪枝，间隙指标度量解的质量；
• 线性松弛给下界，已找到的整数解给上界，两者夹出最优所在区间；
• 0-1 变量三招：选择、蕴含、互斥门槛，是离散建模的通用语法；
• 大 M 要贴身取值，过大的常数会拖垮松弛质量。

线性和整数兵器都假设目标与约束是直的。下一节允许曲线进入沙盘，代价是"局部最优"的幽灵开始游荡。