Heuristic Multiobjective Discrete Optimization using Restricted Decision Diagrams

本文提出了一种基于受限决策图的多目标离散优化启发式方法，通过结合简单规则、特征工程机器学习及端到端深度学习的新节点选择策略，在显著提升求解速度的同时高效恢复了多目标问题中超过 85% 的帕累托前沿。

要点

这篇论文讲述了一个关于**“如何在众多选择中快速找到最佳平衡点”**的聪明办法。

想象一下，你正在经营一家餐厅，想要同时做两件事：

1. 赚最多的钱（利润最大化）。
2. 让顾客最满意（服务质量最大化）。

但这很难，因为通常你想赚大钱就得用便宜的食材（可能降低质量），或者想提升质量就得花大钱（降低利润）。这就是所谓的**“多目标优化”问题。你的目标不是找到一个“完美”的单一答案，而是找到一组“帕累托前沿”（Pareto Frontier）**——也就是那些“你无法在不牺牲一个目标的情况下改善另一个目标”的最佳方案集合。

1. 核心难题：地图太大了，走不完

传统的计算机方法（就像一张巨大的决策树地图）试图画出所有可能的路线，然后找出所有的好方案。

• 比喻：这就好比你要探索一个拥有几亿个房间的迷宫，每个房间代表一种做菜方案。虽然有些房间是“宝藏屋”（帕累托最优解），但绝大多数房间都是死胡同或者普通房间。
• 问题：当迷宫太大时，计算机内存会爆炸，或者算到地老天荒也跑不完。

2. 现有工具：受限决策图（Restricted DDs）

研究人员之前发明了一种叫**“决策图”（Decision Diagram, DD）**的工具，它能把这个巨大的迷宫压缩成一张更紧凑的地图。

• 比喻：就像把迷宫里的死胡同都堵上，只保留主干道。
• 新挑战：如果迷宫实在太大，连压缩后的地图也放不下，或者你急着要结果，该怎么办？
• 老办法：以前大家是随机砍掉地图上的路，或者用简单的规则（比如“只保留最宽的路”）。但这就像**“盲人摸象”**，很容易不小心把真正的“宝藏屋”（帕累托最优解）给删掉了，导致最后找到的方案质量很差。

3. 本文的突破：给地图装上“智能导航”

这篇论文的核心贡献是发明了一套**“智能节点选择启发式算法”（NOSHs）**。

• 比喻：以前删路是“瞎删”，现在他们给地图装上了**“智能导航员”**。这个导航员知道哪些路通向“宝藏屋”，哪些路是死胡同。
• 目标：在保持地图足够小（内存够用、速度快）的前提下，尽可能多地保留通往“宝藏屋”的路。

4. 三种“导航员”策略

论文提出了三种不同级别的导航员，适应不同的场景：

A. 规则型导航员（Rule-based）—— “经验丰富的老向导”

• 原理：不需要学习，直接根据简单的经验法则。
• 比喻：比如在背包问题里，老向导会说：“只保留那些装得最满的背包状态，因为通常装得越多，价值越高。”
• 适用：简单、快速，不需要训练数据。

B. 机器学习型导航员（Feature Engineering）—— “读过很多书的分析师”

• 原理：先人工提取一些关键特征（比如物品重量、价值分布），然后训练一个模型（如 XGBoost）来识别哪些状态是好的。
• 比喻：就像招聘了一位分析师，你教他看“重量”、“价值”、“剩余空间”等数据，他就能判断这个状态有没有潜力。
• 适用：比规则更灵活，准确率更高。

C. 端到端深度学习导航员（End-to-End Deep Learning）—— “天才 AI 侦探”

• 原理：这是最厉害的一招。不需要人工教它看什么特征，直接把整个问题的结构（像一张复杂的社交网络图）扔给一个图神经网络（GNN）。AI 自己从原始数据里“悟”出规律。
• 比喻：这就像派了一个天才侦探进入迷宫。他不需要你告诉他“看墙壁颜色”，他能自己观察迷宫的结构、光线、气流，瞬间就能感知到“宝藏屋”藏在哪里。
• 适用：处理最复杂、最棘手的问题（如旅行商问题），效果最好。

5. 效果如何？（成绩单）

研究人员在三个经典难题上测试了这套方法：

