Skip to content
返回搜索结果

整数规划 — IP 和混合整数规划 (MIP)

提出者
Ralph Gomory (cutting planes, 1958); land-and-doig branch-and-bound (1960)
年份
1958
类型
Mathematical optimisation — exact combinatorial method

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

整数规划 (IP),当仅部分变量被限制为整数时也称为混合整数规划 (MIP),是数学优化中的一个分支,其中一些或所有决策变量必须取整数或二元值。它建立在线性规划的基础上,通过 Ralph Gomory 的割平面法 (1958) 和 Land-Doig 的分支定界算法 (1960) 正式化,此后已成为调度、分配、路由和资源分配问题的标准精确框架。

方法背后的直觉

普通的线性规划在连续可行域中找到最佳点。但许多实际决策是离散的——你不能安排 2.7 名护士或开设半个仓库。整数规划增加了部分或所有变量必须是整数(或二元 0/1 选择)的约束。该约束的代价是计算上的:可行集不再是光滑的曲面,而是一系列分散的点,找到最佳点可能需要检查大量的候选解。求解器通过智能地将问题分解为更小的子问题(分支)并修剪不能优于迄今为止找到的最佳解的分支(定界),同时通过添加不等式(割平面)来收紧连续近似来管理这一点。

历史学

整数规划起源于 20 世纪 50 年代末,当时研究人员试图将线性规划扩展到离散决策。Ralph Gomory 在 1958 年引入了系统的割平面方法,证明了原则上可以通过添加有限数量的割来解决任何整数规划。Land 和 Doig (1960) 正式化了分支定界法,该方法成为占主导地位的精确算法。Wolsey (1998) 和 Nemhauser 和 Wolsey (1988) 提供了该领域至今仍依赖的标准教科书处理。实际的革命来自于 20 世纪 90 年代分支切割求解器的发展,它将这两种技术与先进的启发式方法相结合,以及后来商业和开源求解器性能的爆炸式增长,使得如今能够实现大规模的实际应用。

何时使用

当决策本质上是离散的时——二元的是/否选择、整数数量或逻辑的开/关约束——并且当你需要一个具有可证明质量界限的精确或近精确最优解时,使用整数规划。它适用于调度、人员和资源分配、车辆路线、设施选址、资本预算和投资组合选择。由于 IP 是确定性优化框架而不是统计推断过程,因此没有最小样本量要求。变量类型可以是二元的、分类的(编码为二元的)或连续的(在混合整数情况下)。关键的实际要求是问题可以用线性目标和线性约束来建模;如果目标或约束是非线性的,则需要混合整数非线性规划 (MINLP) 扩展。

局限与注意事项

  • 整数规划在一般情况下是 NP-难的;求解时间可能随问题规模呈指数增长,且表述不佳。
  • 弱 LP 松弛(大的整数差距)会导致深度、昂贵的搜索树和长时间的运行。
  • 大型基数分类变量的二元展开会使模型规模爆炸式增长。
  • 对于非常大的实例,求解器可能需要提前终止,并带有差距容差,而不是达到零差距。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 产生具有已认证最优性差距的精确最优解,不像启发式方法那样提供质量保证。
  • 原生处理二元和一般整数变量,使其成为组合决策的自然框架。
  • 适用于广泛的领域问题——调度、路由、分配、背包问题——使用相同的数学机制。
  • 现代分支切割求解器可以解决包含数百万个变量和约束的问题,这些问题在几十年前是无法处理的。

应用

  • 员工和护士调度——在遵守工作时间规定的同时,分配班次以满足覆盖要求。
  • 车辆路线和物流——在容量和时间窗口约束下寻找最低成本的配送路线。
  • 设施选址——决定开设哪些仓库或工厂以最小化总分销成本。
  • 资本预算——在预算内选择投资项目组合以最大化总回报。
  • 生产计划——确定跨时间段的整数批量大小,以平衡设置成本和持有成本。
  • 网络设计——选择在通信或交通网络中安装哪些链路。

