混合整数线性规划（MILP）算法
MILP（Mixed-Integer Linear Programming，混合整数线性规划）是一类优化问题，在这类问题中，决策变量包含整数变量和连续变量，目标函数和约束条件都是线性函数。
MILP 广泛应用于工业、交通、能源、供应链管理等领域，尤其适用于涉及离散决策（如调度、路径选择、分配问题）和连续变量优化（如资源分配、成本最小化）的场景。
1. MILP 的基本形式
MILP 问题的标准数学表达式如下：
$$ \begin{aligned} & \min c^T x \ & \text{s.t. } Ax \le b \ & x_i \in \mathbb{Z}, \forall i \in I \ & x_j \in \mathbb{R}, \forall j \in J \end{aligned} $$
其中：
- x 是决策变量向量，包含整数变量（x_i）和连续变量（x_j）。
- c 是目标函数的系数向量。
- A 是约束系数矩阵，b 是约束向量。
- I 是整数变量的索引集合，J 是连续变量的索引集合。
如果所有变量都是整数，则该问题变为整数线性规划（ILP）；如果所有变量都是连续的，则是线性规划（LP）。
2. MILP 的求解方法
由于整数变量的存在，MILP 问题比 LP 问题复杂得多，通常采用以下方法求解：
(1) 分枝定界法（Branch and Bound, B&B）
- 该方法先忽略整数约束，求解对应的LP 松弛问题（Relaxation）。
- 如果得到的解满足整数约束，则该解是最优解；否则，基于某个非整数变量进行分枝，将问题分解成两个子问题（如分别向上或向下取整）。
- 通过界限（Bound）剪枝以减少计算量，从而加速求解。
(2) 割平面法（Cutting Plane）
- 在 LP 松弛解的基础上，通过构造额外的**不等式约束（割平面）**来排除非整数解，使得解逐步收敛到整数解。
- 常见的割平面有 Gomory 割平面、混合整数割平面等。
(3) 分支定界与割平面结合（Branch and Cut）
- 结合 B&B 和割平面方法，通过添加割平面提高 B&B 的效率，减少搜索空间。
(4) 启发式和元启发式方法
- 在大规模 MILP 问题中，精确算法可能计算时间过长，因此会采用启发式算法（如贪心算法）或元启发式算法（如遗传算法、模拟退火、粒子群优化等）来找到近似解。
3. MILP 的应用
(1) 交通与物流
- 列车调度优化：确定列车的运行时间表，以最小化总延误或能耗。
- 车辆路径问题（VRP）：优化物流配送路径，减少运输成本。
- 航空调度：优化飞机航班安排，提高机场运营效率。
(2) 生产与制造
- 生产调度：合理安排机器和工人的工作任务，提高生产效率。
- 库存管理：优化库存补货策略，降低仓储成本。
(3) 能源系统
- 电力系统调度：确定发电机组的开关状态和发电功率，以最小化成本。
