Skip to content
返回搜索结果

多目标混合整数规划

提出者
Ehrgott, M.; Mavrotas, G. and others in multi-criteria optimization
年份
1980s–2000s
类型
Mathematical optimization
类别
Simulation / optimization

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

字号

它有什么作用?

多目标混合整数规划(MO-MIP)是一种优化框架,它在满足线性或非线性约束的条件下,同时优化两个或多个相互冲突的目标函数,其中一些决策变量被限制为整数值,而另一些则是连续的。它广泛应用于工程设计、供应链规划、资源分配和调度问题,这些问题需要离散选择与连续数量并存。

方法背后的直觉

许多现实世界的决策既涉及离散选择(例如,开设多少家工厂、资助哪些项目、是否购买一台机器),也涉及连续决策(例如,生产多少、如何分配预算)。当这些选择同时影响多个相互冲突的目标时——例如,在成本最小化的同时最大化服务水平——就不存在单一的最优解。相反,MO-MIP探索所有非支配解的权衡前沿(帕累托前沿),为决策者提供了一张可行的妥协方案的结构化地图,而不是一个单一的强制答案。

历史学

混合整数规划在20世纪50年代至60年代通过Gomory以及Land和Doig的工作得以形式化。多目标扩展在20世纪70年代至80年代出现,当时研究人员认识到许多工程和运筹学问题涉及相互竞争的目标。Ehrgott (2005) 和 Mavrotas (2009) 巩固了系统性处理,他们的ε-约束实现仍然是实际 MO-MIP 的广泛引用的参考文献。

何时使用

当决策问题自然涉及整数或二进制变量(设施选址、项目选择、调度)以及连续数量,并且需要明确权衡两个或多个冲突目标时,请使用 MO-MIP。当需要精确或接近精确的帕累托解且计算资源允许分支定界搜索时,它适用。当所有变量都是连续的(此时应使用多目标线性规划或非线性规划)、当问题规模使得精确 MIP 求解难以处理且元启发式方法更实用、或者当单一聚合目标足以满足需求且多目标分析不增加决策价值时,请勿使用它。

局限与注意事项

  • 计算成本随整数变量数量和问题规模呈指数增长;对于大型实例,精确方法可能难以处理。
  • 需要以数学形式精确制定所有目标和约束,这对于定性或模糊的现实目标可能很困难。
  • 加权和等标量化方法无法发现帕累托前沿非凸区域中的解,可能遗漏重要的权衡。
  • 生成密集的帕累托前沿需要求解许多 MIP 子问题,从而使总计算时间成倍增加。
  • 结果对约束公式和问题数据精度敏感;不可行或边界不佳的模型不会产生有用的输出。

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

优势

  • 为每个标量化子问题提供可证明的最优或接近最优解,保证了可处理问题规模的帕累托前沿质量。
  • 自然处理现实世界中的离散选择(二进制决策、整数数量),这是连续松弛无法忠实表示的。
  • 产生完整的帕累托前沿,为决策者提供透明、结构化的权衡信息,而不是单一的强制妥协。
  • ε-约束法和其他系统性标量化方法允许对非支配解集进行受控的、密集的探索。
  • 与广泛的商业和开源求解器(CPLEX、Gurobi、GLPK、CBC)兼容,这些求解器能够处理大规模 MIP 问题。

应用

  • 设施选址和供应链网络设计:通过二进制开/关变量同时最小化成本和最大化客户服务覆盖。
  • 资本预算和项目组合选择:在预算和资源约束下,通过二进制项目选择变量最大化回报和最小化风险。
  • 生产调度:通过整数批量和二进制机器分配同时最小化完工时间和拖期。
  • 能源系统规划:通过离散投资决策和连续调度变量优化发电厂组合的成本和二氧化碳排放。
  • 医疗资源分配:通过整数人员配置和二进制设施决策,在最小化支出的同时最大化患者覆盖和公平性。
  • 交通和物流:通过整数车队和路线决策,同时最小化旅行时间和排放。

使用方式

