Inverse Optimization Latent Variable Models for Learning Costs Applied to Route Problems
Authors: Alan Lahoud
Erik Schaffernicht
Johannes A. Stork
Venue: NeurIPS 2025 poster ()
Keywords: inverse optimization
latent space
Primary area: general_machine_learning
TL;DR: Learning representations on a latent space from observed and structured solutions through a differentiable constrained optimization problem

Abstract: 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.

Inverse Optimization Latent Variable Models for Learning Costs Applied to Route Problems
Alan Lahoud! Erik Schaffernicht"
Johannes Stork'
Centee of Applied Autonomous Sensor Systems (AASS), Örebro University
(alan lahoud, johannesandreas stork)
2 Technology Transfer Center Kitzingen, Technical University of Applied Sciences Würzburg-Schwer erik. schaf frriierriiee cht@thus.de
Abstract
Learning representations for solutions constrained optimization problems (COPs) with unknown cost functions is challenging, models like (Variational) Autoen- coders struggle to enforce constraints when decoding structured outputs. We propose 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 solver in the loop. Our approach leverages estimated gradients of a Fenchel- Young loss through non-diffcrentiable deter- ministic 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 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 dis- tributions, and yield interpretable latent representations. The code is available at https://gii thub. com AlaaaaooddIOO-WWW
Introduction
When learning latent generative representations, is often necessary for inferred samples to satisfy specific constraints, such as forming paths in a graph between designated start and target nodes, consistent with the feasible of an associated constrained optimization problem (COP). A major challenge is learning such models when the feasible set of solutions is discrete, as the gradients of these solutions with respect to the model parameters are zero almost everywhere, and therefore mon-informative [I] In this paper, we pose this problem as learning latent cost representation of the COP from observed solutions.
State-of-the-arr approaches for recovering underlying cost functions of COPs from observed solutions, e.g., structured decisions performed by agents, primarily address the non-informative gradient problem by either smoothing solver operations
[21), interpolating COP solutions 228, perturbing the COP cost [7). or relaxing the COP [39] to match statistics of the observed behavior (i.e., solutions). However. these methods assume a single underlying cost, making them unable to directly learn from data of multiple different agents with different underlying cost functions. To correctly learn from real world data containing behavior from different agents, they require supervision through agent labels.
In this paper, introduce IO-LVM, novel approach for learning latent representations of COP costs that can recover observed COP solutions, specifically for route problems in graphs. Our approach
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

