组合优化：从理论到实践 - 第3节 📌 1. 整数规划模型

📌 1. 整数规划模型

整数规划 (Integer Programming, IP) 是线性规划中变量取整数值的优化问题。标准形式：

min c^Tx
s.t. Ax ≤ b, x ≥ 0, x ∈ ℤⁿ (或部分整数)

常见类型：

纯整数规划：所有变量均为整数。
混合整数规划 (MIP)：部分变量整数，部分连续。
0-1 整数规划：变量取值 0 或 1 (二进制)。

应用领域	典型问题	整数变量含义
📦 物流	车辆路径 (VRP)	车辆使用数量
🏭 生产调度	作业车间调度	机器分配/顺序
💰 金融	投资组合选择	是否投资 (0-1)
🧬 生物信息	基因选择	特征选取

🌳 2. 分支定界算法原理

分支定界 (Branch and Bound, B&B) 是一种隐枚举框架，通过分支和定界剪枝搜索树。

🔹 核心步骤

松弛：去掉整数约束，求解 LP 松弛。
分支：若解 x_j 非整数，创建两个子问题：x_j ≤ ⌊x_j⌋ 和 x_j ≥ ⌈x_j⌉。
定界：每个节点计算下界 (最小化问题)。
剪枝：若下界 ≥ 当前全局上界，则剪枝。

🔹 算法伪码

1. 初始化: 上界 U = ∞, 队列 Q ← {根节点}
2. while Q ≠ ∅:
3.   从 Q 取出节点 N
4.   求解 N 的 LP 松弛 → 下界 L
5.   if L ≥ U: 剪枝 (prune)
6.   else if 解整数可行: U = min(U, L)
7.   else: 选择分数变量 xⱼ 分支
8.         生成子节点加入 Q
9. 返回 U 对应的整数解

⚙️ 3. 分支策略 & 界的选择

🌿 分支策略

最不可行分支：选择分数部分最接近 0.5 的变量。
伪成本分支：基于历史目标变化估计。
强分支：测试候选变量，选择提升下界最多的。
最小编号/最大编号：简单但低效。

📊 界的选取 (定界)

下界：LP 松弛解 (快速但松)。
上界：当前最佳整数可行解 (启发式/割平面)。
改进：使用 Gomory 割、覆盖不等式等收紧下界。

策略	优点	缺点
最不可行	简单，易实现	可能产生大量分支
强分支	节点少，树小	每个节点计算量大
伪成本	平衡计算与节点数	需要维护历史

⏳ 4. 算法复杂度分析

整数规划是 NP-hard 问题。分支定界在最坏情况下指数级节点 (2ⁿ)。

松弛复杂度：LP 求解使用单纯形/内点法，多项式时间 (实际高效)。
分支树大小：依赖于整数变量数量、约束紧度、分支策略。
剪枝效率：好的上界/下界可大幅削减节点。
平均表现：许多实际问题可在合理时间内求解 (尤其使用割平面)。

📈 复杂度总结： 最坏 O(2ⁿ)，但借助启发式、割平面、并行计算，实际可解数百变量。

🐍 5. Python 实现 (ortools & pulp)

使用 ortools (Google OR-Tools) 和 pulp 求解整数规划。下方展示分支定界风格示例 (MIP 求解器内部已实现 B&B)。

🔧 示例：0-1 背包 (整数规划)

# 使用 pulp 实现分支定界 (底层调用 CBC)
import pulp

# 定义问题
prob = pulp.LpProblem("Knapsack", pulp.LpMaximize)

# 变量 (0-1)
x1 = pulp.LpVariable("x1", cat="Binary")
x2 = pulp.LpVariable("x2", cat="Binary")
x3 = pulp.LpVariable("x3", cat="Binary")

# 目标: 最大化价值
prob += 15*x1 + 10*x2 + 8*x3

# 约束: 重量 ≤ 10
prob += 5*x1 + 4*x2 + 3*x3 ≤ 10

# 求解 (分支定界)
prob.solve(pulp.PULP_CBC_CMD(msg=False))

# 输出
print("状态:", pulp.LpStatus[prob.status])
for v in [x1, x2, x3]:
    print(v.name, "=", int(v.varValue))

🧪 使用 ortools (CP-SAT) 求解整数规划

# ortools CP-SAT 求解器 (内部使用分支定界/冲突分析)
from ortools.sat.python import cp_model

model = cp_model.CpModel()
x = model.NewIntVar(0, 10, 'x')
y = model.NewIntVar(0, 10, 'y')
model.Add(2*x + 3*y ≤ 12)
model.Maximize(5*x + 4*y)

solver = cp_model.CpSolver()
status = solver.Solve(model)

if status == cp_model.OPTIMAL:
    print(f'x={solver.Value(x)}, y={solver.Value(y)}')
    print(f'目标值={solver.ObjectiveValue()}')

💡 实际求解器 (CBC, SCIP, Gurobi) 均采用分支定界 + 割平面 (Branch-and-Cut)。

🧩 整数规划与分支定界 Branch & Bound