使用方式

1

通过指定 k 个目标函数 f_1(x), ..., f_k(x)(需最小化或最大化)、一组线性或非线性约束 Ax <= b,以及变量域来制定问题,其中一些变量是整数值(例如,二进制 0/1),另一些是连续的。在求解之前,明确定义边界和数据。

2

应用标量化或分解策略,将多目标问题转换为一系列单目标 MIP 子问题。常见的策略包括加权和法(最小化 w_i * f_i 的和)、ε-约束法(优化一个目标,同时将其他目标限制在阈值水平)和实现标量化函数。

3

使用分支定界、分支割或其它精确求解器(例如,CPLEX、Gurobi、GLPK)求解每个标量化的 MIP 子问题。对于每个子问题,求解器探索整数可行解空间,在每个节点应用 LP 松弛并剪枝不可行或被支配的分支。

4

收集子问题运行中的所有非支配解,以近似或精确地构建帕累托前沿。当两个解决方案在所有目标上都没有严格优于另一个时,它们是非支配的。通过改变参数重复标量化-求解循环,以使前沿更密集。

5

向决策者展示帕累托前沿,并辅以可视化(散点图、平行坐标图)。应用多准则决策规则、利益相关者偏好或词典序,从非支配集中选择一个首选解决方案进行实施。

常见陷阱

  • 在非凸目标空间上使用加权和法会遗漏帕累托前沿的整个部分;在这种情况下,首选ε-约束法或增广实现标量化函数。
  • 在松弛中将整数变量视为连续变量然后进行四舍五入,不能保证帕累托最优性,并可能产生不可行或被支配的解。
  • 在求解前忽略约束冗余或紧密性检查可能导致求解器运行时间过长或报告虚假不可行性。
  • 在没有过滤或可视化指导的情况下向决策者呈现所有帕累托解会导致决策瘫痪;始终将结果与结构化选择支持一起提供。
  • 在过少的标量化运行后假设帕累托前沿是完整的,可能导致过于自信的结论;通过检查所有收集到的解之间的非支配性来验证覆盖范围。

常见问题

MO-MIP 与标准多目标线性规划有何不同?

在多目标线性规划中,所有决策变量都是连续的,因此可以在凸多面体的顶点处找到有效的帕累托解。MO-MIP 要求部分或全部变量为整数值,使得可行集非凸且离散,这需要分支定界搜索而不是基于单纯形的方法。

我可以使用 NSGA-II 等元启发式算法代替精确的 MIP 求解器吗?

可以,对于大规模或组合复杂的问题,元启发式算法通常更受欢迎,因为它们具有更好的可扩展性。权衡是它们提供近似的帕累托前沿,没有最优性保证,而精确的 MO-MIP 求解器保证它们找到的解的非支配性。

什么是ε-约束法,为什么推荐它?

ε-约束法优化一个目标,同时将所有其他目标限制在不低于指定边界(ε值)的水平。它可以发现加权和法遗漏的非凸帕累托区域中的解,使其对于一般的 MO-MIP 问题更可靠。

我应该生成多少个帕累托解?

这取决于目标的数量和决策所需的精度。对于两个目标,20-50 个均匀分布的解通常足以表征前沿。对于三个或更多目标,数量呈组合式增长;建议使用交互式或偏好引导方法以避免解的过载。

MO-MIP 适用于数据不确定的问题吗?

标准 MO-MIP 假设数据是确定性的。当输入数据不确定时,应将其与鲁棒优化或随机规划扩展相结合——例如,两阶段随机 MO-MIP 或具有最坏情况目标边界的鲁棒 MO-MIP。

相关方法

参考文献

  1. Ehrgott, M. (2005). Multicriteria Optimization (2nd ed.). Springer, Berlin.

    ISBN:9783540213987
    已复制。
  2. Mavrotas, G. (2009). Effective implementation of the epsilon-constraint method in Multi-Objective Mathematical Programming problems. Applied Mathematics and Computation, 213(2), 455-465.

    打开 DOI 文献
    已复制。