does not assume single underlying COP cost, allowing it to learn effectively even when multiple agents or context are represented in the data without labels. Similar to Variational Autoencoder (VAE) [8] we use amortized inference and map into meaningful and interpretable low-dimensional latent cost space. contrast of ordinary VAEs, we guarantee that samples fulfill requirements of the feasible set (e.g.. connected paths) by using black-box COP solver in the generative step. To address non-informative gradient challenge posed by discrete solutions, we employ a gradient estimation technique based on perturbing the input of the black-box solver and the Fenchel- Young loss 7 g)
Applied to path and route data, we can use IO-LVM to, e.g., generate new paths by selecting a latent cost and providing source and target nodes to the black- box solver, which ensures validity of the path. This allows us to infer how different agents would navigate between new source and target nodes, As the IO-LVM learns costs instead of the shape/ / geometry of solutions, a low-dimensional latent representation often sufficient, offering easy interpretation and analysis such as clustering similar COP costs, denoising observed paths by finding a small number of representative paths, and detecting outliers and deviating behavior.
We state our contributions as follows: i) We introduce IO-LVM, a method that combines variational approximation techniques with COP solver gradient estimation to learn latent representations for the underlying costs of COPs based on observed decisions; ii) IO-LVM naturally constructs meaningful and interpretable latent space, allowing for the reconstruction of observed path distributions without making assumptions about the distribution of inferred paths. Notably, the ability to recover distinct (e.g., multimodal) representations for the underlying costs enables the modeling of different agents making decisions; iii) We demonstrate the versatility of IO-LVM M using both synthetic and real-world datasets, highlighting its potential for path analysis tasks such as naturally separating underlying costs into meaningful groups, reconstructing or denoising observed paths, and predicting paths for unseen start and target nodes. Our aim is not only to provide quantitative results but also to offer insights through visualizations of routes and latent variables.
1.1 Related Work
Obtaining useful gradients through optimizers for end-to-end learning is challenging and previous works focussed on convex solvers 3 ( and linear or quadratic programs [1] 36.. However, these methods are mainly limited to continuous COP formulations and are difficult to extend to combinatorial problems such as the graph-based problems in work with the non-informative gradients. More related to our work are efforts to differentiate through dynamic programming algorithms, such dynamic programming differentiability [22), or more specifically, a differentiable version of the Floyd- Warshall algorithm to learn from observed paths in graphs 21]. Different to our work, their approach struggles with scalability as graph size increases.
Learning cost parameters from observed solutions is also done by Inverse Optimization 4 32 33 Inverse Reinforcement Learning, and Inverse Path Planning [37
21). Here, cost parameters are either 24 or non-linear [3] 37 12 and often learned with end-to-end
global (2T). linear 223 38 39
gradient estimation by exploiting insight in the underlying optimization process or in some cases assuming a black box optimizer (29 Z In the later case, the Fenchel-Youus loss, also used in this paper, has been demonstrated as suitable way to match inferred and observed paths within smooth and convex space 77. Different to us, these methods typically assume a single underlying cost function condition the cost on given context, which may not capture the diversity of agent behaviors present in real-world scenarios.
Autoencoders 17 and Variational Autoencoders (VAEs) 18 are often used to learn lower- dimensional representations of data and there have been attempts to simplify solving COPs by learning better representations of the feasible solutions 6 However, we observe in our work that VAFs do not reliable generate feasible solutions complex route problems like TSP and shortest path. In contrast to VAE, IO-LVM uses COP solver in the decoding step and thereby guarantees that generated samples are feasible solutions.
2 Preliminaries
Below, we recap the Evidence Lower Bound (ELBO) for deep latent variable models and introduce Fenchel-Youe Young losses which are both fundamental for our approach.

---

Evidence Lower Bound (ELBO). The objective in latent variable models is to identify the latent variables that best explain the observed data x. However, it well-known that directly computing the posterior P(z x) is generally intractable. To address this, a variational distribution 2o(2 x) is
introduced and learned with lower bound objective (ELBO) 18 31. The ELBOO makes a trade-off'
between accurately reconstructing the input data (the expected log-likelihood) using a model po(x z)
and adhering to the prior distribution P(z) for the latent variables, i.e.,
1(0, o) = - (x(x)) [oggpo( | x)] + 3.x.. (go(2 x) P(z))
(1)
where is Kullback-
(KL) divergence and /3 is a balance factor I6 9. In our approach
detailed in Sec. 3] we also use a learned qø (encoder), but replace the usual reconstruction loss with a
Fenchel-Young loss (see below).
Fenchel- Young Losses Fenchel- Young losses are versatile class of loss functions derived from convex duality theory, specifically leveraging Fenchel conjugates g 7 5 These losses generalize several common loss functions used in structured prediction tasks, such cross-entropy and hinge losses, by formulating the learning problem as a regularized prediction task [8. Fenchel- Young p
losses are defined (y x) C (y) + !xx) (y,x), x), where 12(x) is a chosen regularization function, f2 is its conjugate, and () represents the inner product between two vectors. In our context, x represents decision vector (e.g., a structured output), and y a cost vector; the loss measures how suboptimal x is under the cost structure implied by y. and is minimized when x is the optimal decision under y and regularizer ?2
3 Inverse Optimization Latent Variable Model
In this section, we introduce the notations and problem definition, present IO-LVM in general COP setting (Sec. 3.1), and discuss assumptions for path and cycle applications (Sec. 3.2
Notation and Problem Definition. Our dataset D = {xx; pi) consists of structured decision vectors x; E X' in a constrained space X, e.g.. connected paths performed by agents in a graph, and corresponding problem requirements p; E P. e-g., start and target nodes for the path. We denote by w a black-box box solver for the COP that takes cost vectors y; and problem requirements p; to output an optimal COP solution &; = w(y:, p:). where the COP solved by w is defined as argmin x (Y., x) which, although formulated with linear costs, can represent wide variety of COPs, specially combinatorial ones [20). The main goal is to model a low-dimensional representation of COP costs y; y that leads to the observed decision vectors from D. Concretely, we aim to estimate the posterior distribution P(z x), where z E Z C R* is a latent vector in space of dimension k.
3.1 10-LVM Description and Learning
We learn latent representation Z with amortized inference 19
using a nonlinear mapping do to map samples X; to the latent space 2, and then reconstruct them back to the constrained space X, similar VAE. Different from VAE models, where reconstruction is done by a decoder network, our reconstruction is non-trivial due to the constraints the COP solution space X. E.g., X' contains valid paths between specific nodes a graph. To achieve this, we define our reconstruction as a composition of functions 9e: 2 - y and w: y x P + X, where the former is a nonlinear map parameterized by f, and the latter is a solver that is potentially non-differemtiable. This sequence of transformations visualized in Fig. [
To learn our IO-LVM, we adapt the VAE's ELBO objective by changing the reconstruction loss (first term) of Eq. ①I. We introduce the solver and suitable distance measure d in X' resulting in the w(y" p))]. where yd == (z)... In contrast to VAE models, the black box solver in our reconstruction generally prohibits end-to-end learning with common loss such as the Mean Squared Error. For this reason, we use the Renchel-Young loss for d by inducing perturbations the input space of the COP. Consequently, our loss function is defined as:
term E. (xix) d(x
[(0,0) Φ) = Egg [4r ( x) + 3LL (z|x) P(z)).
By choosing Ω (in 4Fy) to be the conjugate of E. [minxex (y + E, x)], we rewrite (brief derivation in Appendix A) (py as
xx) = (y,x) x) - Eg [min (y - e, x)].
(3)
xEX
3

---

Reconstruction
Constrained Space
Latent Space
Unconstrained Space
Constrained Space
X
X
9
ge
w
Figure 1: IO-LVM during learning: structured data is mapped from X' to latent space 2, then reconstructed in two steps: to unconstrained space V, and y to constrained space X' by solver w.
The second term corresponds to the expected optimal cost under random perturbations of the cost vector y. In Proposition (see below). we justify this choice in the context of our problem setting by showing that, under mild conditions on the perturbation distribution &, this formulation ensures that no solution is priori favoured by the noise or problem structure, and solutions with the same cost impact gradients with the same probability. Specifically, we assume that the components of ~ & are independent, zero-mean, and identically distributed with finite variance, and that & is closed under convolution, c.g., Gaussian noise. In this case, the Mrnchel-Young loss gradient with respect to y-elements is analytically computed as Vydfy (y, x) = x - &c, where & w(y + e), minimizing the Fenchel- Young loss if and only if & [7]] This allows us to obtain gradient estimates w.r.t. the weights 8, as the chain of gradients in the reconstruction block can now be written as
0y
Velfy (y x)
x²) 00
where x w(y" + e). Estimating the gradients in Eq. 4 is generally done in Monte Carlo fashion, which is expensive due the need of running the solver w several times. To avoid this, we use the property of expectation linearity to rewrite the reconstruction loss in Eq. (3) as
(xlx) Ee [[ x) - (y" + wy +))]]
(5)
highlighting that the estimator unbiased with a double expectation. This result allows us to use stochastic gradient descent (SGD) method to learn 0 and o, as described in Alg. [ By leveraging SGD, the solver runs once (rather than several times in Monte Carlo fashion) per data sample during training, reducing the computational cost per iteration.
Algorithm details. The algorithm details the steps in the training pro- cess using an encoder hs model (o(z x), and a mapping ga- Note that in step 1, the problem requirement sample can be leveraged into the en- coder as additional information. Step 2 samples the latent value using the VAE re- re-parametrization trick [19]. In step 3, we include a transformation & ensure that costs yd fits to COP in- put space ) It is common that some COPs require their cost elements be positive, for instance, which is gener- ally fixed by ordinary activation func- tions Φ. In step 4, we compute the COP solution given an inferred and perturbed cost. In step 6, the back-propagation is allowed due to the gradient estimator described in Eq. (4), bridging the gap of the non-differentiable COP solver.
Algorithm One epoch of IO-LVM training process.
1: Components:
-Encoder h&; Decoder go-
Input: Dataset = {(x, p:)
4: Output: Trained model parameters
for each sample (x, p)
do
6: Step 1: Encoding: (n. = hx
Step Sample z: 2 = μ o C.
8:
Step 3: Map to COP cost space: yd (g)(
9:
Step Solve the COP using w, p and the inferred
cost y x! ww + p). where ~ N.
10:
Step 5: Compute the loss as Eq. (2)
11:
Step 6: Update the encoder and decoder parameters
(ò. 0) allowed by Eq. (4).
12: end for
3.2 10-LVM Assumptions and Applications
We assume that the observed structured decision samples in D presented in Sec. Jrr optimal COP solutions, e.g., the taxi drivers solve a shortest path problem under their own underlying cost values. Therefore, the variations in the observed structured decision samples arises from differences in

---

Selecting a proper 3 during the training process is not only useful to mitigate the issue of posterior collapse avoid overfitting in B- 3-VAEs (34), but in our path at inference time, i.c., remove uncommon patters in the observed test path by encoding it through valuations of COP costs. Below, we describe how we model the two problem domains used in experiments in Sec.
Path Planning. For a fixed directed graph with edge set E, we can model a set of paths as a set of binary vectors X' S {0, 131ر1 corresponding to edge usage. Here, D contains samples of paths 'in the graph. In this case, common path requirement is {p (s, t) | s, V. & t), defining start and target nodes those paths. In this scenario, we assume there is an underlying set of edges costs for each data sample such that Shortest Path Problem (SPP) solver (e.g.. Dijkstra) recovers the observed paths.
Hamiltonian Cycles. For a fixed, either directed or undirected graph, with edge set E, we can model a set of cycles also as a set of binary vectors X' C {0, - corresponding to edge usage. Here, DD contains samples of Hamiltonian cycles in the graph. We assume that there is an underlying set of edge costs for each data sample such that a Traveling Salesman Problem (TSP) solver recovers the observed cycle. Although path requirements could be added, we consider null set in our experiments.
Proposition 1. Suppose all feasible routes x E X have equal length, i.e., the same number of edges. Let e E |R be random perturbation vector with independent, zero-mean components, each with identical variance o². Then, the perturbed cost vector y te induces a distribution over X in which all solution costs have equal expected value and equal variance, preventing bias toward specific solution in X after perturbation, and paths with the same cost impact gradients with the same probability.
This condition holds exactly for Hamiltonian cycles, where all feasible solutions have the same length by definition, and serves as a reasonable approximation in our real-world path planning applications, where the graph is embedded in space with relatively uniform node spacing and no significant shorteuts. Therefore, the corresponding Fenchel- Young loss chosen in [ defined via the additive perturbation, is good choice for both experimental settings. When this is not the case, alternative perturbation methods would be required. A proof for Proposition is provided in Appendix B
Note that in both applications, as in general discrete problems, the COP can be formulated with linear objective [20]: argminxxx* (y, x)). fulfilling the requirement for the gradient estimator. Importantly, as in other works in structured prediction 77 21, IO-LVM is limited to problems for which fast solvers w exist, since the solvers are the computational bottleneck of the training process.
3.3 1O-LVM Inference Tasks
Once the IO-LVM training process is complete, we can perform inference tasks in the above appli- cations. IO-LVM allows reconstructing paths from parts of the dow-dimensional latent space using again, as in the training step, a composition of the learned decoder and the solver, i.e., .(go) and w()). allowing to observe different patterns reconstructed in the path space. By fitting kernel density estimation (KDE) into the low-dimensional learned latent space, we can sample latent values and generate paths mentioned above, leading to inferred path distribution.
can also be useful to denoise test
the learned h(Φ) and decoding it using ((go) and w()). In similar direction, similarity metrics between a test path x and inferred paths from IO-LVM can also be used to detect x is an outlier.
Experiments
The experiments focus route problems in graphs using w Dijkstra and TSP solver for path planning and Hamiltonian cycles assumptions, respectively, as described in Sec. 3.2 Details of the 10-LVM training process are provided in Appendix F We use four different datasets to evaluate 10-LVM in tasks like route reconstruction, path distribution prediction, facilitation to latent space analysis, and its potential for unsupervised learning tasks such anomaly detection and denoising. The datasets used in the experiments are presented below, while further details are described in Appendix
S.2.
A) Synthetic Waxman Random Graph. We generate a Waxman graph 35 with 700 nodes and 7230 edges; with three different cost functions for the edges costs y, all of them the basis of
5

---

nonlinear function from unobserved features. We increased the costs of southern edges for agent 1 and of northern edges for agent 3, while agent was unbiased in terms of south/north edges (in Fig. and S] is possible to observe those preferences). We solved the SPP using Dijsktra for each agent cost multiple times on the basis of the generated edges costs plus a Gaussian noise, i.e., wy + 6), to generate multiple paths to 'D. These paths are generated in two manners, one set with a single source-target pair (Single S&T), and another set with multiple pairs (Mult. S&T). In both cases, 6000 paths were generated, which 5000 were used for training.
B) Ships Dataset. Using Automatic Identification System (AIS) data from the Danish Maritime Authority [IO], we use ship locations collected during three months. We project the locations to grid graph with 2513 nodes and 8924 edges, resulting in a set of 2500 paths with different start and larget nodes, where 2,000 were used for training.
C) Taxi Dataset. We use the Cabspotting dataset (27, which contains real-world taxi trajectories in the city of San Francisco, following a preprocessing approach to build a graph based on the available trajectories [2I] Unlike the original setup, we increase the number of nodes and edges 1125 and 8022 to better reflect the realism of the actual trajectories, resulting in 101344 trajectories.
D) TSPLIB. From TSPLIB95 [30], we use burmal4 (14 nodes, 91 edges) and bayg29 (29 nodes, 406 edges) graphs. Actual (underlying) edges costs y are generated using a nonlinear function incorporating unobserved features and Euclidean distances between nodes offset. We create two versions for each graph, one using 3 unobserved features and another using 50 unobserved features. 3000 actual Hamiltonian Cycles (2400 for training) are generated with a TSP solver w using the underlying costs y as input.
4.1 Qualitative Latent Space Analysis
In this section, we analyze the learned latent space Z. The goal is to observe that paths generated by similar costs (e.g., coming from the same agent or similar context) are encoded close to each other in latent space after IO-LVM training. We also analyze how structure in the latent space influences reconstruction by sampling latent values and observing corresponding inferred routes.
Additional results of latent space analysis using the Taxi and TSPLIB datasets are reported in
Appendix
Synthetic Waxman Paths. Fig. 2 shows the learned two- dimensional latent space for the Mult S&T dataset. The colors represent the agent that executed each path. Importantly, the agent identity was not provided during training. We observe that 10-LVM successfully disentan- gles the factors associated with the costs of the three different agents. For example, Agent (red) follows several distinct paths with different start and target nodes, yet these paths are consistently mapped common region in the latent space, reflecting their shared underlying transition costs, that is, avoid southern edges when possible. In contrast, the VAE latent space fails to exhibit this structure: paths performed by the red agent are spread in different locations of the latent space. This suggests that VAEs are unable to disentangle the transition
Simb: suparited undstlying stata
Encoding pamts
ID-LVW
Space
1.00
Agents
Coordinate
Agent
Apert
0.00
-0225
VAE
Space
0050
Agents
Agent
-0.75
Agent
-1.00
-1.0
-0.5
0.0
0.5
1.0
X Coordinate
Agants
Encoding paths
suparatedd undestyrng c0s3
Dataset (Mult. S&T) of paths from 3 agents (blue, red, green) with different underlying costs (+ noise). Right: Learned 2D latent spaces of IO-LVM (top) and VAE (bottom). IO-IVM groups data by cost while VAE groups data by path geometry.
Figure 2: Left:

---

