整数规划 · 深度手册

分类：优化类 ｜ 难度：★★☆ 进阶 ｜ 编号：ip

一、这是什么（一句话用途）

变量必须为整数(人数 / 台数 / 是否选)

二、核心思想

很多现实决策要求变量是整数：买了几台机器、排了几个人、某个项目做不做（0-1 变量）。把整数约束加到线性规划上就成了整数规划（IP），而 0-1 整数规划几乎能表达一切"选择/分配"问题。难点在于：整数可行域不再是连续多面体，极点理论失效，求解变成组合问题，NP 难。主流算法是分支定界（branch and bound），用 LP 松弛给出上下界并剪枝。

三、数学原理与推导

先解 LP 松弛（去掉整数约束）得到上界（最大化情形）。若某变量解 $x_k=v$ 非整数，则分支为两个子问题：

$$x_k\le\lfloor v\rfloor,\qquad x_k\ge\lceil v\rceil$$

对每个子问题递归求解 LP 松弛。维护两个量：

• 下界（已找到的整数可行解目标值，单调不降）；
• 上界（各活节点 LP 松弛目标最大值）。

定界与剪枝：若某子问题 LP 松弛上界 $\le$ 当前已知整数下界，则该枝不可能产生更优整数解，直接剪除。当所有活节点上界都 $\le$ 下界时，当前整数最优解即为全局最优。0-1 变量用 $x\in\{0,1\}$ 表示"是否选择"。

四、建模 / 求解步骤

1. 建 LP 松弛
2. 分支(取非整数变量)
3. 定界剪枝
4. 回溯得整数最优

五、关键公式速查

同 LP + x_i∈ℤ（0-1 变量用于'是否')

六、典型示例

仓库选址 / 机组排班，用 0-1 变量表示开 / 关。

完整算例（数字演示，照着算一遍）

场景：max z=5x+4y s.t. 2x+3y≤12, x+y≤5, x,y∈ℕ。

枚举整数点：(0,4)=16, (3,2)=23, (2,3)=22, (1,4)=21 → 最优 (3,2), z*=23。

结论：整数约束使最优需枚举整数点，不能直接取整线性松弛解。

七、Python 实现示例

import os, numpy as np
import pandas as pd
HERE = os.path.dirname(os.path.abspath(__file__))
df = pd.read_csv(os.path.join(HERE,"..","datasets","ip.csv"))
cost = df["cost"].to_numpy(dtype=float)
benefit = df["benefit"].to_numpy(dtype=float)
use = df[["r1","r2"]].to_numpy(dtype=float)
# 用暴力/分支思路：scipy 无原生 MILP，此处用 pulp
try:
    import pulp
    m = pulp.LpProblem("sel", pulp.LpMaximize)
    x = {i: pulp.LpVariable(f"x{i}", cat="Binary") for i in range(len(cost))}
    m += pulp.lpSum(benefit[i]*x[i] for i in range(len(cost)))
    m += pulp.lpSum(use[i,0]*x[i] for i in range(len(cost))) <= 120
    m += pulp.lpSum(use[i,1]*x[i] for i in range(len(cost))) <= 90
    m.solve(pulp.PULP_CBC_CMD(msg=False))
    print("选中项目:", [i for i in x if x[i].value()>0.5])
    print("总收益=%.1f"%pulp.value(m.objective))
except ImportError:
    print("需安装 pulp：pip install pulp")

配套文件：py_ip.py（需 numpy / pandas；与下方数据集配套练习）

八、MATLAB 实现示例

%% 0-1 整数规划示例（MATLAB，需 intlinprog）
df = readtable('..\datasets\ip.csv');
cost=table2array(df(:,2)); ben=table2array(df(:,3));
use=table2array(df(:,4:5));
f=-ben; A=use'; b=[120;90];
intcon=1:length(f); lb=zeros(size(f)); ub=ones(size(f));
x=intlinprog(f,intcon,A,b,[],[],lb,ub);
fprintf('选中: '); disp(find(x>0.5'));

配套文件：m_ip.m（基础 MATLAB / Octave 即可运行）

九、练手数据集（可下载）

6 个项目的成本/收益与两种资源消耗，资源上限 120/90。用于 0-1 整数规划选项目。

• 字段：project, cost, benefit, r1, r2
• 行数：6 行
• 下载：ip.csv

十、常见误区与避坑清单

• 计算量大(组合爆炸)
• 0-1 建模要写对
• 松弛解下界参考

十一、结果怎么解读

最优值为整数；看变量取 0/1 含义。

十二、常与谁搭配

非线性见 nlp。

十三、论文写作技巧（怎么把它写进论文）

把 整数规划 写进论文，核心不是堆公式，而是讲清「为什么用它、结果怎么呈现、如何对比」三件事。

1. 动机怎么写（为什么用它而不是别的）

先把问题「数学化」：决策变量、目标函数、约束条件——这一步写清楚比算法本身更重要。再说明为何用 整数规划 求解：连续可导用梯度 / 解析法，组合 / 非凸 / 黑箱用启发式（GA / PSO / SA）。

2. 结果怎么写（图表与指标）

放「收敛曲线（迭代 vs 目标值）」+「最优解参数表」+「约束是否满足」三件套。若是多目标，放 Pareto 前沿散点图。

3. 可直接套用的写作话术

• 中文模板：针对<问题>，本文采用 整数规划 进行变量必须为整数(人数 / 台数 / 是否选)。该方法能够自动刻画<优势>，在处理<场景>时相较<对比方法>更具<特点>。
• 英文模板：To address , we adopt 整数规划 to 变量必须为整数(人数 / 台数 / 是否选). Benefiting from its ability to , it outperforms on .

4. 同类易踩的写作坑

务必说明约束是否全部满足、是否陷入局部最优（可多次随机初始化对比）；别把无约束结果当约束最优报。

5. 典型论文段落范例（可直接参考 / 改写）

下面是一段可直接套用的论文表述，已按本算法定制，填空处（…）替换成你的真实数值即可。

将配送中心选址建模为带容量约束的总成本最小化问题，本文采用 整数规划 求解，得到 5 个选址及其服务分配方案，目标值较贪婪启发式降低 12.4%，且全部约束满足。

We formulate the distribution center location as a total-cost minimization problem with capacity constraints and solve it via 整数规划, yielding 5 sites and their service assignments. The objective is 12.4% lower than a greedy heuristic while satisfying all constraints.

十四、相关手册（延伸阅读）

• 非线性规划 · 优化类

十五、本手册导航

• 上一篇：插值（拉格朗日 / 样条） · 预测类
• 下一篇：模拟退火 SA · 优化类
• 返回：算法深度手册库 ｜ 资料站首页

---

本手册由「算法深度手册生成器」自动产出，配套提供 Python / MATLAB 双版本示例与可下载练手数据集。