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

We thank the reviewer for the very positive assessment and for the constructive suggestions. We address the two substantive concerns below.

1. Training‑time solver calls

Reviewer’s concern.

Frequent calls to the black‑box solver may be computationally intensive on large graphs.

Answer.

• Why having a solver in the loop worth it?
  First, 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.
  Pure 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.

• Related work.
  Frequent 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.

---

2. Supervised vs. unsupervised cost learning (and suggested references)

Reviewer’s concern.

A discussion of boundaries between supervised and unsupervised methods is missing, and relate to references such as DIFUSCO, DISCO, T2T.

Answer

Supervised 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.

IO‑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).

If ground‑truth costs were available, as the reviewer pointed out, a solution could still be applied in a two‑stage approach:

1. learn to regress cost functions from data;
2. decode solutions using the solver.
   This 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).

We 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.

---

We 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.

We thank the reviewer for the very positive assessment and for the constructive suggestions. We discuss the raised points below.

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.”

Answer

We agree that our current experiments focus on routing tasks, and we chose these specific experiments for three main reasons:

1. Visual interpretability. Paths are easy to plot, making latent‑space diagnostics more understandable.
2. 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.
3. 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).

However, 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.

Reviewer comment: Derivation of equation (3) from the definition of the fenchel-young loss.

Answer

We 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:

---

For a regularized maximization problem, the Fenchel-Young loss is defined in [8] as

$\ell_{\mathrm{FY}}(y, x) = \Omega^{FC}(y) + \Omega(x) - \langle y, x \rangle$

where $\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:

$\Omega^{FC} = E_{\epsilon} [ \min_{x'} \langle y + \epsilon, x' \rangle ]$

so that

$\ell_{\mathrm{FY}}(y, x) = E_{\epsilon} [ \min_{x'} \langle y + \epsilon, x' \rangle ] + \Omega(x) - \langle y, x \rangle$.

Since 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:

$\ell_{\mathrm{FY}}'(y, x) = \langle y, x \rangle - E_{\epsilon} [ \min_{x'} \langle y + \epsilon, x' \rangle ].$

---

We sincerely thank the reviewer once again for the opportunity to engage in this constructive discussion.

We sincerely thank the reviewer for the insightful questions and concerns raised.
These comments/reviews were extremely valuable for improving the technical clarity and presentation of our work.

Regarding the symbol $\hat{x}_{\epsilon}$:
We 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.

Regarding Eq. (4):
The 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).

Regarding ambiguous wording in Lines 132 &Prop. 1:
The 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):

“ensures equal variance and unbiasedness across the solution space”
with:
“ensures that no solution is a priori favoured by the noise or problem structure.”

Furthermore, 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”.

---

Questions

1. Expressiveness of a linear cost model and validity of the Fenchel–Young (FY) gradient in discrete problems

We thank the reviewer for raising these point, as clarifying both aspects are important to support our claims.

(a) Expressiveness of a linear cost:
A linear cost with general non‑convex constraints is highly expressive, as combinatorial problems can be represented in this form.
According to Korte & Vygen (Combinatorial Optimization),

“Virtually all combinatorial optimization problems can be formulated as integer programs …”

which refers to integer linear programs in the book’s chapter (as we cite it in Lines 193–194 of our paper).
In 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.

In 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.

(b) Gradients for non‑convex/discrete problems:
Reference [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.

The 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.

---

2. Scope of “inverse optimization”
Our 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.

3. Computational efficiency claim (Lines 142–144)
Our statement was intended to highlight computational efficiency rather than improved learning performance. Specifically, COP solver calls dominate training wall‑clock time.
We thank the reviewer for the concern, and to enhance clarity, we have revised the text to:

“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.”

---

We 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.

We thank the reviewer for their thoughtful feedback and constructive suggestions. Below, we address the questions and suggestions point by point.

---

Reviewer comment: "The method assumes optimal demonstrations.”

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}$.

Why this assumption is realistic? Suppose 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).

---

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."

Answer:

Why having a solver in the loop worth it?

Note 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.

Related work.

Frequent 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.

---

Reviewer question: "How does the model perform under suboptimal or noisy data? (can you at least provide a discussion for this?)"

Answer:

This 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.

---

Reviewer question: “Can the method scale with approximate solvers or caching?”

Answer:

This 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.

We 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.

---

Reviewer question: Is the latent space interpretable under interpolation?

Answer:

Yes! 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).

---

Reviewer question: "Can the method generalize beyond routing tasks to other COPs like scheduling?"

Answer:

Yes! 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)").

Why we focused on routing in this paper?

• Visual interpretability. Paths are easy to plot, making latent‑space diagnostics immediately understandable.
• Direct societal value. Predicting routes helps to anticipate roadworks, identify urban mobility patterns, detect traffic anomalies, etc.
• 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.

---

We once more thank the reviewer for the chance of having a fruitful discussion.