1. 多目标背包问题（怎么装包最划算）。
2. 多目标集合打包问题（怎么选项目不冲突且收益高）。
3. 多目标旅行商问题（怎么规划路线最省钱又最快）。

结果令人震惊：

• 速度快：比传统的“穷举法”快了 2.5 倍 以上，甚至有的情况快了 11 倍。
• 质量高：虽然地图变小了，但他们成功找回了 85% 以上 的真正“宝藏屋”（帕累托最优解）。
• 精准：找到的方案里，绝大多数都是真正的好方案，几乎没有“垃圾”方案混入。

总结

这篇论文就像是在说：

“以前我们想找到所有的好方案，必须把整个迷宫跑一遍，太慢了。现在我们发明了一种**‘智能筛选器’**，它能像经验丰富的向导或天才侦探一样，一眼看出哪些路值得走，哪些路可以忽略。这样，我们既能在几秒钟内给出高质量的答案，又不会错过最重要的宝藏。”

这对于现实生活中的决策（如物流调度、投资组合、资源分配）非常有价值，因为它让计算机能在极短的时间内，为决策者提供高质量的备选方案，而不是让他们对着庞大的数据发呆。

技术摘要

论文技术总结：基于受限决策图的多目标离散优化启发式方法

1. 研究背景与问题定义

背景：
现实世界的决策通常涉及多个相互冲突的目标（如最大化利润同时最小化风险），这被建模为多目标优化（MOO）问题。与单目标优化寻找单一最优解不同，多目标优化的目标是找到帕累托前沿（Pareto Frontier），即一组不可支配的可行解（无法在不恶化其他目标的情况下改进任一目标）。

核心问题：
本文聚焦于多目标整数线性规划（MOILP）。近年来，**决策图（Decision Diagrams, DDs）**已成为解决此类问题的最先进方法，能够紧凑地编码可行解空间。然而，精确的 DD 枚举面临的主要瓶颈是：随着问题规模增大，帕累托前沿的大小呈指数级增长，导致内存溢出或计算时间过长，难以满足实际应用中快速获得高质量近似解的需求。

研究目标：
如何在内存受限或时间紧迫的情况下，通过构建受限决策图（Restricted DDs），快速且高质量地近似帕累托前沿？即，在限制 DD 宽度（每层节点数）的前提下，如何智能地选择保留哪些节点，以最大化恢复真实帕累托前沿的比例。

2. 核心方法论

作者提出了一种名为**节点选择启发式（Node Selection Heuristics, NOSHs）**的框架，用于在构建受限 DD 时筛选节点。其核心洞察是：在随机生成的 MOO 实例中，只有极少部分（1% - 12%）的 DD 节点能通向帕累托最优解（称为“帕累托节点”）。如果能提前识别并保留这些节点，即可大幅加速求解。

NOSHs 根据是否依赖训练数据及特征工程，分为三类：

2.1 基于规则的启发式 (Rule-based, NOSH-Rule)

• 原理：不依赖训练数据，利用问题的领域知识设计确定性规则。
• 机制：根据节点状态（State）的特定属性进行排序和截断。
  • 标量状态（如背包问题中的总重量）：按状态值大小排序（例如，保留重量较大的节点，因为可能包含更多物品）。
  • 集合状态（如集合 packing 问题中的可选物品集）：按集合基数（Cardinality）排序，保留可选物品更多的节点。
• 特点：计算成本极低，无需训练，但性能对问题实例结构敏感。

2.2 基于特征工程的机器学习 (Learning-based with Feature Engineering, NOSH-ML-FE)

• 原理：假设拥有大量带标签的训练实例（已知帕累托前沿），训练一个二分类器来预测节点是否为帕累托节点。
• 机制：
  1. 特征提取：人工设计特征向量 $\psi(s(u), l(u))$，包括实例属性（变量数、目标数）、层 - 变量特征（权重、目标值统计量）和状态特征。
  2. 模型训练：使用分类模型（如 XGBoost）学习参数 $\Theta$，输出节点属于帕累托节点的预测概率。
• 特点：比规则方法更灵活，能捕捉复杂模式，但依赖人工特征设计。

2.3 端到端深度学习 (End-to-End Deep Learning, NOSH-ML-E2E)

