Inverse Optimization Latent Variable Models for Learning Costs Applied to Route Problems

📄 arXiv: 2509.15999v1 📥 PDF

作者: Alan A. Lahoud, Erik Schaffernicht, Johannes A. Stork

分类: cs.LG

发布日期: 2025-09-19

备注: Accepted at Neurips 2025

💡 一句话要点

提出逆优化隐变量模型，用于学习路径规划问题中的成本函数分布

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

关键词: 逆优化 隐变量模型 约束优化 路径规划 成本函数学习

📋 核心要点

  1. 现有方法在学习约束优化问题解的表示时，难以保证解码后的结构化输出满足约束条件。
  2. IO-LVM通过学习成本函数的隐空间，并结合优化求解器，实现可行解的重建，从而避免了直接解码结构化输出的难题。
  3. 实验表明，该方法在真实世界和合成数据集上均能有效重建路径和循环，并能预测其分布，生成可解释的隐空间表示。

📝 摘要（中文）

针对带约束优化问题（COP）未知成本函数的解表示学习难题，传统(变分)自编码器难以在解码结构化输出时强制满足约束，本文提出一种逆优化隐变量模型（IO-LVM）。该模型从观测解中学习COP成本函数的隐空间，并通过在环求解器解决COP来重建可行输出。我们的方法利用Fenchel-Young损失的估计梯度，通过非可微确定性求解器来塑造隐空间。与通常恢复单个或上下文相关成本函数的标准逆优化或逆强化学习方法不同，IO-LVM捕获成本函数的分布，从而能够识别来自不同智能体或训练过程中不可用条件产生的各种解决方案行为。我们在船舶和出租车路线的真实世界数据集以及合成图中的路径上验证了我们的方法，证明了其重建路径和循环、预测其分布以及产生可解释的潜在表示的能力。

🔬 方法详解

问题定义：论文旨在解决约束优化问题（COP）中，当成本函数未知时，如何学习解的有效表示的问题。现有方法，如变分自编码器，在解码结构化输出（例如路径）时，难以保证输出满足约束条件（例如路径的连通性、长度限制等）。此外，传统的逆优化方法通常只能恢复单个或上下文相关的成本函数，无法捕捉成本函数的多样性。

核心思路：论文的核心思路是学习一个成本函数的隐空间，而不是直接学习解的表示。通过将优化求解器嵌入到模型中，利用隐空间中的成本函数来生成解。这样，只要求解器能够保证输出满足约束，模型就能学习到满足约束的解的表示。此外，通过学习成本函数的分布，模型能够捕捉到不同智能体或条件下产生的多种解决方案行为。

技术框架：IO-LVM的整体框架包含以下几个主要模块：1) 编码器：将观测到的解编码到成本函数的隐空间中。2) 隐空间：表示成本函数的分布。3) 求解器：根据隐空间中采样的成本函数，求解COP，生成解。4) Fenchel-Young损失：用于训练模型，鼓励模型生成的解与观测到的解相似，并保证解的可行性。整个流程是，给定一个观测到的解，编码器将其映射到隐空间，然后从隐空间中采样一个成本函数，利用求解器求解COP，得到一个重建的解，最后计算重建解与观测解之间的Fenchel-Young损失，并利用梯度下降法更新模型参数。

关键创新：最重要的技术创新点在于将逆优化与隐变量模型相结合，通过学习成本函数的分布来表示解的多样性。与传统的逆优化方法相比，IO-LVM能够捕捉到不同智能体或条件下产生的多种解决方案行为。此外，该方法利用Fenchel-Young损失的估计梯度，通过非可微确定性求解器来塑造隐空间，避免了对求解器的可微性要求。

关键设计：论文中关键的设计包括：1) 使用变分自编码器作为编码器，学习成本函数的隐空间。2) 使用确定性求解器求解COP，保证解的可行性。3) 使用Fenchel-Young损失作为训练目标，鼓励模型生成的解与观测到的解相似。4) 使用梯度估计技术，处理非可微求解器带来的梯度反向传播问题。具体的网络结构和参数设置根据不同的应用场景进行调整。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，IO-LVM在船舶和出租车路线的真实世界数据集以及合成图中的路径上，能够有效地重建路径和循环，并能预测其分布。与基线方法相比，IO-LVM能够更好地捕捉到解的多样性，并生成更可解释的隐空间表示。具体的性能数据（例如重建误差、分布相似度等）在论文中进行了详细的展示和分析。

🎯 应用场景

该研究具有广泛的应用前景，例如：交通运输领域的路径规划、供应链管理中的资源分配、机器人领域的运动规划等。通过学习不同场景下的成本函数分布，可以更好地理解和预测智能体的行为，从而优化决策，提高效率。此外，该方法还可以用于生成对抗样本，评估优化算法的鲁棒性。

📄 摘要（原文）

Learning representations for solutions of constrained optimization problems (COPs) with unknown cost functions is challenging, as models like (Variational) Autoencoders struggle to enforce constraints when decoding structured outputs. We propose an Inverse Optimization Latent Variable Model (IO-LVM) that learns a latent space of COP cost functions from observed solutions and reconstructs feasible outputs by solving a COP with a solver in the loop. Our approach leverages estimated gradients of a Fenchel-Young loss through a non-differentiable deterministic solver to shape the latent space. Unlike standard Inverse Optimization or Inverse Reinforcement Learning methods, which typically recover a single or context-specific cost function, IO-LVM captures a distribution over cost functions, enabling the identification of diverse solution behaviors arising from different agents or conditions not available during the training process. We validate our method on real-world datasets of ship and taxi routes, as well as paths in synthetic graphs, demonstrating its ability to reconstruct paths and cycles, predict their distributions, and yield interpretable latent representations.