使用方式

使用方式

1

该问题被构建为一个数学规划:定义决策变量(在问题需要时必须声明为整数或二元),编写一个要最小化或最大化的线性目标函数,并列出所有线性约束。一个紧凑的表述——其连续 (LP) 松弛尽可能接近真实的整数最优解——可以显著减少求解时间。

2

通过暂时放弃整数约束来获得 LP 松弛。求解此松弛速度很快,并产生一个界:其最优值始终至少与真实的整数最优解一样好(最小化的下界)。如果松弛解恰好是全整数的,则问题已解决。否则,松弛与整数约束之间的差距会指导搜索。

3

在松弛解中选择一个分数变量,然后将问题分成两个子问题——一个要求该变量向下取整,一个要求向上取整。每个子问题本身都被松弛并求解,从而创建一个搜索树。其松弛界比迄今为止找到的最佳整数解更差的分支将被修剪,而无需进一步探索。

4

割平面是有效的线性不等式,它们在不移除任何整数可行点的情况下,切除 LP 松弛可行域的一部分。添加强割(Gomory 割、覆盖不等式、团割)可以收紧 LP 界并减少求解器必须探索的节点数量。

5

在所有已探索节点中找到的最佳整数可行解被返回作为最优解。报告最优性差距——最佳整数解与最佳剩余界之间的百分比差异;0% 的差距证明了全局最优性。对于大型 NP-难问题实例,求解器可能会提前终止,并带有用户指定的差距容差,返回一个具有可证明界限的近优解。

常见陷阱

  • 将变量声明为连续但实际上应该是整数——反之亦然——会默默地产生错误的结果;务必验证变量类型是否与问题的物理现实相符。
  • 松弛的表述导致大的 LP 松弛差距,会引起过度的分支;在求解之前,投入时间进行表述收紧(强不等式、对称性打破)。
  • 忽略求解器输出中的整数差距:报告的目标值仅是找到的最佳整数解,除非差距为零,否则不一定是全局最优解。
  • 将 IP 应用于目标或约束为非线性的问题,而没有适当的 MINLP 处理,将导致模型不正确。
  • 对于调度或路由问题,未能添加有效的不等式(如团不等式或覆盖不等式)会留下大量的性能提升空间。

常见问题

IP 和 MIP 有什么区别?

在纯整数规划 (IP) 中,每个决策变量都必须是整数。在混合整数规划 (MIP) 中,一些变量是整数或二元的,而其他变量则允许是连续的。MIP 是实践中更通用、更常用的框架,因为大多数实际问题混合了离散选择和连续数量。

如果线性规划是多项式的,为什么整数规划是 NP-难的?

线性规划在凸多面体上进行优化,并且可以通过单纯形法或内点法在多项式时间内求解。添加整数约束会破坏这种凸性:可行集变成一个有限但可能极其庞大的整数点集合,并且在一般情况下,没有已知的多项式时间算法可以找到最佳点。LP 松弛提供了界,但不是直接的解。

我如何知道我的解是否是最优的?

求解器报告一个最优性差距——最佳整数解与最佳剩余下界之间的百分比差异。0% 的差距证明了全局最优性。对于大型问题,您可以设置一个差距容差(例如 1%)并接受一个近优解;该界仍然保证真实的最佳解不可能比这更好一个百分比。

什么使得表述“紧凑”,为什么它很重要?

紧凑的表述是指其 LP 松弛给出的界接近整数最优解,留下小的整数差距。当差距很小时,分支定界法需要探索的节点更少,终止速度更快。添加有效的不等式,如 Gomory 割、覆盖不等式或团割,可以收紧表述,并且通常是加速求解器最有效的方法。

相关方法

参考文献

  1. Wolsey, L.A. (1998). Integer Programming. Wiley.

    ISBN:9780471283669
    已复制。
  2. Nemhauser, G.L. & Wolsey, L.A. (1988). Integer and Combinatorial Optimization. Wiley.

    ISBN:9780471359432
    已复制。