cost structure inherent in the data. Illustrations of path reconstruction from different regions of the latent space are presented in Appendix [
Ship Paths. The top-left chart in Fig. 3 illlstrates the 2D latent space (3D latent space results are seen
in Fig. 12 in the Appendix). Each hexagon in the right chart of Fig. correspoods to subspace of the latent space. For each hexagon, the average of the ships' width is plotted in color. Larger ships are less frequently found in the top-right corner of the latent space, leading a low average ship width in that region. This is another example that IO-LVM was capable to capture unobserved factors within the la- tent space, i.e., the ship width information (provided by AIS) was not used during the training process.
We also analyze the reconstruc- tion process through this dataset by sampling 20 latent values from Gaussians in the latent space and then computing the re- spective edges costs and paths.
Eomeia Do
Encoeding ship palls
Secochig pachi
As seen in the right part of Fig,
3 neighbor latent values share
Oreanre
high number of edges in the
graph (e.g.. many path samples the same). Moreover, in- teresting pattern emerges: some regions of the latent space con- taining wider ships avoid the Ore- sund Strait when traveling from the east to the north part of Den- mark even though is the short- est path in terms of euclidean dis- tance, as observed in the second column of the figure where ships prefer going through the Great Belt.
QIOM BAA
Figure 3: A) Ship paths (bottom-left chart in black) are encoded the latent space using do (top-left chart). Colors in the latent space represent the average ship width in each hexagon. B) Costs are sampled from Gaussians in the latent space (three top-right graphs), and respective paths are inferred given hypothetical (non-existent in training paths) pair of start and target nodes (three bottom-right graphs).
4.2 Validating IO-LVM Reconstruction Quality
Table 1: Reported are the percentage of full reconstruction match (i.e., the reconstructed cycle matches perfectly with the target) calculated on the test set.
Dataset Methods
w(yE)
VAE
VAE (k = 10)
1O-LVM (k: = 2)
1O-LVM (k = 10)
(k = 2)
burmal4 14 (3 feats.)
9.0%
55.2 1 1.1%
78.4 1 0.6%
82.7 1 1.3%
91.0 - 0.7%
bayg29 (3 feats.)
4.5%
15.4 1 1.3%
46.0 1 1.6%
37.3 1 7.3%
77.1 1 1.5%
burmal4 (50 feats.)
1.3%
9.8 1 1.3%
45.3 1 19%
29.6 26%
78.3 - 1.1%
bayg29 (50 feats.)
0.0%
0.2 0.1%
3.4
1.5%
31.9 - 3.5%
We evaluate reconstruction performance by compar- ing if the inferred output perfectly match the observed path (input to the encoder) with low latent dimensions on the TSPLIB datasets. Note that the task of recon- structing a perfect Hamiltonian cycle is challenging, since there are 13! sz 6 10 possible Hamiltonian cycles for the burmal4 dataset and 28! RJ 3 * 1029 for
Table 2:
Reconstruction match calculated on the test set varying the training size for bayg29 with 50 features.
Methods Train. size
1000
10000
VAE (k: = 10)
0.8%
11.8%
VAE (k- = 100)
1.3%
30.2%
the bayg29, Results reported in Table T demonstratess that 10-LVM consistently outperforms VAE due to its structured reconstruction process. As naive reference, we include the w(ye), ), a non learning baseline where the TSP solution is computed using edge costs defined as the Euclidean distances between node positions. Although VAËS demonstrate to have good performance when the recon- struction is measured by edge mulching instead of full reconstruction, as show in Table (Appendix F}. they do not guarantee feasible outputs with respect to the COP, leading to worse results a full match comparison. Also, results in Table 2 shows that even by increasing the latent dimension of
10-LVM (k = 10)
20.8%
58.3%
7

---

