混合整数线性规划 MILP 是什么？排产、调度和物流背后的数学优化

混合整数线性规划（Mixed Integer Linear Programming，MILP）是一种数学优化技术，用于在一组线性约束条件下，寻找线性目标函数的最大值或最小值，并且要求部分或全部变量必须取整数。它是运筹学中最核心、应用最广泛的工具之一。

从线性规划说起

MILP 是线性规划（LP）的扩展。线性规划要解决的问题是：在若干个用线性不等式表示的限制条件下，让一个线性的目标最优。比如一家工厂生产两种产品，每种产品消耗的原料和工时不同、利润不同，原料和工时都有上限，问各生产多少能让利润最大。线性规划里的变量可以取任意的小数。

但现实中很多决策必须是整数：你不能派 2.7 辆卡车，不能建 0.5 个仓库，一个员工要么上这个班、要么不上。MILP 允许问题中的部分变量是整数，甚至是只能取 0 或 1 的“是否”变量，这让它能更精确地描述现实世界的许多问题。“混合”指的就是同时有连续变量和整数变量。在 MILP 中，目标函数和所有约束都仍然是线性的。

能解决什么问题

MILP 的应用几乎遍布所有行业：生产计划和排程，安排哪台机器在什么时间生产什么；物流和车辆路径，规划配送路线、分配车辆；设施选址，决定在哪里建仓库、工厂、门店；排班，安排员工、航班机组、护士的班次；电力系统调度，决定哪些发电机组开机、各发多少电；供应链网络设计、投资组合优化、芯片布局布线，等等。

为什么难解

加上整数的要求后，问题的难度会急剧上升。线性规划可以高效地求解，而 MILP 在一般情况下属于 NP 难问题：最坏情况下求解时间会随问题规模指数增长。常用的求解方法是分支定界：先放松整数要求，求出一个线性规划的解作为参考；如果某个变量不是整数，就把问题“分支”成两个子问题，比如这个变量小于等于 2 和大于等于 3，分别求解；用已知的最好解作为“界”，剪掉不可能更好的分支。现代求解器，比如 Gurobi、CPLEX、SCIP，以及国内的 COPT、MindOpt 等，还结合了割平面、启发式算法等大量技术。近年来，研究者也在用机器学习改进求解器的各个环节，比如学习更好的分支策略，形成了“AI 加运筹”的研究方向。