• 原理：为克服人工特征工程的局限性，提出一种通用的深度学习架构，直接从原始状态和层定义中学习节点评分。
• 架构（如图 3 所示）：
  1. 实例嵌入阶段（Instance Embedding）：
     • 目标聚合器 (Objective Aggregator)：使用 Deep Sets 处理目标函数，确保对目标顺序的不变性。
     • 变量编码器 (Variable Encoder)：利用图神经网络 (GNN)（具体为 Edge-augmented Graph Transformer, EGT）将 MOILP 建模为图，学习变量间的复杂依赖关系。此阶段每个实例只计算一次，避免冗余。
  2. 评分阶段（Scoring Phase）：
     • 结合预计算的变量嵌入与动态状态信息（已访问节点集合、当前城市）及层索引。
     • 通过评分头 (Scoring Head, MLP) 输出节点得分。
• 特点：表达能力最强，能自动学习复杂约束与目标间的依赖，适用于结构复杂的组合优化问题（如 TSP）。

3. 实验结果

作者在三个经典的多目标问题上进行了验证：多目标背包问题 (MOKP)、多目标集合打包问题 (MOSPP) 和 多目标旅行商问题 (MOTSP)。

3.1 主要性能指标

• 帕累托恢复率 (Cardinality)：恢复的真实帕累托解的比例。
• 精确度 (Precision)：找到的解中真正属于帕累托前沿的比例。
• 运行时间 (Time)：构建 DD 并枚举解的总时间。
• 逆世代距离 (IGD)：衡量近似前沿与真实前沿的距离（越低越好）。

3.2 关键发现

1. MOSPP (集合打包)：
   • NOSH-Rule 表现优异，在保持 85%-99% 帕累托恢复率的同时，实现了高达 11 倍 的加速（相比精确 DD）。
   • 对于大尺寸实例，精确方法常因内存不足失败，而受限 DD 方法依然有效。
2. MOKP (背包)：
   • NOSH-ML-FE (XGBoost) 优于规则方法，恢复率可达 88%-92%，精确度 92%-96%，且比精确方法快 1.75-2.33 倍。
   • 证明了结合人工特征与梯度提升树的有效性。
3. MOTSP (旅行商)：
   • 规则方法效果较差（恢复率接近 0），因为 TSP 状态结构复杂。
   • NOSH-ML-E2E (GNN) 表现卓越，恢复率 89%-91%，精确度 ~95%，IGD 极低，同时实现了 1.5-2.15 倍 的加速。
   • 证明了端到端深度学习在处理复杂图结构问题上的必要性。
4. 对比基线：
   • 与广泛使用的进化算法 NSGA-II 相比，NOSH 方法在求解质量和速度上均显著占优。NSGA-II 在处理整数变量和硬约束时表现不佳，难以找到可行解或高质量前沿。

4. 主要贡献

1. 首次应用受限 DD 于多目标优化：将受限 DD 从单目标领域扩展到多目标领域，提出了一种快速近似帕累托前沿的新范式。
2. 提出了 NOSH 框架：系统性地设计了从简单规则到端到端深度学习的三种节点选择策略，适应不同复杂度的问题。
3. 实证有效性：在三个基准问题上证明了该方法能在 2.5 倍 平均加速下，恢复 85% 以上 的帕累托前沿，且非帕累托解极少。
4. 开源代码：提供了完整的实现代码，促进了该领域的复现与进一步发展。

5. 意义与展望

• 实际意义：为决策者提供了一种在有限时间内获取高质量多目标决策方案的实用工具，解决了精确算法在大规模问题上“不可行”的痛点。
• 理论意义：展示了机器学习（特别是图神经网络）在指导组合优化搜索过程中的巨大潜力，证明了“学习如何剪枝”比“盲目剪枝”更有效。
• 未来工作：
  • 减少对完整帕累托前沿作为训练标签的依赖（目前训练需要精确解），探索利用部分前沿进行训练。
  • 将问题建模为结构化输出预测任务（直接预测帕累托子图），而非独立的节点分类。

总结：该论文通过结合决策图的结构化优势与机器学习的预测能力，成功解决了多目标整数规划中帕累托前沿计算昂贵的问题，为大规模多目标优化提供了一种高效、高质量的启发式解决方案。