Combinatorial Optimization Augmented Machine Learning

📄 arXiv: 2601.10583v1 📥 PDF

作者: Maximilian Schiffer, Heiko Hoppe, Yue Su, Louis Bouvier, Axel Parmentier

分类: cs.LG, math.OC

发布日期: 2026-01-15

💡 一句话要点

综述组合优化增强机器学习(COAML)，弥合预测模型与组合决策。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 组合优化 机器学习 数据驱动决策 运筹学 随机优化

📋 核心要点

  1. 传统机器学习方法在复杂决策问题中缺乏对约束的有效处理，导致方案可行性难以保证。
  2. COAML将组合优化嵌入机器学习流程，利用数据驱动的预测模型指导组合决策，同时保证解的可行性。
  3. 该综述提供COAML统一框架，并根据问题特性进行分类，总结算法和应用，为未来研究提供方向。

📝 摘要（中文）

组合优化增强机器学习(COAML)是近年来兴起的一种强大的范式，它将预测模型与组合决策相结合。通过将组合优化 oracle 嵌入到学习流程中，COAML 能够构建数据驱动且保持可行性的策略，从而桥接机器学习、运筹学和随机优化等领域的传统方法。本文全面概述了 COAML 的最新进展。我们介绍了一个统一的 COAML 流程框架，描述了其方法论构建块，并将它们与经验成本最小化联系起来。然后，我们根据不确定性和决策结构的形式，开发了一个问题设置的分类法。利用这个分类法，我们回顾了静态和动态问题的算法方法，调查了调度、车辆路径、随机规划和强化学习等领域的应用，并从经验成本最小化、模仿学习和强化学习等方面综合了方法论贡献。最后，我们确定了关键的研究前沿。本综述旨在作为该领域的入门教程，并作为组合优化和机器学习交叉领域未来研究的路线图。

🔬 方法详解

问题定义：论文旨在解决将机器学习模型与组合优化决策相结合的问题。现有方法要么忽略了组合优化的约束，导致不可行的解决方案，要么过度依赖人工设计的规则，缺乏数据驱动的适应性。

核心思路：论文的核心思路是将组合优化问题视为机器学习流程中的一个可学习的模块。通过将组合优化 oracle（即求解器）嵌入到学习流程中，可以利用数据来学习如何更好地做出组合决策，同时保证解的可行性。这种方法结合了机器学习的预测能力和组合优化的决策能力。

技术框架：COAML 的整体框架通常包含以下几个阶段：1) 数据收集和预处理；2) 预测模型训练，用于预测与组合优化问题相关的参数；3) 组合优化 oracle，利用预测的参数求解组合优化问题，生成决策方案；4) 损失函数设计，用于衡量决策方案的质量，并反向传播梯度以更新预测模型。这个流程可以迭代进行，不断优化预测模型和决策方案。

关键创新：COAML 的关键创新在于将组合优化问题视为一个可学习的模块，并将其嵌入到机器学习流程中。这使得可以利用数据来学习如何更好地做出组合决策，同时保证解的可行性。与传统的机器学习方法相比，COAML 能够更好地处理具有复杂约束的决策问题。

关键设计：关键设计包括：1) 如何选择合适的组合优化 oracle，例如线性规划求解器、整数规划求解器等；2) 如何设计损失函数，以衡量决策方案的质量，并反向传播梯度；3) 如何处理组合优化问题的不可微性，例如使用松弛技术或代理梯度等；4) 如何设计预测模型，以准确预测与组合优化问题相关的参数。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

该综述系统地总结了 COAML 领域的研究进展，并提出了一个统一的框架，有助于理解和比较不同的 COAML 方法。此外，该综述还对 COAML 的应用场景进行了广泛的调研，并指出了未来研究的潜在方向。虽然没有提供具体的实验数据，但该综述为研究人员提供了一个全面的 COAML 路线图。

🎯 应用场景

COAML 在诸多领域具有广泛的应用前景，包括调度、车辆路径、供应链管理、网络设计、资源分配等。通过结合数据驱动的预测和组合优化决策，COAML 可以提高决策效率、降低成本、优化资源利用，并为企业带来显著的经济效益。未来，COAML 有望在智慧城市、智能制造等领域发挥更大的作用。

📄 摘要（原文）

Combinatorial optimization augmented machine learning (COAML) has recently emerged as a powerful paradigm for integrating predictive models with combinatorial decision-making. By embedding combinatorial optimization oracles into learning pipelines, COAML enables the construction of policies that are both data-driven and feasibility-preserving, bridging the traditions of machine learning, operations research, and stochastic optimization. This paper provides a comprehensive overview of the state of the art in COAML. We introduce a unifying framework for COAML pipelines, describe their methodological building blocks, and formalize their connection to empirical cost minimization. We then develop a taxonomy of problem settings based on the form of uncertainty and decision structure. Using this taxonomy, we review algorithmic approaches for static and dynamic problems, survey applications across domains such as scheduling, vehicle routing, stochastic programming, and reinforcement learning, and synthesize methodological contributions in terms of empirical cost minimization, imitation learning, and reinforcement learning. Finally, we identify key research frontiers. This survey aims to serve both as a tutorial introduction to the field and as a roadmap for future research at the interface of combinatorial optimization and machine learning.