Skip to content
返回搜索结果

确定性整数规划 — 使用整数决策变量进行精确优化

提出者
Ralph E. Gomory
年份
1958
类型
Exact combinatorial optimization
类别
Simulation / optimization

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

字号

它有什么作用?

确定性整数规划(DIP)是一种数学优化方法,用于在决策变量部分或全部必须取整数值的问题中找到最佳解决方案,前提是目标和约束数据完全已知(确定性)。它是整数规划的经典、非随机形式,自20世纪50年代末以来一直是运筹学和组合优化的基础。

方法背后的直觉

许多现实世界的决策本质上是离散的:您要开设一个设施,或者不开设;您要将一名工人分配到一个班次,或者不分配。连续优化方法无法强制执行这些整数要求。确定性整数规划通过将变量限制为整数来处理此问题,同时所有问题参数——成本、容量、需求——都是确定已知的。结果是在该确定性假设下,一个精确的、可证明最优的解决方案,使其成为与随机和鲁棒变体进行比较的参考模型。

历史学

整数规划起源于20世纪50年代末的线性规划。Ralph Gomory在1958年提出的割平面算法是第一个系统的精确方法。与分支定界(Land和Doig,1960)同时,这些方法定义了该领域。“确定性”一词将经典模型与随机整数规划(Birge和Louveaux,1997)区分开来,并随着考虑不确定性的变体激增而成为标准术语。

何时使用

当满足以下条件时,使用确定性整数规划:(1)决策变量本质上是离散的(分配、调度、设施选址、箱装问题、网络设计);(2)所有问题参数都已知或可以可靠地估计为点值;(3)需要精确的最优解而不是启发式近似。不使用的情况:(参数不确定或依赖于场景(改用随机或鲁棒整数规划);问题规模过大,以至于分支定界在计算上不可行且启发式方法可接受;变量是真正连续的(改用线性规划);或必须同时平衡多个冲突的目标(改用多目标整数规划)。

局限与注意事项

  • 假设所有问题参数都已知——设计上忽略了现实世界的不确定性。
  • 在一般情况下是NP难问题;最坏情况下的求解时间随问题规模呈指数增长。
  • 即使使用现代求解器,大型组合问题也可能需要数小时或数天才能计算。
  • 模型构建质量(约束紧密度、对称性破坏)严重影响求解时间。

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

优势

  • 在确定性模型假设下,保证可证明的最优解。
  • 自然地处理连续方法无法处理的离散、组合决策结构。
  • 得到成熟、高效的商业和开源求解器(CPLEX、Gurobi、SCIP)的支持。
  • 提供最优性差距证明,为大型实例的原则性提前终止提供可能。
  • 作为启发式和随机变体的比较的黄金标准基准模型。

应用

  • 具有离散机器或劳动力资源的生产计划和调度
  • 设施选址:决定开设哪些仓库或工厂
  • 交通和物流中的车辆路径和乘务员调度
  • 资本预算:选择不可分割的投资项目组合
  • 具有固定线路建立成本的电信网络设计
  • 医疗保健人员排班和手术室调度

使用方式

使用方式

1

定义优化模型:一个以整数决策变量的线性组合作为目标函数(最小化或最大化),受一组线性不等式或等式约束的限制。所有系数(c、A、b)都是固定的且已知的——这就是使该模型成为确定性的原因。二元变量(0/1)是用于是/否决策的特例。

公式
\min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0,\; x \in \mathbb{Z}^n
2

求解线性规划松弛,该松弛暂时允许变量取连续值。这给出了整数目标最优值的下界。如果线性规划松弛解已经是整数值,则它对于整数规划是最优的;否则,开始分支。

公式
\text{Solve LP relaxation: } \min \; c^\top x \quad \text{s.t.} \quad Ax \leq b,\; x \geq 0
3

从线性规划松弛解中选择一个分数变量,通过在一个分支上添加地板约束(x_j <= 整数值)和在另一个分支上添加天花板约束(x_j >= 整数值)来分割可行区域,生成两个子问题进行递归求解。

公式
\text{Select fractional variable } x_j^*. \text{ Create two subproblems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceil
4

求解每个子问题的线性规划松弛以获得界限。如果一个节点的界限比已知最佳整数解(现有解)差,则剪枝。如果子问题产生一个比现有解更好的整数可行解,则更新现有解。该过程形成一个分支定界搜索树。

公式
\text{Compute bounds; prune nodes where LP bound} \geq \text{incumbent. Update best integer solution.}
5

割平面方法——最著名的是Gomory割——从线性规划单纯形表中导出额外的线性不等式,这些不等式被所有整数解满足但被当前分数线性规划解违反。添加这些割可以收紧线性规划松弛并减少分支。现代求解器在分支割框架中结合了分支定界和割平面。

公式
\text{Optionally add Gomory cuts or problem-specific valid inequalities to tighten LP relaxation.}
6

当所有开放节点都被剪枝或产生整数解时,算法终止。终止时的现有解是可证明最优的整数解。求解器还会报告最佳界限和现有解之间的差距,该差距可用于大型问题的停止标准。

公式
\text{Return optimal integer solution } x^* \text{ with objective value } z^* = c^\top x^*

常见陷阱

  • 将不确定参数视为确定性点估计可能会产生在实践中表现不佳的解决方案——在应用DIP之前验证此假设。
  • 弱线性规划松弛(大的整数间隙)会导致巨大的分支定界树;在扩展规模之前,应投入有效不等式和重构。
  • 大M公式产生的二元变量爆炸可能导致线性规划松弛在数值上不稳定;优先选择更紧的约束重构。
  • 在使用非零差距容差时,将可行性误认为最优性——始终在目标值旁边报告差距。
  • 忽略模型中的对称性(例如,相同的机器或工人)会导致冗余分支;添加对称性破坏约束。

常见问题

确定性整数规划与随机整数规划的区别是什么?

在确定性整数规划中,所有目标和约束参数都是固定且已知的。随机整数规划通过概率分布或场景显式地对不确定参数进行建模,产生在这些场景下具有鲁棒性或期望最优的解决方案。确定性整数规划更简单、求解更快,但忽略了不确定性。

二元规划是整数规划的特例吗?

是的。二元(0-1)规划将每个决策变量限制在{0, 1}。它是最常见的特例,用于是/否决策,例如是否开设设施、选择项目或分配工人。一般整数规划允许任何非负整数值。

什么时候应该从确定性整数规划切换到启发式方法?

当分支定界树太大,无法在可接受的时间限制内探索,并且一个好的启发式方法(遗传算法、模拟退火、大邻域搜索)的最优性差距对于应用来说是可以容忍的时候。当偏离精确优化时,应报告并说明差距。

确定性整数规划可以处理非线性目标或约束吗?

经典的确定性整数规划假设是线性的(整数线性规划)。存在非线性整数规划,但其难度要大得多;许多非线性形式可以通过辅助二元变量和大M重构进行线性化。二次整数规划(QIP)由一些现代求解器直接支持。

实际中应该使用哪个求解器进行确定性整数规划?

商业:Gurobi或IBM CPLEX以获得最佳性能。学术/开源:SCIP、CBC(通过COIN-OR)或HiGHS。所有这些都实现了带有自动预处理的分支割。对于Python用户,PuLP、Pyomo或scipy.optimize.milp提供了方便的建模接口。

相关方法

参考文献

  1. Gomory, R. E. (1958). Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64(5), 275-278.

    打开 DOI 文献
    已复制。
  2. Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.

    ISBN:9780471283669
    已复制。