VAEs, they are still far from the reconstruction power of IO-LVMS for the most challenging dataset (bayg29 with 50 features). The gap even higher when the number of training samples are smaller, Additional results on the variation of the number of latent dimensions are
as also shown in Table 2
provided in Appendix E
Sarada (Vbbic burmalf)
Samcie 1Vd and burrald)
Sumppir DABE and burmaz)))
Sample (olld buwe20
Samiie (1old buvs220
Sario (ViB sut bunys22
vog (dinded)
Edges correctyy reconstructed
Edges correctly reconetuctedd
Figure 4: Each column illustrates an inferred sample for the Hamiltonian eycles experiment using VAE (top) and IO-LVM (bottom) the first three samples of each dataset generated with 50 features. Green edges denote correct reconstructions relative to groundtruths, while red edges indicate false positives. VAEs might yield unstructured outputs. Groundtruths and other bascline results are available in the Appendix
Figure
Fig. illurratess some reconstructed samples of IO-LVM against VAE, where the decoder outputs paths binary edge usage indicators (i.e., probabilities converted to binary). In the figure, thick edges illustrate the reconstructed paths for the first three test samples of each dataset (burmal4 14 and bayg29 created with 50 features). It can be seen from the figure that, different from VAEs, IO-LVM ensures that the output forms a valid Hamiltonian cycle due to the inclusion of a TSP solver in its processing loop. This happens even when the reconstruction is not fully correct (e.g., most right graph in in Fig.
Effect of varying 3: Reconstruction versus Denoising We analyze the effect of varying 3 on two metrics in the Single S&T synthetic Waxman dataset: i) the number of distinet paths reconstructed by the decoder using the test dataset; ii) and the Intersection over Union (IoU) metric between observed and inferred edges usage during training. Figure 5 shows that as B increases, the number of distinct paths decreases, indicating a denoising effect due to the diminished influence of the recon- struction loss. This results in the decoder re- ducing diversity of generated paths due to the posterior collapse. The loU decreases with larger 8, also reflecting reduction recon- struction power. In Figure [ (Appendix E we show a projection of noisy real-world taxi paths into similar but expected paths by recon- structing them using IO-LVM.
Recarstucton B- 0.1
Donating
B
8 10
Lobent 2imerston2
0.00
Latert Dimretaion 1
Conntraate
3.0
65
00
05
1.0
3.0
05
33
055
19
1.0
035
28
83
Agem:
Agent:
Agonc
Figure 5: Lower 3 yields more distinct paths recon- structed by IO-LVM, while balanced or higher increases denoising.
4.3 Inference Results
Path Distribution Prediction. To measure the prediction quality of the overall test paths distribution, we used a kernel density estimator (KDE) in the learned latent space to estimate its probability density function and sample latent values from it. We evaluate the quality of predicted path distributions using two metrics: lensen-Shannon divergence (Dıs, lower is better) and root mean squared error (RMSE, lower is better), both computed on edge usage frequencies between predicted and ground truth paths given fixed start and target nodes. For the Ship and Taxi datasets, these nodes are selected as the most frequent pairs in the data ensure consistency in comparisons at inference time. Path
8

---

Table 3: Results on the prediction of paths distribution. Average and standard deviation of DJs and RMSE on edges usage over 20 runs are reported. NC denotes no convergence.
Single S&T
Ship Data
Taxi Data
Method
Dis
RMSE
D1s
RMSE
D1s
RMSE
BO
0.777 + 0.040
3.678 + 0.299
0.795 + 0.011
6,44 + 0.07
0.707 + 0.037
5.70 = 0.09
PO
0.058 + 0.008
0.218 + 0.063
0.164 + 0.007
1.18 + 0.06
0.439 + 0.003
2.61 + 0.03
VAF
0.060 + 0.005
0.177 + 0.067
NC
NC
0.599 + 0.020
3.44
10-LVM
0.054 + 0.003
0.151 + 0.034
0.141 + 0.010
0.96 + 0.11
0.289 + 0.008
1.56 + 0.10
samples for the VAE and IO-LVM are obtained using KDE samples from their latent spaces, inferring their corresponding edges costs y", and solving Dijkstra on them, i.e., w(y"). We also compare the results against two other baselines: the Perturbed Optimizer (PO) baseline 7. which estimates gradients for structured prediction without modeling a latent space. We adapt PO to our setting by removing contextual inputs and reintroducing the training-time noise at inference to sample paths as w(y" + +); and naive BO baseline, where we minimize RMSE w(y + + BB)) through Bayesian Optimization where the distribution variance from which e is sampled is a single decision variable. Results in Table 3 show that IO-LVM outperforms VAE, which fails to model constraints under limited data, c.g., in the Ship dataset, the sparse path count relative to the graph size prevented convergence (NC). IO-LVM also outperforms PO, whose naive sampling, i.e., w(y" + E). fails to capture some characteristics of the true path distribution. The resulting inferred path distribution by IO-LVM of the Taxi dataset is illustrated with the blue paths of Figure O (top-left chart), and can be compared with the green observed paths in the test dataset with the same pairs of start and target nodes (top-mid chart).
Outlier Detection. We generate two path outliers in the taxi dataset illus- trated in the top-right chart of Fig. 6 one by using Dijsktra considering edge costs as Euclidean distances between nodes (purple path), and the other solving Dijkstra on learned costs but removing edges in latitude/longitude box, enforcing deviation (red path). To analyze if each of the observed paths (greens) and each of the outlier paths are actually outliers, we compute a low 7-th quantile Q (c.g.. a distance measured between this test path x and the path distribution using inferred samples x² by IO-LVM, i.e.,
Freq. of sampled paths Freq. 50 observed paths
Outlier path Created
Outlier path Creazed edges region
Target node:
aucikian
(Urion Square)
to of
0.02) of
Qi~zld(x x* (z))], score reflecting how far each observed path lies from most of the paths in the inferred distri- bution. Although alternative distances d could be chosen, we compute d the RMSE between the cost of those paths by sampling N edges from the learned latent space, i.c., d = RMSE ([(x, y [x*), > This distance reflects how far two paths are from each other when projected on learned costs. A high quantile score Q' suggests that the path is unlikely under the inferred path distribution and therefore anomalous. We compute this score Q" for each path in the data
Stert mode
(Aurpott
Outler 2
Q
Outlier 1 120 1274
100
25.2
81.8
01.9
50
Figure 6: Taxi paths from fixed start (airport region) and target (union square) nodes. Frequency of inferred paths by IO-LVM (blue), observed paths (green), and outlier paths (purple, red). Plots are generated with Open Street Map 25 Quantile scores Q:=000 (d(x, x² (2))) for test paths x are reported for outlier detection.
9

---

(green) and the created outliers (purple and red) for r 0.02. Results showing higher scores for outlier paths are reported in the bottom graphs of Fig. 6 and could also indicate the existence of other potential outliers in the test dataset (green bars).
5
Conclusion
This paper proposed IO-LVM, a novel approach for learning latent representations of COP costs, specifically for paths and cycles in graphs. The method leverages amortized inference and integrates black-box solvers within a probabilistic framework, allowing for the modeling multiple agents and diverse behaviors in graphs. By employing Fenchel- loss with perturbed inputs, it overcomes the gradient challenges in optimizing COPs, ensuring feasible and interpretable path reconstructions. The learned latent space captures meaningful structures, highlighting the model's characteristic to distinct agent behaviors, while maintaining accurate path reconstruction and prediction. Our method description valid for a general set of COPs if gradient estimation is available.
Acknowledgments and Disclosure of Funding
This work has been supported by the Industrial Graduate School Collaborative Al & Robotics funded by the Swedish Knowledge Foundation Dnr:20190128, and the Knut and Alice Wallenberg Foundation through Wallenberg AI, Autonomous Systems and Software Program (WASP).
References
[1] Ahmed Abbas and Paul Swoboda. Combinatorial optimization for panoptic segmentation: A fully differentiable approach. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, Curran Associates, Inc., 2021.
pages 15635-15649.
[2] Akshay Agrawal, Shane Barrat, Stephen Boyd, Enzo Busseti, and Walaa M Mousri. Dif- ferentiating through cone program. Journal of Applied & Numerical Optimization, 1(2). 2019.
[3] Brandon Amos and J. Zico Kolter. OptNet: Differentiable optimization layer in neural networks. Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 136-145. PMLR, 06-11 Aug 2017.
[4] Anil Aswani, Zuo-Jun Shen, and Auyon Siddiq. Inverse optimization with noisy data. Opera- lions Research, 66(3):870-89) 2018.
[5] Han Bao and Masashi Sugiyama. Fenchel-young losses with skewed entropies for class- cass-posterior probability estimation. In International Conference Artificial Intelligence and Statistics, pages 1648-1656. PMLR, 2021.
[6] Peter Bentley, Soo Ling Lim, Adam Gaier, and Linh Tran. Coil: Constrained optimization in learned latent space: Learning representations for valid solutions. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pages 1870-1877, 2022.
[7] Quentin Berthet, Mathieu Blondel, Olivier Teboul, Marco Cuturi, Jean- Sean-Philippe Vert, and Francis Bach. Learning with differentiable pertubed optimizers. Advances neural information processing systems, 33:9508 111999999911 2020.
[8] Mathieu Blondel, André FT Martins, and Vlad Niculae. Learning with fenchel-young losses. Journal of Machine Learning Research, 21(35): 2020.
[9] Christopher P Burgess, Irina Higgins, Arka Pal, Loic Matthey, Nick Watters, Guillaume Des- jardins, and Alexander Lerchner. Understanding disentangling in beta-vae. arXiv preprint 180iv:1804.00 03599, 2018.
[10] Danish Maritime Authority. Ais data, 2020. Accessed: 2024-08-01.
10

---

[11] Priya Donti, Brandon Amos, and Zico Kolter. Task-based end-to-end model learning in stochastic optimization. Advances neural information processing systems, 30, 2017.
[12] Tharindu Fernando, Simon Demman, Sridha Sridharan, and Clinton Fookes. Deep inverse reinforcement learning for behavior prediction in autonomous driving: Accurate forecasts of vehicle motion. IEEE Signal Processing Magazine, 38(1):87-93) 2020.
[13] Chelsea Finn, Sergey Levine, and Pieter Abbeel. Guided cost learning: Deep inverse optimal control via policy optimization. In International conference on machine learning, pages 49-58. PMLR, 2016.
[14] Vincent Furnon and Laurent Perron. Or-tools routing library.
[15] Arie Hagberg, Pieter Swart, and Daniel S Chult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab.(LAN)), Los Alamos, NM (United States), 2008
[16] Irina Higgins, Loic Matthey, Arka Pal, Christopher P Burgess, Xavier Glorot, Matthew M Botvinick, Shakir Mohamed, and Alexander Lerchner. beta-vae: Learning basic visual concepts with constrained variational framework. ICLR, 3, 2017.
[17] Geoffrey E Hinton and Ruslan R Salakhutdinov. Reducing the dimensionality of data with neural networks. science, 313(5786):304- 507, 2006.
[18] Diederik P Kingma. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114 2013.
[19] Durk P Kingma, Tim Salimans, and Max Welling. Variational dropout and the local reparame- terization trick. Advances neural information processing systems, 28, 2015.
[20] Bernhard H Korte, Jens Vygen, B Korte, and Vygen. Combinatorial optimization, volume 1. Springer, 2011.
[21] Alan Lahoud, Erik Schaffernicht, and Johannes Stork. Datasp: A differential all-to-all shortest path algorithm for learning costs and predicting paths with context. Uncertainty in Artificial Intelligence, pages
PMLR, 2024.
[22] Arthur Mensch and Mathieu Blondel. Differentiable dynamic programming for structured prediction and attention. In International Conference on Machine Learning, pages 1462-3471 PMLR, 2018
[23] Andrew Y Ng, Stuart Russell, et al. Algorithms for inverse reinforcement learning. In Ieml, volume 1, page 2, 2000.
[24] Quoe Phong Nguyen, Bryan Kian Hsiang Low, and Patrick Jaillet. Inverse reinforcement learning with locally consistent reward functions. Advances in neural information processing systems, 28, 2015.
[25] OpenStreetMap contributors. Planet dump retrieved from https://planet.osm.org /www: www.oppnstreetmmappp org 2017.
https
[26] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[27] Michal Piorkowski, Natasa Sarafjanovic-DJukic, and Matthias Grossglauser. epfl/mobility, 2009.
Crawdad
[28] Marin Vlastelica Pogančić, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differentiation of blackbox combinatorial solvers. In International Conference on Learning Representations, 2020.
[29] Marin Vlastelica Pogančić, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differentiation of blackbox combinatorial solvers. In International Conference on Learning Representations, 2020.
11

---

[30] Gerhard Reinelt. Tsplib a traveling salesman problem library, 1991. Available at http: //comopt. ifi. uni heieeeeeerberreeeeeeeeeeeeeeeeee de/ wwfttwaa///TPPL1195///
[31] Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. In International conference machine learning, pages 1278-1286. PMLR, 2014.
[32] Yingcong Tan, Andrew Delong, and Daria Terekhov. Deep inverse optimization. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 16th International Conference, CPAIOR 2019, Thessaloniki, Greece, June 4-7, 2019, Proceedings 16, pages 540- 556. Springer, 2019.
[33] Yingcong Tan, Daria Terekhov, and Andrew Delong. Learning linear programs from optimal decisions. Advances in Neural Information Processing Systems, 33:19738- 2020.
[34] Aaron Van Den Oord, Oriol Vinyals, et al. Neural discrete representation learning. Advances in neural information processing systems, 30, 2017.
[35] Piet Van Mieghem. Paths the simple random graph and the waxman graph. Probability the Engineering and Informational Sciences, 15(4):535-555, 2001.
[36] Bryan Wilder, Bistra Dilkina, and Milind Tambe. Melding the data-decisions pipeline: Decision- focused learning for combinatorial optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1658-1665, 2019.
[37] Markus Wulfmeier, Dushyant Rao, Dominic Zeng Wang, Peter Ondruska, and Ingmar Posner. Large-scale cost function learning for path planning using deep inverse reinforcement learning. The International Journal of Robotics Research, 36(10):1073-10 2017.
[38] Brian Ziebart, Andrew L Maas, J Andrew Bagnell, Anind K Dey, et al. Maximum entropy inverse reinforcement learning. In Aaai, volume 8, pages 1433-1438. Chicago, IL, USA, 2008
[39] Brian D Ziebart, Andrew L Maas, Anind K Dey, and Andrew Bagnell. Navigate like cabbie: Probabilistic reasoning from observed context-aware behavior. In Proceedings of the 10th international conference Ubiquitous computing, pages 322-331, 2008
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Claims are summarized in the last paragraph of the introduction. Contribution i is reflected through the method section. Contribution is qualitative measure presented in the latent space analysis in the experiments. Contribution iii is in its majority represented by quantitative measures reflected in Tables 1, 2, 3 and Fig. 6
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations regarding additive perturbation and use of a solver in the training process are explicitly discussed in Section 3.2
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "LLmitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
13

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: There is proof for Proposition detailed in Section B The assumption is described in Proposition 1, and connected one of the limitations.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Synthetic dataset generation and dataset details (e.g., preprocessing) are provided Appendix The main algorithm presented in Algorithm [ while its imple- mentation details (e.g.. hyperparameters, type of optimizers, bascline details) are presented in Appendix
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
14

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: For the real datasets, the reference is provided and the used preprocessing code is found in the supplementary material. The code for the method and how run is also provided in the supplementary material. The full code will be publicly available after acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ https//ccpuullcguddeeeeeeeeee (CooeeSumissiionooooo
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: These details are found either in Appendix C in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The only result without standard deviation is in Table 2 since the analysis is supplement to the main results for path prediction (e.g., to vary training size and latent dimensions).
15

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
These details are found in Appendix F
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https::ts /atne//nnsusis/e
Answer: [Yes]
Justification: The research conducted is aligned with all relevant points in the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
16

---

Answer: [NA]
Justification:
The paper proposes an algorithm for latent space model in graph-based
applications. Therefore, is hard to directly connect to societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (c.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Both real-world datasets are referenced. The preprocessing step in the Taxi dataset is also referenced.
Guidelines:
The answer NA means that the paper does not existing assets.
17

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, papppssitphheeeocc thoode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-pan re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: All new assets are provided in the supplementary material, such as the code, the synthetic dataset generation process, and the preprocessing step of real-datasets. A description assets related the dataset processing is found in Appendix C
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
18

---

Justification:
Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly berween institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality the research, declaration is not required.
Answer: [NA]
Justification: The method development in this research does not involve the usage of LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https http://///nrigsccc/ooferrrrreee/ for what should or should not be described.
19

---

A Perturbed Fenchel- Fenchel-Young brief derivation
For regularized maximization problem, the Fenchel- Young loss is defined in
(y x) - (y) + +[(x) x)
where Ω is convex regularized and Ω is its convex conjugate. By choosing the regularized f2 as the conjugate the perturbed minimum cost, i.e., F2F = Eg min (y + e, x')]. the loss is rewritten
(y x) = E. [mingr (y + e, x + !(x)) (y,x) x)
Since the only important terms for gradient- badient-bbsed learning approach are the terms dependent i.e., we are only interested in gradients with respect to y, and inverting the sign of the loss to be suitable minimization problem instead of maximization problem, we simplify the loss for the gradient computation as:
4e xx. = (y,x) Ee [mmnn + +, xx)
B Perturbed Tenchel-Young for Graph-based Applications
Proof of Proposition 1. Let E E be the edge cost vector, and let e E R|EI be a random vector with independent, zero-mean components added to each edge. Let ý y denote the perturbed cost vector. For any path eycle x e X C {0, 1] | represented as an indicator vector over edges, the perturbed cost is given by (ý, x). representing the inner product between both variables.
We first show that the expected cost of path remains unchanged under perturbation:
Eg [y x)] Eg (y + E, x)] (y, x) + El(e, x)] = (y,x).
since each component of e has mean and is fixed.
Next, we compute the variance of the perturbed cost. The variance of the cost (ÿ.x) = (y + E, arises from the perturbation:
Var( x)] = Var[<e,
Assuming the components E, are independent with identical variance o², we obtain:
|E|
[E]
Varl(e, = x Varlee] = o²
Σ
xe = 0=||x|lo.
e=1
where ||x|lo denotes the number of edges in the path x. Hence, if all x E X' have equal length, the variance is the same for all paths.
As direct consequence, the additive perturbation model induces equal expected cost and variance across paths cycles when their lengths equal. This condition holds exactly in Hamiltonian cycle experiment, where all feasible cycles visit each node once and thus have fixed length. In the path planning experiment, although path lengths may vary. the uniform spatial layout our real-world datasets (ship and taxi) and lack of large shortcuts make it reasonable to assume that most feasible paths between start and target nodes have similar lengths, while too lengthy paths are extremely unlike to be optimal even with perturbation. Consequently, the induced variance does not vary much, validating the use of this perturbation model in both settings.
C Datasets details
Synthetic Waxman Random Graph We generate Waxman graph 35 with 700 nodes (a = 0.05. 0.6), where the probability of an edge between two nodes u and given by P(u, v) d(u.w)
3-dres where we considered d(u, v) as the Euclidean distance between nodes u and and dmax is the maximum distance between of two nodes, consequently ending up in 7230 edges. We create three edge cost sets to simulate three different agents performing decisions to go from start and end nodes. The edge costs based on Euclidean distances, with higher costs for the southern edges
exp
20

---

for agent 1, and higher costs in the northern for agent 3, while agent 2 is not biased by the edges position. For each agent, we add random noise in the cost elements y so the generated paths can be different from each other even within the same agent. The "observed" paths are generated by running the Dijkstra on the noisy edge costs. Two sets of 6,000 observed paths are generated: one with single source and target pair (Fig. [2] top-left) and another with multiple source-targed pairs (Fig. 2 bottom-left). In each of these sets, 5,000 paths are used for training IO-LVM and the baselines, while 1,000 are used for evaluation purposes. Further details on cost generation are provided in the code.
Ships dataset We use the Automatic Identification System (AIS) data provided by the Danish Maritime Authority [10), considering latitude and longitude projected in 2D space for simplicity. The analysis focuses on paths from the first week of the months January 2024, May 2024, and June 2024. Only paths that exceed distance of 4 units (in latitude/longitude) in Euclidean space included. path is considered completed either when the ship speed approaches zero or when there is an abrupt change in its heading. In some cases, there gaps in the latitude/logittude signals; when such jumps occur, we segment the data and treat them as separate paths. We created grid graph with distance of 0.09 units between adjacent nodes, focusing more route options to be taken, which in total led to 2513 nodes and 8924 edges. This resulted in approximately 2,500 ship paths, for which the first 2000 (in the order available from the data) is used for training. Note that this is the most sparse dataset, i.e. few paths in comparison with the graph size. This led, in our experiments, the VAE not being able learn even after considerably more (c.g.. 10x more) epochs than IO-LVM.
the area where there
Taxi dataset The data and the preprocessing follows exactly what is done in 21 with their available preprocessing code, except for the fact that we increase the density of the grid, so that the resulting in a bigger graph, consisted of 1125 nodes and 8022 edges and 101344 trajectories. We split the train and test datasets by randomizing the taxi drivers (anonymized driver id), where 70% was used for training and 30% for test.
We use datasets from TSPLIB95 30 a library of benchmark instances for the Traveling Salesman Problem (TSP) and related optimization problems. Specifically. we selected two graphs: burmal4, which consists of 14 nodes representing locations in Myanmar, forming a complete graph with 91 edges, and bayg29, which consists of 29 nodes representing the coordinates of cities in Bavaria, Germany, forming complete graph with 406 edges. To assign the actual edge costs y, we uses the Fuclidean distance between nodes as an offset, and design nonlinear function that incorporates unobserved features to calculate edge costs. We generate two datasets for each graph, one considering unobserved features (less complex), and one considering 50 unobserved features (more complex). The observed paths are generated as w(y) without noise, where represents TSP search solver. In all experiments with TSPLIB, even with different training size, we always used the same 600 test samples for fair evaluation and proper comparisons. For the main results 2400 samples were used for training, while we had other experiments (see tables in the main paper) where we also used 1000 and 10000 training samples to understand the role of the training size in the reconstruction results.
TSPLIB
21

---

D Additional Results: Latent Space Analysis
Single S&T. We sample 20 latent values from Gaussians in the latent space and compare distribution of paths generated by the composition of the decoder and solver. Reconstructed synthetic paths from the Single S dataset are shown in the bottom graphs of Fig. 7 It is observed that points closer in the latent space share a high number of edges in the graph. Additionally, as the variance increases, the number of distinct reconstructed paths grows, indicating consistency in the learned latent space. e.g., difference between third and fourth columns in Fig. 7
Figure 7: Reconstruction for the Single S&T. Top charts: region of samples from Gaussian in the latent space. Bottom charts: corresponding generated trajectories. Blue agents has higher costs on edges in the north, while red edges has higher costs edges in the south.
Hamiltonian Cycles. We select nine samples from the test set of the burmal4 graph, dis- tributed across different regions of the latent space. They organized into three groups of three samples each (see the top graph of Fig. [9. The corresponding paths that gen- erated these latent values by the encoder are visualized in the bottom graph of Fig.
Paths with more edges intersection tend be closer each other in the latent space. We generalize this anal- ysis by computing the Euclidean dis- tance between all pairs of latent values versus the Manhattan distance based on edge usage (path choice) between those paths. For each group sam- ple pairs with a specific Manhattan distance, we calculate the average Eu- clidean distance in the latent space. The results, presented in Fig. [ reveal that samples that closer the la- tent space are also closer in terms of edge intersection.
Aug. Eusliecon distincs in coont
2.02
2.00
2.0
3.76
1.50
0.96
0.5
12
3.4
Manhat:an distance edges usage betweon path samples
Figure 8: Relationship between Manhattan distance groups and the average Euclidean distance in the latent space. Sam- ples with smaller Manhattan distances (i.c., paths with more similar edge usage) tend to have smaller Euclidean distances in the latent space.
E Additional Results: Inference
Taxi Dataset. We sample three different latent vectors from the learned latent space on the Taxi Dataset and compute three different set of learned edges costs, i.e., y = & (go (z)). Then, we use Dijkstra as w(y") on those three set of edges to compute the shortest path given two set nodes in the extremes of the graph on those learned edges. The resulting edges costs, normalized by the mean and standard deviation of a bigger sampling population of edges, and the resulting shortest paths, are illustrated in Figure 10
22

---

Latent Dimension
10
Latent Dimension
Figure 9: Visualization of the latent space and paths for the burmal4 graph. The top graph shows the latent space with nine manually selected samples. The bottom graphs display the corresponding paths for these samples.
Sampled cost
Sampled cost B
Sampled cost C
par-
puth
Stal loee
Ser.
Star IeIO
Spur
Figure 10: Three different set of edges costs from the learned latent space on the Taxi Dataset (top graphs, one per column). Corresponding shortest path given two set of nodes in the extremes of the graph on those learned edges (bottom graphs, one per column).
TSPLIB reconstruction The results in Table are Recall of edges reconstruction in the TSPLIB datasets for both training and test path samples. IO-LVM is capable to reach almost 1.0 in all cases. VAEs can also do good reconstruction when analyzing this metric. However, most of the mistakes in VAEs reconstruction leads non-structured output, i.e., non Hamiltonian cycle, which can be observed with some reconstruction examples in Figure
Varying the number of latent dimensions
In our experiments, we observed that for certain tasks, very low number of latent dimensions was enough. For instance, in the Ship Dataset, attempting to add a third dimension to the latent space revealed that the second and third dimensions are highly correlated (Fig. 12). indicating that the third dimension is unnecessary. Conversely, in the Hamiltonian Cycles experiment, where 50 hidden features were used generate edge costs with a complex relationship, increasing the latent dimensions proved beneficial in mitigating underfitting during the reconstruction process. This effect illustrated Fig. [3, which compares the performance of using latent dimensions (left graphs) versus 10 latent dimensions (right graphs) for both the burmal4 /4 (top graphs) and bayg29 datasets. In the right-hand charts, we observe that using latent dimensions achieves 100% Recall in the reconstructions for the training datasets and improves Recall for the test datasets compared to the
23

---

Table 4: Reported are the average Recall of edges reconstruction (edge matching) the training (first row) and test (second row) sets for the Hamiltonian Cycles experiment.
Methods
Lat. Dims
burmal4 dims)
bayg29 (3 dims)
burmal4 (50 dims)
bayg29 (50 dims)
VAE
0.924 0.004
0.805 = 0.007
0.704 0.007
0.572 0.026
0.908 = 0.004
0.798 = 0.003
0.678 0.003
0.555 + 0.028
VAE
10
1.000 0.000
0.995 + 0.002
0.998 0.001
0.916 0.025
0.976 0.004
0.957 + 0.003
0.911 0.009
0.799 + 0.033
1O-LVM
1
0.900 0.003
0.856 = 0.003
0.731 0.004
0.696 + 0.005
0.890 0.007
0.846 = 0.004
0.724 0.005
0.685 0.006
1O-LVM
2
0.973 = 0.004
0.908 = 0.016
0.867 0.008
0.786 + 0.010
0.950 0.007
0.883 - 0.013
0.810 0.009
0.723 1 0.005
IO-LVM
10
1.000 + 0.000
0.999 + 0.000
0.999 + 0.000
0.997 + 0.001
0.985 + 0.002
0.971 + 0.005
0.960 = 0.004
0.900 + 0.004
Gamp burna14)
Samsle
Sample
Sample
Cample
10-AVM (8m--30)
Edges correctly
Edges correctly
Figure 11: Each column illustrates an inferred sample for the Hamiltonian Cycles experiment. The first row represents the cycle observed in the test set. The second row represents solution of the TSP using edges cost as euclidean distances (offset in the data generation process). Third and Fourth rows represent inference using VAE and IO-LVM with 10 latent dimensions. Green edges denote correct reconstructions relative to the groundtruth, while red edges indicate false positives.
2-dimensional case shown in the left-hand charts. However, with 10 latent dimensions, slight overfitting emerges, which could be mitigated through more careful regularization and neural network architecture design. Addressing this was beyond the scope of our current study.
E.1 Denoising Taxi paths
By encoding observed paths using the trained encoder of IO-LVM, and then decoding the correspond- ing latent value through the decoder solver, it is possible to observe slight differences between the input and output. This due the well-balances /3 chosen the training process avoid overfitting, leading to denoising feature, i.c., removing uncommon patterns in observed path. Figure [4]

---

Latorr Oliner Soon
ship Wests
ship Weet
00 Literi Dinension
23
Latone Diverrion 35
Figure 12: Latent space of ship trajectories using three dimensions. The right graph indicates that there is no need for third latent dimension. Narrow ships are more concentrated in the top right corner of the two left graphs.
Burmal4 (2 Latent Dimensions)
Burma14 (10 Latent Dimensions)
1.0
Train
1.0
Validation
0.9
0.9
0.7
0.7
0.6
0.6
Accuracy
0.5
0.5
100
300
500
100
300
500
800
Bayg29 Latent Dimensions)
Bayg29 Latent (imeessios)
1.0
0.9
0.9
0.8
0.6
0.6
0.6
0.5
100
200
300
400
500
600
70%
B0D
100
200
300
400
500
800
700
8do
Epochs
Figure 13: Comparison of training and validation curves for reconstruction performance using latent dims (left) and 10 (right) for the burmal4 (top) and bayg29 (bottom) datasets. Increasing the number of latent dims improves Recall for both training and validation datasets.
illustrates four samples of observed paths and its corresponding reconstruction. There are small differences three of them, indicating less likely path decision patterns based on the training dataset.
Obsarved /twoorttuudedd-n PMth
Obsarved flacoanussd Path
Otearvez va Racorss
Ubserved itcoommndddd Path
Figure 14: Four observed paths in the test dataset (green) are reconstructed (blue) by IO-LVM. eliminating potential uncommon patterns. When there is no uncommon pattern, the blue path overlaps the green path.
25

---

Implementation details
IO-LVM is trained according to Algorithm We used PyTorch [26] for the implementation. We consider learning rate of 0.00004 and a batch size of 250 for the Waxman synthetic dataset, the Ship dataset, while the Taxi dataset and the Hamiltonian Cycle experiment uses learning rate of 0.0001 and batch size of 200. COPs are solved in parallel for the batches. The neural network architectures do not have any special implementations. The encoder architecture consists of a neural network with 4 hidden layers, each containing 1000 neurons, with ReLU activation functions in the hidden layers. The decoder architecture the same as the encoder, but with a Softplus activation function to ensure that all edge costs remain positive. The RMSProp optimizer is used for the Synthetic and Ship datasets, while the Adam W optimizer is used for the Hamiltonian Cycles experiment. The experiments were run model used was the 13th Gen Intel(R) Core(TM) 17-13700KF, which has 24 cores. We use Dijkstra from networkx library in python [5] for solving SPP: and Ortools routing python library for TSP solutions [4). For all the experiments, we rum with fixed and high number of epochs. The most time consuming experiment with the Taxi dataset dueto the number of samples. We observed that after 100 epochs (around days to complete with our resources) was enough for the model to converge. The other experiments be finished in maximum of few hours with epochs (the higher the better). However, for the VAEs baseline, more epochs are generally needed (we observed convergence after 1200 epochs for the synthetic experiment, for example). Further details are found in the provided code at hhttps://githuu com/ AlanLahoud/IO-LVV
CPU due the bottleneck introduced by COP solvers. The processor
than 500
Baselines. BO was performed to optimize a single variable i.e., the variance of the perturbation. 100 calls for each run was performed by varying the initial state. PO was trained by setting pre-defined (Synthetic and Ship Datasets), as related works, by leveraging the mean of trained latent values in IO-LVM (Taxi Dataset), since the training process of PO is equivalent to IO-LVM with a single point in the latent space. Further details are found in the provided code.
26


Reviews:
[{"review_id": "MswO5dyToR", "reviewer": "Reviewer_V5dK", "summary": "The paper proposes IO-LVM, a generative model that learns latent cost representations of constrained optimization problems (COPs) from observed structured decisions, such as paths in graphs. By integrating variational inference with a black-box solver and using Fenchel-Young losses with perturbation-based gradient estimation, IO-LVM can generate feasible solutions and capture a distribution over cost functions, enabling modeling of diverse agent behaviors without labels. The method is evaluated on synthetic and real-world datasets, showing strong performance in reconstruction, latent space structure, and downstream tasks.", "questions": "See weaknesses above as well as the following questions.\n\n* How does the model perform under suboptimal or noisy data?  (can you at least provide a discussion for this?)\n* Can it scale with approximate solvers or caching? \n* Is the latent space interpretable under interpolation? \n* Can the method generalize beyond routing tasks to other COPs like scheduling?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n\nThe proposed approach ensures constraint satisfaction via solver-in-the-loop decoding and handles multimodal behaviors by learning cost distributions. Theoretical grounding is solid, and experiments show clear advantages over VAEs and other baselines across multiple tasks. The learned latent space is interpretable and supports applications like denoising and anomaly detection.\n\nWeaknesses\n\nThe method assumes optimal demonstrations and requires efficient solvers, limiting applicability to complex or noisy real-world tasks. Solver calls during training could be a bottleneck. Connections to more recent inverse RL or graph generative methods are not clearly stated.", "was_revised": true, "final_justification": "Given the consensus of all reviewers, I think this is a good paper that should be accepted.", "rebuttal": "We thank the reviewer for their thoughtful feedback and constructive suggestions. Below, we address the questions and suggestions point by point.\n\n---\n\n>> **Reviewer comment:**  \"The method assumes optimal demonstrations.”\n\n**Answer**: Our framework **does not require global optimality under a single, unknown cost function**. Instead, we assume agent‑specific optimality. This means that each observed trajectory $x_i$ is optimal **for its own latent cost vector** $y_i$ over the feasible set $\\mathcal{X}$.\n\n**Why this assumption is realistic?**\nSuppose the task is to perform a path from node A to node B. If two agents perform two distinct paths, both are considered optimal with respect to their own underlying (latent) costs. There is no assumption of a global optimal path. There is no assumption of a static COP cost (e.g., constant transition costs in the graphs).\n\n---\n\n>> **Reviewer comment:**  \"The method requires efficient solvers... Solver calls during training could be a bottleneck. Connections to more recent inverse RL or graph generative methods are not clearly stated.\"\n\n**Answer**: \n\n**Why having a solver in the loop worth it?**\n\nNote that by calling efficient solvers, feasibility is guaranteed by construction. Pure generative models (VAEs, normalising flows, diffusion) must post‑process outputs with hand‑crafted heuristics that are problem‑specific and do not generalize across COP families. Some of these methods, suggested by reviewer aXGz, for example, are discussed in the answer to reviewer aXGz. To summarize it here, in general (except for related work, that is discussed below), methods that attemps to solve the same problem without using COP solvers have the disadvantage of not ensuring feasibility or needs an extra layer that is problem-specific and tailored to map the output to the feasible set. In contrast, IO‑LVM inherits guarantees output feasibility as soon as a suitable COP solver is available, making our method more flexible to a wider variety of problems.\n\n**Related work.**\n\nFrequent call of blackbox solvers are also presented in papers in well-known venues such as \"Learning with Differentiable Perturbed Optimizers (Berthet et al., 2020)\", \"Differentiation of Black‑box Combinatorial Solvers (Pogančić et al., 2020)\", and \"DataSP: A Differential All-to-all Shortest Path Algorithm (Lahoud et al., 2024)\". In SOTA, this is generally the price to pay to ensure outputs feasibility across a wide variety of problem structures, unless the output structure (to ensure feasibility) is easier to model in other manners.\n\n---\n\n\n\n>> **Reviewer question:** \"How does the model perform under suboptimal or noisy data? (can you at least provide a discussion for this?)\"\n\n**Answer**: \n\nThis is a very important question. Our model is explicitly designed to remain reliable when demonstrations are noisy.  The main assumption is that the noise in the decision space comes from the variation of the underlying COP cost, e.g., agents perform tasks with distinct COP costs, and therefore it reflects to variations in the decision space (noise in paths, \"near-optimality\")). This assumption is stated in our paper in lines 167-168 in Section 3.2.\n\n---\n\n>> **Reviewer question:** “Can the method scale with approximate solvers or caching?”\n\n**Answer**: \n\nThis is also a very important question. We believe that scaling via approximate solvers and caching is an appealing research direction, and we appreciate the opportunity to discuss it. Although the current submission uses an exact solver at training time, the architecture is solver‑agnostic; replacing the exact oracle with an approximate or cached one is straightforward. However, the implications either on the results or in the time of convergence might harm, and it might depend on the bound guarantees of the solver near-optimality. \n\nWe note that recent work in the broader \"predict‑and‑optimize\" literature already explores similar directions. For example, the work “Smart predict-and-optimize for hard combinatorial optimization problems” (Jantaya et al., 2020) shows that approximate or learned solvers can accelerate end‑to‑end training with a COP solver in the loop. We believe that extending such techniques to the *learning‑from‑demonstrations* setting we study here would be a promising research direction.\n\n---\n\n>> **Reviewer question:** Is the latent space interpretable under interpolation?\n\n**Answer**: \n\nYes! In Figure 9 (Appendix C) for example, we can observe that selected points are not in the training set, they are picked between training samples. Closer points in the latent space do not have much difference in edges usage in the graph, while distant points leads to more distinct cycle choices. A more general result is observed in Figure 8, where the statistics of the latent distance is correlated to the statistics of path divergence. Figure 7 (Appendix C) is another evidence, where we sample latent vectors using Gaussians, and the paths sampled from the same Gaussian are relatively similar (if the Gaussian variance is not too high). Note that, however, because of the COP nature, that it is still possible that small changes in the latent space result in very different solutions (e.g., a slight variation on edges costs might make a taxi driver to take the shortcut instead of the highway).\n\n---\n\n>> **Reviewer question:** \"Can the method generalize beyond routing tasks to other COPs like scheduling?\"\n\n**Answer**: \n\nYes! The framework is geenric to any COP formulated with a linear cost. Note that, as we discussed with reviewer eUDr, linear costs are powerful to formulate combinatorial problems. Linear costs are note only able to formulated problems like the ones we tackle in the paper but also many other combinatorial problems such as scheduling COPs (e.g., \"The Schedule-Sequencing Problem (Bowman 1959)\", \"An ILP Model for Machine Scheduling (Wagner 1959)\").\n\n**Why we focused on routing in this paper?**\n\n* **Visual interpretability.**  Paths are easy to plot, making latent‑space diagnostics immediately understandable. \n* **Direct societal value.**  Predicting routes helps to anticipate roadworks, identify urban mobility patterns, detect traffic anomalies, etc.  \n* **Public data abundance.**  Large‑scale, high‑quality demonstrations (GPS traces) are readily available, whereas labelled scheduling decisions are more difficult to find (to the best of our knowledge). Note that we specifically need demonstrations / solutions for the same COP by different agents or under different costs. Such datasets are not easy to find in the real world.\n\n---\n\nWe once more thank the reviewer for the chance of having a fruitful discussion."}, {"review_id": "3CLNptwI9e", "reviewer": "Reviewer_eUDr", "summary": "This paper presents a new method called IO-LVM for tackling inverse optimization problems, i.e., the problem of learning unknown cost functions from the solutions of constrained optimization problems. The work combines two techniques: latent-variable variational encoder models and gradient estimation via French-Young loss, to deal with two issues (1) learning of the underlying distributional representations of the cost vectors, and (2) non-informative gradient in discrete solution spaces, respectively. They present their framework’s versatility in route problems.", "questions": "1. It seems that the chosen FY loss is well-defined (as in your citation [7]) only when the COP is exactly a linear program with convex polytope constraint set. Otherwise, the linear operator (inner product) does not make sense, and the gradient may not be valid. I see no reason to define the FY loss this way if the objective of the COP for example is a general quadratic form of decisions $x^\\top Y x$ where $Y$ is the cost matrix. I also doubt if the gradient derivation that works for the convex constraint set assumption, can also work here when the decision set is discrete. Can you confirm if this is the case? If yes, then I believe you need to specify it for a rigorous presentation, and you should explicitly discuss that your methods do not work for the general COPs. \n2. I may not fully understand but the presented work does not perform or generalize inverse optimization; it effectively works on a related but not exactly same problem. I have no doubt It learns a latent representation of the cost function, and it is possible to sample a cost function out of the latent model. However, it is not clear if the framework can give the best prediction of the cost vector given a decision solution out of the COP, unless the black-box solver $\\omega$ represents a invertible map that can recover $y^\\theta$ from $\\hat{x}_\\epsilon^\\theta$. \n3. In Line 143, you mentioned that a benefit of your derived objective eq. (5) is that the solver runs once per data sample in SGD. I don’t see this as an advantage without any evidence. You need to compare with SGD that runs with solving multiple Monte-Carlo per data sample. It potentially yield better results as it offers a less noisy gradient that can lead to a steeper descent and require less iterations of training.", "limitations": "1. Following the first bullet in Questions, I believe the presented method is not sufficient for handling the general class of constrained optimization problems as claimed in Abstract and Intro.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n1. The paper tackles some well-motivated real issues in inverse optimization literature. The method IO-LVM presents a reasonable routine for solving these issues.\n2. The method allows some interesting inference analysis by exploring the learned cost distribution, as a consequence of adapting the VAE models.\n\n**Weaknesses**\nThe mathematical rigor needs some polishment in Section 3. This include undefined problem setups, undefined/inconsistent notations, etc.:\n\n  - The symbol $\\hat{x}\\_{\\epsilon}$ is never introduced. From Eq. (3) it looks like the gradient of the expectation term. Moreover, when you write $x=\\hat{x}\\_{\\epsilon}(\\theta)$,  $x$ are data while $\\hat{x}\\_{\\epsilon}$ is a function of the trainable parameters $\\theta$.  Thus, I believe it is more natural to flip the equation and write \"if and only if we set $\\theta$ such that $\\hat{x}\\_{\\epsilon}(\\theta) = x$\". \n\n  - In eq. (4), the LHS uses $y^\\theta$ (with no $z$), while the RHS inconsistently uses $g\\_{\\theta}(z)$ and introduces notation $\\hat{x}\\_{\\epsilon}^\\theta$ with a new index $\\theta$ for the first time.\n  - A formal and mathematical formulation of the original optimization problem should be presented. No *mathematical language* asserts that you have the assumption that the dataset is heterogeneous with different agents solving a same optimization problem that has a common constraint space yet differs in personalized linear cost. I can raise more questions about the problem setting if not specified. For example, following Figure 2, do you assume that conditional on an agent, and a given problem requirement (fixed origin-destination), the cost is determined or random? \n  - See first bullet in Questions.\n\nThese all impede a smooth reading and understanding of the methods.\n\n2. Weak theory with insufficient and vague explanation.\n  - Authors highlighted that the formulation ensures “equal variance and unbiasedness across the solution space” in Line 132, while in Proposition 1 the phrase used is “all solution costs have equal expected value and equal variance” What do these two phrases mean in mathematical language? The two expressions do not mean the same thing to me. \n  - Furthermore, in Line 141, it is not clear what it means that eq. (5) highlights “the estimator is unbiased with a double expectation”. You probably mean eq. (5) is an unbiased estimator of the original objective in eq. (2).  Moreover, in Line 190, I cannot clearly see how the FY loss with additive perturbation yields a good choice.", "was_revised": true, "final_justification": "Most of my concerns are resolved during the rebuttal and discussions. I weakly recommend the acceptance if authors improve over  mathematical rigor in Section 3.", "rebuttal": "We sincerely thank the reviewer for the insightful questions and concerns raised.  \nThese comments/reviews were extremely valuable for improving the technical clarity and presentation of our work. \n\n\n**Regarding the symbol $\\hat{x}_{\\epsilon}$:**  \nWe have added an explicit introduction of $\\hat{x}_{\\epsilon}$ in Line 135 of the revised manuscript (to be updated in openreview in case of acceptance) as $\\omega(y + \\epsilon)$.  We also agree that reversing the equation order in the inline equation in Line 136 improves clarity, and we have applied this modification in the new version as well.\n\n**Regarding Eq. (4):**  \nThe reason we did not use $z$ on the LHS of Eq. (4) was to avoid inconsistency with the previous equations of $l_{FY}$ (e.g., Eq. (3)), while the use of $z$ on the RHS was meant to emphasize the encoding-decoding process.  However, we agree with the reviewer’s suggestion and, in the revised version, replace $g_{\\theta}(z)$ by $y^{\\theta}$, prioritizing clarity and self-content of eq.(4) itself over emphasizing the encoding-decoding pipeline.  We have also introduced $\\hat{x}_{\\epsilon}^{\\theta}$ in Line 138, immediately after Eq. (4).\n\n**Regarding ambiguous wording in Lines 132 &Prop. 1:**  \nThe additive perturbation model, connected with Proposition 1, states that all solutions of equal length share the same expected cost and the same variance. This means that no path is a priori favoured by either the noise or the graph structure because solutions with the same expected cost is mapped to the same likelihood of being chosen with minimum cost (detailed in Appendix A).  Therefore, to enhance clarity, we have replaced the original sentence (lines 131/132):  \n> “ensures equal variance and unbiasedness across the solution space”  \nwith:  \n> “ensures that no solution is a priori favoured by the noise or problem structure.”\n\nFurthermore, we acknowledge that for other applications it can be more precise to replace the additive noise, as we state in the lines 191/192: “When this is not the case, alternative perturbation methods would be required”.\n\n---\n\n\n### Questions\n\n**1. Expressiveness of a linear cost model and validity of the Fenchel–Young (FY) gradient in discrete problems**\n\nWe thank the reviewer for raising these point, as clarifying both aspects are important to support our claims.\n\n**(a) Expressiveness of a linear cost:**  \nA linear cost with general non‑convex constraints is highly expressive, as combinatorial problems can be represented in this form.  \nAccording to Korte & Vygen (*Combinatorial Optimization*),  \n> “Virtually all combinatorial optimization problems can be formulated as integer programs …”  \n\nwhich refers to integer linear programs in the book’s chapter (as we cite it in Lines 193–194 of our paper).  \nIn the case of a quadratic cost (in a discrete space), as the reviewer pointed out, one would introduce auxiliary variables and reformulate the problem with a linear cost before applying IO‑LVM. Such reformulations are outside the scope of this work but are standard practice. \n\nIn case of continuous feasible spaces (QPs, LPs), simpler ways are available to compute gradients, such as differentiating KKT conditions, for example. However, as we introduced in lines 20 and 38, and mention in line 193, the focus of IO-LVM is on problems with discrete feasible sets.\n\n**(b) Gradients for non‑convex/discrete problems:**  \nReference [7] (\"Learning with Differentiable Perturbed Optimizers (Berthet et al., 2020)\") discusses how Fenchel-Young gradients apply when $\\mathcal{X}$ is discrete. In fact, those gradients are useful mainly because they fit to discrete problems. We did not detail the steps to avoid confusion to our contributions. However, we agree that it is important to clarify this point and below we summarize the reason why they fit to discrete problems.\n\nThe gradient $\\nabla_y L_{FY}$ is needed to perform backpropagation during training, which depends on the solution of the COP solver. Because the COP cost is linear (and the reason why linear costs are expressive enough is discussed in the previous item), this solution is an extreme point of the convex hull of the original discrete feasible set. But the convex hull itself does not need to be explicitly described in our paper (i.e., the focus of our method is not to derive the fenchel young gradients) because the solution is the same, i.e., $\\hat{x}_\\epsilon$ is identical whether solving over $\\mathcal{X}$ or $\\operatorname{conv}(\\mathcal{X})$ (convex hull). In simple words, although FY is defined under a convex feasible set, the trick is to consider that this convex feasible set is the convex hull of the problem of interest, which is initially defined under a discrete feasible set.\n\n---\n\n**2. Scope of “inverse optimization”**  \nOur use of the term “inverse optimization” in our paper follows the literature in recovering cost functions from observed decisions (e.g, Inverse Reinforcement Learning). We agree with the reviewer that, in general, the solution mapping from COP costs may not be invertible. However, this limitation is inherent to any inverse optimization approach when multiple cost functions yield the same observed decision. We would like to argue that this is not a specific limitation of IO-LVM.\n\n**3. Computational efficiency claim (Lines 142–144)**  \nOur statement was intended to highlight **computational efficiency** rather than improved learning performance. Specifically, COP solver calls dominate training wall‑clock time.  \nWe thank the reviewer for the concern, and to enhance clarity, we have revised the text to:  \n> “By leveraging SGD, the solver runs once (rather than several times in a Monte Carlo fashion) per data sample during training, reducing the computational cost per iteration.”\n\n---\n\nWe sincerely thank the reviewer once again for the opportunity to engage in this constructive discussion. We hope that our responses have helped to clarify the major concerns and we would be happy to provide any additional clarifications should further questions arise."}, {"review_id": "0woMWvBIID", "reviewer": "Reviewer_4jFq", "summary": "The paper proposes a latent variable model to learn representations of (unknown) cost functions from examples of the form (problem requirements, structured decision vector). The model, dubbed Inverse Optimization Latent Variable Model (IO-LVM), operates as follows:\n* The pair is stochastically encoded to a latent variable, which is then decoded, similar to VAE\n* Unlike a VAE, the decoded variable is not directly a sample. It represents costs for a constrained optimization problem (COP). The costs are passed to a black-box COP solver (with some perturbation to improve the efficiency of gradient estimation). The use of a solver in the reconstruction guarantees that the generated samples satisfy the problem constraints.\n* A Fenchel-Young loss is used in place of the usual VAE reconstruction loss. This allows gradients to be estimated even though we cannot differentiate through the black-box solver.\n\nThe model is evaluated on two graph problems, routing and Hamiltonian cycles, over several datasets. Compared to traditional VAEs, IO-LVM is shown to produce better reconstructions and a more interpretable latent space. It is also demonstrated to be useful for anomaly detection.", "questions": "Do you have ideas for other problems to which IO-LVM could be applied? (No need to run additional experiments.)", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n* The structure of the model guarantees that samples satisfy the constraints, which is a very useful property.\n* Experiments demonstrate both the quantitative and qualitative superiority of IO-LVM to VAEs (and other baselines) for the tasks considered.\n* The writing of the paper is generally clear and understandable.\n\nWeaknesses\n* The approach is limited to problems for which there is a suitable Fenchel-Young loss with analytic gradients. (Although, this covers a significant class of problems, e.g. those with linear objectives.) Experiments mostly only consider routing on graphs (also a bit about Hamiltonian cycles), which perhaps does not demonstrate the full utility of the model.\n* To get equation (3) from the definition of $l_{FY}$ and the chosen $\\Omega^{FC}$, one must argue that the $\\Omega$ term disappears. The disappearing term is not mentioned at all, which was confusing. This is not a terribly long derivation, so I think it should be included in the appendix (or cite an existing derivation).", "was_revised": true, "final_justification": "Overall I think this is a solid paper that should be accepted. The authors have promised to add a brief derivation in their revision per my suggestion, and mentioned additional problems to which the method is applicable.", "rebuttal": "We thank the reviewer for the very positive assessment and for the constructive suggestions. We discuss the raised points below.\n\n>> **Reviewer comment**: “The approach is limited to problems for which there is a suitable Fenchel-Young loss with analytic gradients (although this covers a significant class of problems, e.g., those with linear objectives). Experiments mostly only consider routing on graphs (also a bit about Hamiltonian cycles), which perhaps does not demonstrate the full utility of the model.”\n\n**Answer**\n\nWe agree that our current experiments focus on routing tasks, and we chose these specific experiments for three main reasons:\n\n1. **Visual interpretability**. Paths are easy to plot, making latent‑space diagnostics more understandable. \n2. **Direct societal value**. Predicting routes helps to anticipate roadworks, identify urban mobility patterns, detect traffic anomalies, etc. The motivation of learning from demonstrations is more intuitive.\n3. **Data availability**. Large‑scale, high‑quality demonstrations (GPS traces) are readily available, whereas labelled scheduling decisions, for example, are more difficult to find (to the best of our knowledge).\n\nHowever, the framework itself is not limited to routing. It can be applied, for example, to combinatorial problems with a linear cost structure, as correctly observed by the reviewer. This includes scheduling, resource allocation, and timetabling, for example. Note that even though the cost structure is not naturally linear, a problem reformulation could be used for linearization (more details in this matter is found in the discussion with reviewer eUDr). Those examples above could be potential problems to adress with IO-LVM if the aim is to \"imitate scheduling\" or \"imitate resource allocation\" and interpret those decisions in the COP cost space.\n\n\n>> **Reviewer comment**: Derivation of equation (3) from the definition of the fenchel-young loss.\n\n**Answer**\n\nWe agree with the reviewer that this derivation will enhance the clarity of the paper, therefore, we will provide it in the revised version of the manuscript. Below are the steps that we will add to the Appendix:\n\n---\n\nFor a regularized maximization problem, the Fenchel-Young loss is defined in [8] as\n\n$\\ell_{\\mathrm{FY}}(y, x) = \\Omega^{FC}(y) + \\Omega(x) - \\langle y, x \\rangle$\n\nwhere $\\Omega$ is a convex regularizer and $ \\Omega^{FC} $ is its convex conjugate. We choose the regularizer $\\Omega$ as the conjugate of the perturbed minimum cost:\n\n$\\Omega^{FC} = E_{\\epsilon} [ \\min_{x'} \\langle y + \\epsilon, x' \\rangle ]$\n\nso that\n\n$\\ell_{\\mathrm{FY}}(y, x) = E_{\\epsilon} [ \\min_{x'} \\langle y + \\epsilon, x' \\rangle ] + \\Omega(x) - \\langle y, x \\rangle$.\n\nSince the only important terms for our gradient-based learning approach are the terms dependent on $y$, i.e., we are only interested in gradients with respect to $y$, and inverting the sign of the loss to be suitable to a minimization problem instead of a maximization problem, we simplify the loss for the gradient computation as:\n\n$\\ell_{\\mathrm{FY}}'(y, x) = \\langle y, x \\rangle - E_{\\epsilon} [ \\min_{x'} \\langle y + \\epsilon, x' \\rangle ].$\n\n---\n\nWe sincerely thank the reviewer once again for the opportunity to engage in this constructive discussion."}, {"review_id": "prhDZuInoq", "reviewer": "Reviewer_aXGz", "summary": "Summary\nThis paper proposes a novel Inverse Optimization Latent Variable Model (IO-LVM) for learning implicit cost representations in constrained optimization problems (COPs) from observed optimal solutions. Unlike traditional Variational Autoencoders (VAEs), IO-LVM maps latent variables to cost function parameters and incorporates a black-box solver to ensure the generation of feasible, constraint-satisfying solutions. This design effectively addresses the challenges of non-differentiability and structural infeasibility common in structured output prediction. By leveraging Fenchel-Young losses and perturbed gradient estimators, the authors develop a principled training framework that enables unsupervised learning tasks such as path reconstruction, distribution prediction, interpretable latent space modeling, and anomaly detection.\n\nThe proposed approach is thoroughly evaluated on synthetic graphs, maritime shipping routes, taxi trajectories, and TSP benchmarks, covering multiple aspects such as reconstruction accuracy, distributional modeling, latent structure analysis, and inference performance. Comparative studies with representative baselines (VAE, Perturbed Optimizer, Bayesian Optimization) demonstrate the modeling capacity and practical potential of IO-LVM in unsupervised structured decision problems.", "questions": "The manuscript is clearly written and technically sound. The reviewer has no additional questions at this time.", "limitations": "This work primarily focuses on unsupervised cost inference in combinatorial optimization problems. Including a brief overview of recent advances in supervised CO solvers could further clarify the positioning and contribution of IO-LVM. Suggested references include (and potentially others) :\n\n[1] DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization\n\n[2] DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems\n\n[3] T2T: From Distribution Learning in Training to Gradient Search in Testing for Combinatorial Optimization", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths\n\n1. IO-LVM generates feasible solutions by mapping latent variables to cost vectors and invoking a black-box solver, which guarantees constraint satisfaction (e.g., valid paths or Hamiltonian cycles) and avoids the infeasible outputs often produced by VAE-based models.\n\n2. The learned latent space naturally captures behavior patterns of different agents or preferences, enabling interpretable clustering and path preference analysis.\n\n3. IO-LVM supports unsupervised inference tasks such as path denoising, anomaly detection, and distributional generation, filling a gap in current methods for unsupervised structured prediction.\n\nWeaknesses\n\n1. Despite adopting expectation linearization to approximate gradients, training still requires frequent calls to the black-box solver, which can be computationally intensive, especially on large-scale graphs.\n\n2. The paper focuses exclusively on the unsupervised setting and does not discuss how supervised methods might perform when agent labels or ground-truth cost functions are available.\n\n\nThe writing, theoretical formulation, and empirical performance of this work are all strong. The reviewer is generally supportive of acceptance. However, a discussion on the relationship and comparative boundaries between supervised and unsupervised methods would further strengthen the paper. The reviewer would be willing to raise the rating upon incorporation of this clarification in the revised version.", "was_revised": true, "final_justification": "After carefully considering the authors' rebuttal and the subsequent discussion, I find that the main concerns raised in the initial review have been adequately addressed. I am satisfied with their responses and have decided to raise my final rating.", "rebuttal": "We thank the reviewer for the very positive assessment and for the constructive suggestions.\nWe address the two substantive concerns below.\n\n## 1. Training‑time solver calls\n\n**Reviewer’s concern.**  \n> Frequent calls to the black‑box solver may be computationally intensive on large graphs.\n\n**Answer.**\n\n- **Why having a solver in the loop worth it?**  \nFirst, the expectation‑linearisation technique reduces the cost to *one forward call per training sample*, rather than the multiple Monte‑Carlo calls used in classical perturbed‑optimizer methods.  Also, Feasibility of the yielded decision vector (e.g., paths, cycles) is guaranteed by construction.  \nPure generative models (VAEs, normalising flows, diffusion) must post‑process outputs with hand‑crafted heuristics (e.g., DIFUSCO details some heuristics in §3.5 of their paper) that are *problem‑specific* and do not generalize across COP families. In contrast, IO‑LVM inherits guarantees output feasibility as soon as a suitable COP solver is available for the formulated COP. \n\n- **Related work.**  \nFrequent call of blackbox solvers are also presented in papers in well-known venues such as *Learning with Differentiable Perturbed Optimizers* (Berthet et al., 2020), *Differentiation of Black‑box Combinatorial Solvers* (Pogančić et al., 2020), and *DataSP: A Differential All-to-all Shortest Path Algorithm* (Lahoud et al., 2024). In SOTA, this is generally the price to pay to ensure outputs feasibility, unless the output structure (to ensure feasibility) is easier to model in other manners.\n\n\n---\n\n## 2. Supervised **vs.** unsupervised cost learning (and suggested references)\n\n**Reviewer’s concern.**  \n> A discussion of boundaries between supervised and unsupervised methods is missing, and relate to references such as DIFUSCO, DISCO, T2T.\n\n**Answer**\n\nSupervised approaches such as DIFUSCO, DISCO, and T2T operate in a direct mapping setting. This means that these methods directly learn to map an instance to a *solution* (e.g., a path or cycle) without explicitly estimating COP costs. This has the advantage of not requiring solver calls during training, but the resulting model outputs may violate constraints unless additional decoding heuristics are applied (for example, DIFUSCO §3.5 proposes custom decoding for the specific problems they tackle). Another disadvantage of those methods is that they do not model a cost space, which is a key factor in our method for a simplified interpretability.\n\nIO‑LVM instead targets a mix of **supervised and unsupervised settings**. Supervised in a sense that **observed decisions** (e.g., paths or cycles) are available, and Unsupervised in the cost function space, where the underlying cost functions are latent. Our model explicitly learns a distribution over these latent cost functions and then uses a solver to produce solutions, guaranteeing feasibility by construction and allowing interpretable modeling of agent behaviours (and not only the output itself).\n\nIf ground‑truth costs were available, as the reviewer pointed out, a solution could still be applied in a **two‑stage approach**:  \n1. learn to regress cost functions from data;  \n2. decode solutions using the solver.  \nThis would remove solver calls during training but potentially suffer from error propagation, since the cost predictor would not directly optimise decision quality (e.g., quality of inferred paths and cycles).  \n\nWe decided to add a summarized paragraph in the related work in the new version of our paper (to be updated in case of acceptance) comparing supervised learning methods for COPs (mostly combinatorial) in a direct mapping setting using some of the references suggested by the reviewers, as discussed above.\n\n---\n\nWe sincerely thank the reviewer for engaging in this constructive discussion. We hope that our responses regarding the boundaries of supervised vs unsupervised have helped to clarify the major concerns and we would be happy to provide any additional clarifications should further questions arise."}]

Author rebuttal:

Meta-review: The paper proposes IO-LVM, a generative model that learns latent cost representations of constrained optimization problems from observed structured decisions. The approach leverages estimated gradients of a Fenchel-Young loss, propagated through a non-differentiable deterministic solver, to shape the latent space. Experimental results demonstrate the superiority of IO-LVM over VAEs and other baselines across several tasks.

The paper is generally well written and understandable. While reviewers raised some common concerns regarding the theoretical formulation, derivation, and applicability to other problems, the authors have provided clarifications that addressed these points. All reviewers noted that their comments were satisfactorily resolved. The authors are encouraged to incorporate the rebuttal clarifications into the final version to further improve the paper’s quality, for instance, by refining the exposition around Proposition 1 as suggested by a reviewer.

Given the overall positive evaluations from all reviewers, I recommend acceptance of this work.
Decision: Accept (poster)