Research map / Probabilistic and scientific modeling / Variational and generative sampling
Inverse Optimization Latent Variable Models for Learning Costs Applied to Route Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes IO-LVM, a latent variable model that learns a distribution over COP cost functions from observed solutions, decoding through a black-box solver (Dijkstra/TSP) and training with a perturbed Fenchel-Young gradient estimator.
Problem
Learning latent representations of structured solutions of constrained optimization problems with unknown costs, where VAE-style decoders fail to enforce feasibility and discrete solver outputs give zero gradients.
Approach
Replace the VAE reconstruction term with a perturbed Fenchel-Young loss through a black-box solver, so the latent space encodes costs rather than path geometry; decoded costs are passed through the solver so outputs are always feasible paths or cycles.
Key results
- On TSPLIB bayg29 (50 features), IO-LVM with k=10 reaches 31.9% full reconstruction match versus 3.4% for VAE (k=10).
- Path distribution prediction on Taxi: IO-LVM achieves D_JS 0.289 vs 0.599 for VAE and 0.439 for PO.
- On Ship data the VAE fails to converge (NC) while IO-LVM gets D_JS 0.141 and RMSE 0.96.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use solver-based IO-LVM reconstruction instead of VAE decoding | Hamiltonian-cycle reconstruction · TSPLIB test sets | full reconstruction match: 78.4 \pm \text{ 0.6} % -> 91.0 \pm \text{ 0.7} %; 46.0 \pm \text{ 1.6} % -> 77.1 \pm \text{ 1.5} %; 45.3 \pm \text{ 1.9} | Helped |
| use IO-LVM instead of the Euclidean-cost TSP baseline | Hamiltonian-cycle reconstruction · TSPLIB test sets | full reconstruction match: 9.0\% -> 91.0 \pm \text{ 0.7} %; 4.5\% -> 77.1 \pm \text{ 1.5} %; 1.3\% -> 78.3 \pm \text{ 1.1} %; 0.0 \% -> 31.9 \pm \t | Helped |
| model a latent distribution over costs with IO-LVM instead of using PO | path distribution prediction · Ship Data | D_JS: 0.164 \pm \text{ 0.007} -> 0.141 \pm \text{ 0.010} | Helped |
| model a latent distribution over costs with IO-LVM instead of using PO | path distribution prediction · Taxi Data | RMSE: 2.61 \pm \text{ 0.03} -> 1.56 \pm \text{ 0.10} | Helped |
| increase latent dimensions from 2 to 10 (ablation) | IO-LVM · TSPLIB test sets | edge recall: 0.950 \pm 0.007 -> 0.985 \pm 0.002; 0.883 \pm 0.013 -> 0.971 \pm 0.005; 0.810 \pm 0.009 -> 0.960 \pm 0.004; 0.723 \pm 0. | Helped |
| increase beta during training (ablation) | IO-LVM · Single S&T synthetic Waxman | number of distinct reconstructed paths | Hurt |
| increase beta during training (ablation) | IO-LVM · Single S&T synthetic Waxman | IoU | Hurt |
| use 10 latent dimensions instead of 2 (ablation) | VAE · TSPLIB test sets | full reconstruction match: 55.2 \pm \text{ 1.1} % -> 78.4 \pm \text{ 0.6} %; 15.4 \pm \text{ 1.3} % -> 46.0 \pm \text{ 1.6} %; 9.8 \pm \text{ 1.3} | Helped |
| increase latent dimensions from 2 to 10 (ablation) | IO-LVM · Ship Dataset | latent-space usefulness | No clear effect |
Surprising findings
- VAE reaches 100% edge recall on training sets with 10 latent dims but low full-cycle match, showing edge-level metrics overstate feasibility-aware quality.
- Increasing latent dimensions from 2 to 10 causes slight overfitting on TSPLIB, per the authors.
Limitations
- Limited to problems with fast solvers, since the solver is the training bottleneck.
- Additive perturbation proposition holds exactly only for equal-length solutions (Hamiltonian cycles); path applications rely on an approximation.
- Only tested on small graphs and a few datasets; 10 latent dims show slight overfitting.
Experimental setup
Datasets: Synthetic Waxman random graph Danish Maritime AIS ship data Cabspotting taxi trajectories TSPLIB95 burma14 and bayg29
Benchmarks: Synthetic Waxman paths Danish AIS ship paths Cabspotting taxi paths TSPLIB burma14 and bayg29
Metrics: full reconstruction match edge recall Jensen-Shannon divergence RMSE on edge usage outlier quantile score
Baselines: VAE Perturbed Optimizer (PO) Bayesian Optimization (BO) omega(y_E) Euclidean-cost TSP solution
Builds on: Fenchel-Young losses Variational Autoencoder Perturbed Optimizer beta-VAE
Closest papers by meaning
- Massively Scalable Inverse Reinforcement Learning in Google Maps (ICLR 2024 · similarity 0.86)
- Meta-Inverse Reinforcement Learning for Mean Field Games via Probabilistic Context Variables (AAAI 2024 · similarity 0.85)
- Conformal Inverse Optimization (NeurIPS 2024 · similarity 0.85)
- A Geometric Perspective on Reward Function Updates in Inverse Reinforcement Learning (NeurIPS 2026 · similarity 0.85)
- Provably Efficient Exploration in Inverse Constrained Reinforcement Learning (ICML 2025 · similarity 0.84)
- Recent Advancements in Inverse Reinforcement Learning (AAAI 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.