混合整数规划 — 对连续和整数决策进行精确优化
- 提出者
- Ralph Gomory (branch-and-bound cuts, 1958); Land & Doig (branch-and-bound, 1960)
- 年份
- 1958–1960
- 类型
- Mathematical optimization
- 类别
- Simulation / optimization
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
混合整数规划(MIP)是一种数学优化框架,其中一些决策变量必须取整数值,而另一些可以是连续的。它推广了线性规划,并广泛应用于运筹学、物流、调度、资源分配和工程设计等领域,这些领域自然会出现不可分割性约束——例如是/否决策或整数数量。
方法背后的直觉
许多实际的优化问题涉及无法分割的决策——您要么开设一个设施,要么不开设;您为一次轮班分配一名确切的工人;您订购整数单位。连续线性规划忽略了这些现实情况,并可能产生不可行的分数解。MIP直接在模型中强制执行整数性。求解器通过分支定界法系统地探索可行整数解的空间:它求解松弛的连续子问题来界定每个区域中最佳可能解的上限,丢弃那些无法改进迄今为止找到的最佳整数解的区域,并添加割平面来收紧搜索。结果是一个可证明的最优或近最优计划。
历史学
整数规划的基础由Ralph Gomory奠定,他于1958年引入了割平面方法,Land和Doig于1960年正式化了分支定界法。随后的几十年里,LP松弛理论、多面体组合学(Edmonds、Padberg、Grötschel)得到了发展,到20世纪90年代,商业求解器使大规模MIP变得可行。该领域在Nemhauser和Wolsey(1988)以及Wolsey(1998)的著作中有全面阐述。
何时使用
当您的问题具有线性或可线性化的目标和约束,并且包含必须是整数值的决策(设施选址、乘务员调度、资本预算、网络设计、切割库存问题)时,请使用MIP。当您需要一个可证明的最优解或有界差距的解,并且问题规模可处理(现代求解器可处理数千个变量)时,它是首选方法。当目标或约束高度非线性时(请改用非线性或混合整数非线性规划),当问题大到精确方法无法承受时(考虑启发式或元启发式),或者当连续近似足够准确时(为速度使用LP),请勿使用MIP。
局限与注意事项
- 最坏情况复杂度为NP难;求解时间可能随整数变量数量呈指数增长。
- 需要精确的数学公式;即使底层问题可管理,公式不当的模型也可能难以处理。
- 非凸或非线性元素需要额外的线性化或专用求解器,增加了模型复杂度。
- 商业工具的求解器许可成本可能很高,尽管存在高质量的开源替代方案。
- 结果的好坏取决于模型:错误的约束规范会导致无意义的最优解。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 产生可证明的最优解,并具有可量化的最优性差距,从而能够进行严格的决策论证。
- 原生处理二元和一般整数变量,捕捉现实世界中的不可分割性和逻辑约束。
- 现代求解器(Gurobi、CPLEX、SCIP)利用先进的分支定界法、割平面和预处理来高效处理大型实例。
- 透明的模型公式使假设明确,并可由领域专家进行审计。
- 支持敏感性分析和参数研究,以了解解如何随输入数据变化。
- 广泛的建模语言(AMPL、GAMS、Pyomo、JuMP)支持,可实现快速原型开发。
应用
- 供应链与物流:车辆路径规划、设施选址和库存优化,涉及整数装运量。
- 劳动力调度:护士排班、乘务员分配和班次计划,使用二元分配变量。
- 资本预算:在预算约束下选择不可分割的投资项目组合。
- 电信与网络设计:容量扩展和路由,涉及二元链路激活决策。
- 能源系统:电网中的机组承诺,决定每小时开启或关闭哪些发电机。
- 制造业:生产批量定价、机器调度和切割库存问题,涉及整数批量大小。
使用方式
使用方式
定义优化模型:一个目标函数(要最小化或最大化的决策变量的线性组合)、线性不等式和等式约束以及整数要求。连续变量处理可以为分数的量;二元(0/1)或一般整数变量处理离散决策。
公式
\min_{x,y}\; c^\top x + d^\top y \quad \text{s.t.}\; Ax + By \leq b,\; x \geq 0,\; y \in \mathbb{Z}^p通过暂时删除整数约束来求解LP松弛。这为MIP最优目标提供了下界(对于最小化问题),并提供了一个可能为分数的候选解。
公式
\text{LP relaxation: replace } y \in \mathbb{Z}^p \text{ with } y \geq 0从LP松弛解中选择一个分数整数变量。通过在一个子问题中添加地板约束,在另一个子问题中添加天花板约束,创建两个子问题,从而划分可行空间而不丢失任何整数可行点。
公式
\text{Select fractional } y_j^*; \text{ create subproblems: } y_j \leq \lfloor y_j^* \rfloor \text{ and } y_j \geq \lceil y_j^* \rceil求解每个子问题的LP松弛。如果界限比迄今为止找到的最佳整数解(当前最优解)差,则剪枝该分支。如果LP解恰好是整数可行的,则在改进目标函数时更新当前最优解。
公式
\text{Prune node if LP bound} \geq \text{incumbent; update incumbent when integer-feasible solution found}可选地添加割平面——有效的不等式,它们在不移除任何整数可行点的情况下截断分数LP解。Gomory割是最经典的方法;特定于问题的割(例如,团割、流割)可以显著减小树的大小。
公式
\text{Add Gomory or problem-specific cutting planes to tighten LP relaxation before branching}当分支定界树完全探索完毕,或者当最佳整数解与全局下界之间的差距落入用户指定的容差(例如0.01%)之内时停止。返回具有最优性证明的当前最优解。
公式
\text{Stop when all nodes pruned; return incumbent } x^*, y^* \text{ with optimality gap} \leq \epsilon常见陷阱
- 选择过紧的最优性差距容差可能导致求解器无限期运行;对于大型实例,始终设置一个实际的差距(例如1%)。
- 模型中的对称性(例如,可互换的设施)会产生冗余分支并导致搜索树爆炸——使用对称性破坏约束。
- 弱LP松弛(大的整数差距)会导致非常大的分支定界树;投入时间添加有效不等式或收紧公式。
- 将所有变量都视为整数,而实际上只有部分变量需要如此,这是不必要的昂贵;仅在逻辑约束要求时使用二元变量。
- 忽略使用良好的初始可行解进行热启动,会浪费求解器寻找第一个当前最优解的时间。
常见问题
MIP与线性规划(LP)有何不同?
LP要求所有决策变量都是连续的(实值),这可能产生物理上不可行的分数解(例如,2.7辆卡车)。MIP在部分或全部变量上增加了整数约束,强制要求整数或二元解,但计算复杂度更高。
何时应使用启发式方法而不是MIP?
当问题包含数百万个变量、高度非线性结构或需要近实时解决方案时,精确MIP可能太慢。元启发式(遗传算法、模拟退火)可以快速产生良好的解决方案,但没有最优性保证。当解决方案质量认证很重要时,首选MIP。
什么是 optimality gap(最优性差距),它应该多小?
差距为(当前最优目标 - LP下界)/ LP下界,以百分比表示。它证明了已知最佳整数解与真实最优解的距离。对于大多数实际应用,0.1-1%的差距就足够了;更小的差距需要指数级更多的时间。
MIP可以处理非线性目标或约束吗?
标准MIP假定线性。非线性关系必须线性化(例如,分段线性逼近、乘积的二元展开)或由混合整数非线性规划(MINLP)求解器处理,后者求解起来要困难得多。
推荐使用哪些MIP求解器?
商业:Gurobi和CPLEX是行业标杆。开源:SCIP、CBC(通过COIN-OR)和HiGHS在中等规模问题上具有竞争力。所有这些都支持标准的建模接口,如AMPL、Pyomo和JuMP。
相关方法
参考文献
Nemhauser, G. L., Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley-Interscience, New York.
ISBN:9780471359432已复制。Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.
ISBN:9780471283669已复制。