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

💡 一句话要点

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

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

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

📋 核心要点

  1. 现有方法在学习约束优化问题解的表示时，难以在解码过程中强制满足约束条件。
  2. IO-LVM通过学习成本函数的隐空间，并结合求解器在环路中进行优化，从而重建可行解。
  3. 实验表明，该方法能够重建路径和循环，预测其分布，并产生可解释的隐空间表示。

📝 摘要（中文）

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

🔬 方法详解

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

核心思路：论文的核心思路是构建一个逆优化隐变量模型（IO-LVM），该模型学习一个成本函数的隐空间，而不是直接学习解的表示。通过在隐空间中采样，并使用优化求解器根据采样的成本函数生成解，从而保证解的可行性。这种方法能够捕捉成本函数的分布，从而可以生成多样化的解。

技术框架：IO-LVM的整体框架包含以下几个主要模块：1) 编码器：将观测到的解编码到成本函数的隐空间。2) 隐空间：表示成本函数的分布。3) 解码器（求解器）：从隐空间采样成本函数，并使用优化求解器生成对应的解。4) 损失函数：使用Fenchel-Young损失来训练模型，该损失函数鼓励模型生成与观测到的解相似的解。

关键创新：IO-LVM的关键创新在于：1) 学习成本函数的分布，而不是单个成本函数，从而能够捕捉解的多样性。2) 将优化求解器集成到模型中，保证生成解的可行性。3) 使用Fenchel-Young损失，该损失函数允许使用非可微的确定性求解器进行训练。

关键设计：IO-LVM的关键设计包括：1) 编码器和解码器的网络结构选择，可以使用各种神经网络结构，如MLP或CNN。2) 隐空间的维度和分布选择，可以使用高斯分布或其他合适的分布。3) 优化求解器的选择，需要根据具体的COP选择合适的求解器。4) Fenchel-Young损失的计算，需要估计求解器的梯度，可以使用各种梯度估计方法。

📊 实验亮点

在船舶和出租车路线的真实数据集以及合成图上的实验表明，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.