Solver-Free Decision-Focused Learning for Linear Optimization Problems
Authors: Senne Berden
Ali İrfan Mahmutoğulları
Dimos Tsouros
Tias Guns
Venue: NeurIPS 2025 poster ()
Keywords: Decision-Focused Learning
Predict-then-Optimize
Contextual Optimization
Linear Programming
Primary area: optimization
TL;DR: We propose a highly efficient loss function that exploits the geometry of linear optimization to enable fast solver-free training without compromising decision quality.

Abstract: Mathematical optimization is a fundamental tool for decision-making in a wide range of applications. However, in many real-world scenarios, the parameters of the optimization problem are not known a priori and must be predicted from contextual features. This gives rise to predict-then-optimize problems, where a machine learning model predicts problem parameters that are then used to make decisions via optimization. A growing body of work on decision-focused learning (DFL) addresses this setting by training models specifically to produce predictions that maximize downstream decision quality, rather than accuracy. While effective, DFL is computationally expensive, because it requires solving the optimization problem with the predicted parameters at each loss evaluation. In this work, we address this computational bottleneck for linear optimization problems, a common class of problems in both DFL literature and real-world applications. We propose a solver-free training method that exploits the geometric structure of linear optimization to enable efficient training with minimal degradation in solution quality. Our method is based on the insight that a solution is optimal if and only if it achieves an objective value that is at least as good as that of its adjacent vertices on the feasible polytope. Building on this, our method compares the estimated quality of the ground-truth optimal solution with that of its precomputed adjacent vertices, and uses this as loss function. Experiments demonstrate that our method significantly reduces computational cost while maintaining high decision quality.

Solver-Free Decision-Focused Learning for Linear Optimization Problems
Senne Berden, Ali Irfan Mahmutogulları, Dimos Tsouros, Tias Guns
Department of Computer Science, KU Leuven
(senne. berden, irfan www.mtoguulaarr........... dimos. tsouros, tias. guns))kuleuven.
Abstract
Mathematical optimization a fundamental tool for recision-making in a wide range of applications. However, in many real-world scenarios, the parameters of the optimization problem are not known a priori and must be predicted from contextual features. This gives rise learning model predicts problem parameters that are then used to make decisions via optimization. A growing body of work on decision-focused learning (DFL) addresses this setting by training models specifically to produce predictions that maximize downstream decision quality, rather than accuracy. While effective, DFL is computationally expensive, because it requires solving the optimization problem with the predicted parameters each loss evaluation. In this work, we address this computational bottleneck for linear optimization problems, a common class of problems in both DFL literature and real-world applications. We propose a solver- free training method that exploits the geometric structure of linear optimization enable efficient training with minimal degradation in solution quality. Our method is based on the insight that a solution is optimal if and only if it achieves an objective value that least as good as that of its adjacent vertices on the feasible polytope. Building on this, our method compares the estimated quality of the ground-truth optimal solution with that of precomputed adjacent vertices, and uses this as loss function. Experiments demonstrate that our method significantly reduces computational cost while maintaining high decision quality.
seadict-then-optie
problems, where machine
Introduction
Linear optimization widely used to model decision decision-making -maiing problems across many domains 5 20 41]. Given linear objective function and set of linear constraints, optimization solver can compute the optimal decisions. However, many real-world scenarios, define the objective function are not known at solving time. For example, delivery company may need to plan delivery routes without knowing the future traffic conditions. In such cases, the problem parameters must first be predicted from available contextual information (c.g., the weather conditions or temporal features). This gives rise to predict-then nnten-optimize problems [26). where the predictions of machine learning model serve inputs to optimization problem. The quality of the produced solutions thus hinges on the parameters predicted by the machine learning model, making the loss function used to train this model highly important.
cost coefficients that
Traditionally, machine learning model trained to maximize accuracy (e.g., by minimizing the mean squared error over all its predictions). However, this may lead to suboptimal decisions. This is because, while perfect predictions lead perfect decisions, different kinds of imperfect predictions in different ways. Decision-focused learning (DFL) addresses
affect downstream decision-maker this by training models specifically to make predictions that lead to good decisions. As numerous
works have shown, this generally improves decision quality 2 9
40
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

However, a large limitation of DFL is its high computational cost and limited scalability. This stems from the fact that gradient-based DFL involves solving the optimization problem with the predicted parameters during each loss evaluation, to assess the impact of the predictions on decision quality.
In this paper, we address this issue and greatly improve the efficiency of DFL for linear optimization
problems, which have received much attention in DFL literature [2 TO 24 28 26 40), and are a mainstay in mathematical optimization. Our solver-free approach significantly reduces training time by eliminating the need for solve calls during training altogether, and hence bypassing the most computationally expensive part of the training process. It based on the insight that a solution is optimal if and only if it achieves an objective value that is at least as good as that of its adjacent vertices on the feasible polytope. Building on this, we propose a new loss function named LAVA, that compares the quality of the ground-trune optimal solution with that of its adjacent vertices, evaluated with respect to the predicted cost vector. These adjacent vertices can be precomputed efficiently prior to training, by performing simplex pivots. Our experiments show that our solver-free L.AVA loss enables efficient training with minimal degradation in solution quality, particularly on problems that are not highly degenerate.
Background
In this section, we formalize the predict-then- then-optimize problem setting, and give the necessary background from linear programming, which we will utilize in our methodology.
2.1 the-oiiithe
We assume parametric linear program (LP) of the following form.
min c
(Ia)
s.t. As =
(1b)
2 2
(Ic)
with c R", A E Rmxx, b E RRM and m < We denote the set of optimal solutions as
(c) C I"," and a particular optimal solution as 2 (c) E (c). The parametric LP is written in standard form (i.e., with equality constraints), without loss of generality: if an LP is not initially in standard form, it can be converted by introducing slack variables. We further assume that the rows of the constraint matrix A are linearly independent. If not, the problem includes redundant (implied) constraints that can be removed without affecting the feasible region. Finally, we assume that the feasible region f R" A b, 2 0} is non-empty and bounded.
The cost parameters e = [er e2 C.). where e; E R. are unknown, but correlated with a known feature vector x E d according to some distribution P. Though not known, we assume access to training set of examples D, sampled from P. Two settings can be distinguished:
1. Complete information: each example in D is of the form (x, 2* (c)). providing direct access to historical realizations of cost parameters e, and corresponding solutions =c(c..
2. Incomplete information: observed optimal solutions 2" (c) without revealing the underlying parameters c.
each example in D is of the form (x, == (c)), offering only the
The incomplete information setting poses a notably more difficult learning problem than the complete information setting. The method we develop in this work does not assume access to the historical cost parameters c, and can thus be applied to both settings. In either setting, training set D is used to train model m., with learnable parameters usually linear regression model or a neural network - which makes predictions č.
Unlike conventional regression, the objective in training is not to maximize the accuracy of predicted costs č. Rather, the aim is to make predictions that maximize the quality of the resulting decisions. This is measured by the regret, which expresses the suboptimality of the made decisions 2 (é) with respect to true costs (lower is better).
Regret(e, c ====(())= -T (c)
(2)
2

---

2.2 Linear programming preliminaries
We briefly review core concepts from linear programming that we use in our methodology. The feasible region {= E R" A= b, 2 0} is convex polytope, assuming non-emptiness and boundedness. vertices correspond to basic feasible solutions, defined in the following.
Definition 2.1 (Basis). Given a matrix E Rmxx with full row rank, a basis is set of m linearly independent columns of A. These columns form an invertible matrix B E Rmxm The variables corresponding to the columns the basis are called basic variables; the remaining n m variables called non-basic variables.
Definition 2.2 (Basic solution). Let B be a basis. The corresponding basic solution is obtained by setting the non-basic variables to zero and solving Brg for the basic variables (i.e., 2B = B B-)
Definition 2.3 (Basic feasible solution (BFS)). basic solution is called basic feasible solution (BFS) if it satisfies z 2 O. Every vertex of the feasible region corresponds to a BFS, and every BFS corresponds to a vertex the feasible region. Thus, we use the terms interchangeably.
Definition 2.4 (Degeneracy). A BFS 2 said to be degenerate if one or more of its basic variables is zero. In such cases, multiple bases lead to the same BFS. We refer to the number of zaro-valued basic variables as the degree of degeneracy.
For any cost vector c, there exists an optimal solution (c) that is BFS, and therefore, lies at vertex of the feasible polytope. The methodology we propose in this paper will make use of the vertices adjacent this optimal solution. This notion of adjacency is defined as follows.
Definition 2.5 (Adjacent bases). Two bases B₁ and B2 are said be adjacent if they differ by exactly one column; that is, the set of basic variables for Bg can be obtained from that of B₁ by replacing a single basic variable with non-basic one (an operation referred to pivot).
Definition 2.6 (Adjacent vertices). Two BFSs (i.e., vertices of the feasible region) said to be adjacent if there exists a pair of adjacent bases such that each basis in the pair corresponds to one of the two BFS.
Related work
lot of work on DFL has focused specifically on LPs and combinatorial problems, as handling these problems is particularly challenging. This is because they make the gradient of any loss that depends on 2n (c) (like the regret) zero almost everywhere. This can be seen when applying the chain rule:
aL(='(0).e aL(= 0z*(c) de (2)(2)
(3)
Ow
de dw
The second factor (A)
de expresses the change in (C) when è changes infinitesimally. However, for LPs and combinatorial problems, this factor zero almost everywhere, and nonexistent otherwise. In other words, a small change in the problem's 's parameters è either does not change its solution 2 (c). or changes discontinuously (leading to nonexistent gradients). Most work on DFL has focused on circumventing this obstacle. Three general types of approaches can be distinguished. We briefly discuss them here, but refer the reader
22 for a comprehensive overview of the field.
The first type of approach is based on analytical smoothing of the optimization problem, in which the problem's formulation is altered such that the optimal solution changes smoothly in function of the parameters. This creates a new problem that, while only an approximation of the original, leads to non-zero gradients of the regret 25 40 To compute these gradients, differentiable optimization is used, which offers way of differentiating through continuous convex optimization problems 21
The second type instead computes weight updates for the predictive model by perturbing the objective vector. Here, the difference between the solution for the predicted vector and the solution for a perturbed vector is used to compute a meaningful gradient [ 29 33).
The third type uses surrogate loss functions that are smooth but still reflect decision quality. The loss we propose fits this category. Other examples are the seminal SPO+ loss, well as losses based on noise-contrastive estimation (28) and learning to rank 24). Also (35) and [36] which first learn
surrogate losses, to then use them to train predictive model of this type.
3

---

Zudj
7
-C
Figure I: Optimal solution 2 has two adjacent vertices, Padi and "adj" Geometrically, these vertices define the facets of the optimality cone =*, All cost vectors for which -c lies within this cone lead to 2², Cost vector is predicted. è correctly prefers =* to Zddj (i.e., ēT < ē add and thus lies on the correct side of the corresponding facet. This adds no penality to LVVA However, è
(1)
wrongly prefers add 2*, and thus lies on the wrong side of the corresponding facet. This adds cT c =dd Fadj
(2)
(2)
to LAVA.
Some work within DFL has instead focused on improving efficiency and scalability. Because DFL involves repeatedly solving optimization problems, training be computationally expensive. To improve efficiency. (27 has investigated the use of problem relaxations and warm-starting techniques. Additionally, 28 and 24 have introduced losses that solution pool that is incrementally grown.
Finally, and most directly related to this paper, [39] proposed a surrogate loss that measures the distance between the predicted cost vector and the optimality cone of the true optimal solution, which can be computed by solving a non-negative least squares problem, which is quadratic program (QP).
In summary, most existing methods repeatedly solve the (smoothed) LP QP corresponding to non-negative least squares problem at training time. Alternatively, they solve the LP to construct a surrogate loss or solution pool for training. Our approach, however, is completely frever-free, making significantly faster than existing methods, without compromising on decision quality.
4 Solver-free training by contrasting adjacent vertices
We now present our approach to enable solver-free DFL. for linear optimization problems. We first present novel loss function that uses only the adjacent vertices of the optimal solutions. We then describe how these adjacent vertices can be efficiently precomputed.
4.1 Loss based on adjacent vertices
We construct loss function based on the following proposition, which follows from the convexity of the feasible polytope (as proven in Appendix A
Proposition 4.1. Let z be vertex of the feasible polytope, and let Zudj (2) be the set of vertices adjacent to z. Vertex is an optimal solution for cost vector if and only if c S c Zadj for all Zadj Zady (z).
The proposition expresses that solution is optimal if and only if none of its adjacent vertices have better objective value. Recall that in predict-then-optmmzz problems, predicted cost vector leads to zero regret if it makes the known solution ²c( optimal. So, for any suboptimal cost vector č (not leading to 2* (c)), one or more of the adjacent vertices will score better than 8 (c). We construct loss named Loss via Adjacent Vertex Alignment (LAVA) that penalizes è for each such adjacent vertex.
Lxva (c))
Σ
max(eT x- (c) E Zadj; -)) where e 2 0
Fadi E (c)))

---

The geometric interpretation of the LAVA loss is shown in Figure [ The loss evaluates how well the predicted cost vector è distinguishes a true optimal solution (c)) from its adjacent vertices. Specifically, it penalizes cases where an adjacent solution Eadj E Zadj appears more favorable than the optimal one under è Geometrically, this occurs when the predicted cost vector é falls outside the optimality cone of =* (c), defined as the set of cost vectors for which =" =c( remains optimal. For each adjacent vertex, the loss increases proportionally to the margin by which e =<(c) is worse than c Zady e. Once = {c) is better than Eadj by at least no further gain is enforced, reflecting the fact that, in Proposition 4.1 the precise margin by which c² 2 S c Zadj is irrelevant. In case there are multiple optimal solutions for ground-truth (i.e., [Z* (c)] 1), the loss is more conservative, and is minimized only for a proper subset of cost vectors that leads to x" (c) as optimal solution.
The value of defines margin for how much better the optimal solution must be before further improvements are not rewarded. In principle, 6 = is most in line with the optimality condition expressed in Proposition 4.1 However, after meeting the optimality condition, subsequent updates during training (e.g.. from other instances) may shift the predicted cost vector slightly such that an adjacent vertex becomes preferred again. To prevent this, using small positive value (c.g.. 0.1, which we use in our experiments) introduces a buffer zone that tends to lead to smoother and more stable learning, likely by reducing sensitivity minor fluctuations near the decision boundary. In Appendix B
we provide a visualization of how this margin parameter affects the learning curve.
The LAVA loss function has the following desirable properties:
1. It is differentiable with respect è almost everywhere and offers non-zero gradients when- ever è does not yet lead to the ground-truth optimal solution =" =c()).
2. It only requires access to ground-truth solution = *c)), and not to the underlying true cost vector c. Thus, it can be applied to both the incomplete and complete information settings.
3. It is convex, ensuring that any local minimum is also a global minimum. To see why, note that both terms in ê' 2 (c) è Eadj are affine functions of é and thus their difference also affine (and hence convex). Taking the maximum of this affine function and constant -< leads to a hinge-like like function that remains convex. And since the sum of convex functions remains convex, the overall loss remains convex when taking the sum over all Zadj E Zudj (z" (c)).
4. It is computationally efficient to evaluate, as it does not require computing 2" (é) through a call to solver. Instead, it only involves dot products between è and a set of precomputed solution vectors, making highly efficient.
The LAVA loss is somewhat related to the recently proposed CaVE 39 underlying objectives. The CaVE loss is the cosine distance between č and its projection onto the optimality cone of solution x" (c). Computing the projection involves solving a QP, Instead, LAVA penalizes the "violation" of each facet of the cone separately, as illustrated in Figure [ This requires no solve calls. Another important difference is that CaVE represents the optimality cone through its extreme rays, which correspond to the binding constraints in 2 (c). In contrast, LAVA operates on the cone's 's facets, each defined by the hyperplane separating 2 (c) from an adjacent vertex Zadj.
particularly in terms of
LAVA is also related to the NCE loss from (28), but whereas NCE requires an arbitrary set of feasible solutions constructed via solve calls on predicted cost vectors during training, LAVA contrasts the optimal solution with its adjacent vertices, which can be precomputed without solving. Additionally, LAVA is hinge-like loss thresholded at -e, aligning with the LP optimality condition (Proposi- tion 4.1 whereas NCE seeks to increase the difference in objective values as much as possible. This thresholding is crucial to LAVA'S performance, as demonstrated in an ablation in Appendix B
Note that LAVA is not differentiable everywhere, because each of its max(e (c) e Zadj- -)
terms has like form, which is not smooth at the kink where ēT 2 (c) - Zndj -e. However, these kink points constitute a measure-zers set, meaning that the probability of the predicted cost vector è ending up exactly at a kink point is zero. Consequently, LAVA can be optimized reliably using standard gradient- bradie methods.
Also note that, although the zero vector technically lies within every optimality cone and could in principle minimize LAVA when the margin is zero, this does not occur in practice. Standard random initialization of the predictive model ensures that the predicted cost vector starts away from zero, and gradient updates induced by LAVA push predictions toward differences between optimal and adjacent solutions, rather than toward the origin. While pathological scenarios could be constructed in which
5

---

all gradients align exactly toward zero, such cases are extremely unlikely and have not been observed practice.
We presented LAVA in the context of LPs. However, also extends to integer linear programs (ILPs) and mixed-integer linear programs (MILPs) by operating on their I.P relaxations. The effect of doing so depends on the properties of the original problem. For binary ILPs, each optimality cone in the LP relaxation is contained within the corresponding cone of the binary ILP [9] This only makes LAVA somewhat conservative: it will always push predicted cost vectors toward the correct optimality cone, but it may push them further into the cone than strictly needed. For non-binary ILPs and MILPs, this containment does not necessarily hold, and the performance of using LAVA largely depends on the integrality gap of the relaxation.
4.2 Precomputing the adjacent vertices
Algorithm Find adjacent vertices of a basic feasible solution
I: Input: Basic feasible solution z², basic indices B(1)..... B(m), non-basic indices .........NV ((n m). constraint matrix A
2: Output: Set Zadj of vertices adjacent to z*
3: B < [A.B(1) B(m)
4: N + [A,N(1) A. N(m)
5: Zudj 0
6: Queue + [BB N)
7: Visiled {(B,N) N)}
8: while Queue is not empty do
9: Dequeue basis Beary and corresponding Neurr from Queue
cury 10: Compute directions of movement D -B-r, -Baryr-Neur Neurr
for each non-basic variable 2 as entering variable do d' Day the direction of movement of the basic variables when increasing 23 by 1
13:
Perform minimum ratio test 0"
min ( <i)
d;
e* then
D Nondegenerate pivot
15:
Let d be the unit vector ej E R for =..1.... do
16:
17:
Set direction dB d' for basic variable Bourr (k)
18:
Add new adjacent vertex Zadj Zadj U(= 0+d]
else
Degenerate pivot
20:
Identify Bearr (i) as the leaving basic variable according to the TNP rule
Construct new basis Brew and corresponding N.ew by replacing B(i) with N(j)
22:
if (Brewy Nnew) & Visited then
23:
Add (Baew: Nnew) to Queue and to Visited
24:
return Zadz
We outline the procedure that precomputes the adjacent vertices Zadi of a vertex 2" in Algorithm The algorithm takes input a basic feasible solution 2*, the constraint matrix A, and a basis of (expressed through the indices of the basic and non-basic variables). It outputs the set Z of all adjacent vertices. The algorithm starts by constructing the initial basis matrix B (and the associated matrix of non-basic columns N), and uses these to perform pivots, performed in the (revised) simplex method [5] 7. Here, pivot refers to the swapping of a basic variable and a non-basic variable. The progression through the algorithm differs depending on whether 2" is nondegenerate or degenerate solution. We now discuss each case separately.
4.2.1 Base case: nondegenerate vertices
When 2* is nondegenerate, it has unique associated basis, and every adjacent vertex can be obtained through single pivot operation (i.e., by replacing one basic variable with a non-basic one). To do so, D = - B-12 B- is computed at 10 Algorithm Each column D.j expresses how the basic variables must change to maintain Az b when non-basic variable z, is increased by 1. The algorithm then loops through the non-basie variables, and considers each zÿ in turn as the variable

---

that enters the basis (line IT. This differs from the simplex method, which selects a single entering variable heuristically.
For each entering variable, the algorithm must determine the corresponding variable that should leave the basis. To do so, it computes the maximum step size 0 that be taken in direction d' Daj without violating the nonnegativity constraints 2 2 0. This is computed using the standard minimum ratio test 0+ min;;d/<< (-=//4 [5 71. Since z" nondegenerate, 0* 0 will hold, and the if-block at line 14 will be entered. The corresponding adjacent vertex is now given by 2 + 0'd.
where E IR' is obtained by setting the entry corresponding to the entering variable j to 1, and setting the value of each basic variable index Bii) to d', with all other entries remaining zero (lines 15 18
Because of nondegeneracy, the else-block line T9 never entered, and all adjacent vertices are found after single iteration of the while-loop.
4.2.2 Edge case: degenerate vertices
In the degenerate case, multiple bases correspond to =*. This makes efficiently computing all adjacent vertices much more challenging, as they cannot all be obtained by performing pivots on any single basis B of 2²" In this case, some of the basis pivots performed in Algorithm [ have a step size of 8" = 0, and result in the same vertex 2². These pivots thus produce other bases associated with 2*, which subsequently have to be explored. Thus, ensure that all adjacent vertices of =" identified, one in principle needs to consider all pivot operations across all bases associated with 2*. However, as shown in and 23 this quickly becomes intractable.
Some work has aimed to address this, primarily between the late 1970s and early 1990s, but has since remained relatively obscure, receiving limited attention in recent research. For overview, we refer the reader to [13 [6]. Particularly relevant to this paper is the work by Geue [17] and Kruse (23] which showed that to compute all adjacent vertices of degenerate solution, not all bases of that solution need to be explored. It suffices to only consider those bases that can be reached through lexicographic pivoting [8. To further reduce the required number of pivots, Geue later introduced
a dedicated Transition Node Pivoting (TNP) rule [155. which we employ in Algorithm T More
information on the TNP rule can be found in Appendix C
To systematically explore bases using the TNP rule, we use the Queue and Visited data structures initialized in lines [ respectively. When an entering variable results in step size 0 0 in line 13 the algorithm applies the TNP rule to select leaving variable (line (0ine If the resulting basis is not in Visited yet, it is added to the Queue for later exploration. The Visttdd set ensures that each basis is processed only once, preventing redundant pivot operations.
4.3 Putting it together
Given a dataset D (()),, or == ((x, (c))), we use Algorithm find all adjacent vertices Zadz (z" (c)). For each =" (c) this will be an kxn matrix with & the number of adjacent vertices. Using these matrices, we can train a predictive model m. over dataset D with LAva (m) 2 (c)).
5 Experimental evaluation
We evaluate our method against state-of-the-an approaches, focusing on the trade-off between training time and decision quality, and how performance scales with the number of variables and constraints.
5.1 Experimental setup
Here we give an overview of our experimental setup; more details can be found in Appendix D The
models are linear regressors, as is common in existing literature [10 24 26 28 34] We train these models using the Adam optimizer [22]. All hyperparameters are tuned on independent validation sets prior to training. We train the models until their performance on the validation set has not improved by at least 1% for three checks a row, or until training time has surpassed 600 seconds (not including evaluation on the validation set), whichever comes first. For LAVA, this training time includes both adjacent vertex precomputation and actual training. We report the test set performance of the model state that led to the best validation set performance during training. When reporting
7

---

training times, we report the time it took to reach this state. Reported results are the average taken over 5 independent runs with varying cain-validation-tess splits. We report the normalized regret:
Eueet c 2* (c) c (c)
Normalized Regret
(5)
E c (²)
All experiments were conducted on a machine equipped with an Intel(R) CTr)(TM) 17-1165G7 processor and 16 GB of RAM. All code is implemented in Python, and builds the PyEPO
library 38 Our code and data are available at https//gthhlloomm./.K/LLLaaaaaee DFL/
5.2 Baselines
We compare with the same set of methods as used in the evaluation of [39] These methods are:
1. Mean Squared Error (MSE): This method minimizes the mean squared error (MSE) between the predicted cost coefficients and the ground-truth cost coefficients c. This not a decision-focused approach, but is typically included in DFL evaluations to demonstrate the decision quality obtained when predictive accuracy maximized during training.
2. Smart Tredict-Then-Opieee
(SPO+): This the smart sendict-the-oppimiiie approach from [10], which minimizes the surrogate SPO+ loss, convex upper bound of the regret that uses the true cost vector This method generally achieves great decision quality in existing comparative analyses 26 38
3. Perturbed Tenchel-Young Loss (PFYL): This method, proposed in 4 uses the Fenchel- Young losses from [6] in combination with an approach that obtains informative gradients through perturbation of the cost vectors é. The size of the perturbations is controlled by hyperparameter a.
4. Noise- Contrastive Estimation (NCE): This method compares the quality of the optimal solution with a set of suboptimal solutions that is gradually grown throughout training (88) This method was introduced with the intention of improving the efficiency of DFL. For only 5% of the instances in each epoch, solver is used to compute solution and add it to the pool of feasible solutions; the other 95% use the pool is.
5. Cone-Aligned Vector Estimation (CaVE): This method projects the predicted cost vector onto the optimality cone of the optimal solution. Doing so involves solving a non-negative least squares problem, which is QP. The intention is that solving this QP is computationally cheaper than solving the original LP.
worth noting that MSE and SPO+ are given access to the true cost vectors c, as they are only applicable in the complete information setting. PFYL, NCE, CaVE, as well as proposed LAVA also work in the incomplete information setting, and do not require access to c.
is
5.3 Benchmarks
We compare these methods on the following predic--hhen-optimize benchmarks, listed in increasing order of degeneracy. We refer to Appendix D for further details.
Random LPs: We construct LPs by sampling the entries of and i uniformly at random,
which ensures that the feasible space contains only nondegenerate vertices [19]. Each LP contains 150 variables and 50 constraints. We make sure that all generated constraints are nonredundant. As true mapping between features and cost values, we use degree 8 polynomial that is approximated using linear regression to simulate model misspecification.
This is common practice in DFL evaluations 110 24 34 38 39], and is especially relevant when training interpretable models [I| 21 37/.
2. Multi-dimensional knapsack: The optimization task
nulti-diimesioonll knapsack problem, as also considered in [25] 28 38). Because this problem has integer variables, we compute the adjacent vertices for LAVA on its LP relaxation, but evaluate the test set regret on the original integer problem. In the first experiment, the problem is three-dimensional and considers 300 items. In the second, we vary the problem size. Most vertices are nondegenerate, some are slightly degenerate. We use real-world data, taken from common
8

---

MSE
SPO+
PFYL
NCE
CaVE
LAVA (Ours)
Random LP
Multi-dim, Knapsack
Shortest path
Test Regret
10
6x
200
10 Training Time (s)
Training Time (8)
Training Time 69)
Figure 2: Comparison the efficiency of different methods
machine learning benchmark which the median house prices of districts in California must be predicted from 8 correlated features, including spatial features, features about the districts' populations and other aggregate housing statistics [31]
3. Shortest path: We include this common benchmark from the DFL literature [10 24 26 28 The optimization problem involves computing the shortest path from the bottom-left node to the top-right node of a 5 x 5 grid, giving rise to 40 variables and 25 constraints. The predicted values serve edge costs in the grid. The true predictive mapping is the same as used in the first benchmark. All vertices are highly degenerate, making this a particularly challenging benchmark for our method.
5.4 Results and discussion
Figure shows the training time and test set regret (log scale) of the various methods (full results with standard eиrors given in tabular format in Appendix(E). LAVA is Pareto-efficient all benchmarks, meaning is never bested both training time and test regret by another method. On the random LPs and multi-dimensional knapsack problems, it offers highly desirable trade-off: training time is reduced significantly with minimal degradation in solution quality compared to the best- pest-performing methods (SPO+ and PFYL). On the highly degenerate shortest path problem, the relative test regret of LAVA is slightly worse, and the improvement in training time less significant. Despite the shortest path being the smallest problem considered, it is the benchmark on which LAVA takes the longest. Figure 3 shows why: the majority of LAVA's 's computation time spent precomputing the adjacent vertices, which is compu- tationally expensive due to the shortest path's 's high degree of degeneracy (see Section 4.2.2p. Because of this, LAVA may be the most appropriate method to address network flow prob- lems, which tend to be highly degenerate problems do not suffer much from efficiency issues in the first place, as specialized solving algorithms are available [3] 30].
Computing Vert
Traning Time (g)
10.0
Fortunately, these
7.5
0.5
5.0
50
F also highlights another advantage of LAVA. In hyperpa- rameter tuning, the adjacent vertices can precomputed once and subsequently used in each configuration explored. Since the majority of LAVA's computation time is spent on this pre- computation, the tuning process becomes particularly efficient.
Random LP
Knapsack Shortest Path
Figure 3: Breakdown of LAVA'S training time
Figure 4 shows how the training time and normalized test regret scale with increasing problem size. This is shown for the dulti--immnsionall knapsack problem, where we vary the number of items (i.e.. variables) and dimensions (i.e., constraints). The left column shows that LAVA's 's test regret remains on par with SPO+ and PFYL for increasing problem size. The right column shows that LAVA remains highly efficient when the problem size increases, whereas SPO+ and PFYL scale significantly worse. This is especially true for an increasing number of constraints, by which LAVA'S 's total computation time is largely unaffected.

---

NCE
Training Time (S)
Test Rugeeet
400
200
extent
Number of Hemm
Number
Teat Regret
Training Time
400
10-1
200
Ex
Number of Dimensions
Number of Dimensions
Figure 4: Comparison of performance in function of the problem size of multi-dimensional knapsack
6 Conclusions and future work
In this work, we significantly improve the efficiency of DFI. for linear predict-then-optimiz problems, by proposing solver-free method that exploits the geometric structure of these problems. Our method, named LAVA, compares the estimated quality of the known optimal solution with that of its adjacent vertices the feasible polytope, based on the insight that a solution is optimal if and only if it scores at least as good as its adjacent vertices. Experiments demonstrate that LAVA significantly reduces computational cost while maintaining high decision quality, and that it scales well with problem size.
Directions for future work include improving the performance of LAVA on highly degenerate problems, possibly through problem-specific adjacent vertex computation methods or heuristics. Another avenue to investigate ways for I.AVA to utilize the ground-truth cost coefficients when available (i.e., the complete information setting). Finally, extension of the approach to other problem classes, such as mixed-inte mixed-integer linear programs, through more principled methods than linear programming relaxation, another worthwhile direction.
7
Acknowledgements
This research received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (Grant No. 101002802, CHAT-Opt). Senne Berden a fellow of the Research Coundation-Flandee (FWO-Vlaanderen, IPPQ024N).
References
[1] Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and Zico Kolter. Differentiable convex optimization layers. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[2] Brandon Amos and J Zico Kolter. Optnet: Differentiable optimization as a layer in neural networks. In International Conference on Machine Learning, pages 136-145. PMLR, 2017.
[3] Mokhtar S Bazaraa, John Jarvis, and Hanif D Sherali. Linear programming and network flows. John Wiley & Sons, 2011.
[4] Quentin Berthet, Mathieu Blondel, Olivier Teboul, Marco Cuturi, Jean-Philippe Vert, and Francis Bach. Learning with differentiable pertubed optimizers. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 9508-9519. Curran Associates, Inc., 2020.
[5] Dimitris Bertsimas and John N Tsitsiklis. Introduction to linear optimization, volume 6. Athena scientific Belmont, MA, 1997.
10

---

[6] Mathieu Blondel, André FT Martins, and Vlad Niculae. Learning with fenchel-young losses. Journal of Machine Learning Research, 21(35):1 2020.
[7] George Dantzig. Maximization of linear function of variables subject to linear inequalities. Activity analysis of production and allocation, 13:339-344 -47, 1951.
[8] George B Dantzig, Alex Orden, Philip Wolfe, et al. The generalized simplex method for minimizing a linear form under linear inequality restraints. Pacific Journal of Mathematics, 5(2):183-195, 1955.
[9] Priya Donti, Brandon Amos, and Zico Kolter. Task-based end-to-end model learning in stochastic optimization. Advances neural information processing systems, 30, 2017.
[10] Adam N. Elmachtoub and Paul Grigas. Smart "predict, then optimize". Management Science, 68(1):9-22 26, 2022.
[11] Joseph Futoma, Michael C Hughes, and Finale Doshi- Popcorn: Partially observed prediction constrained reinforcement learning. arXiv preprint arXiv:200..04032 2020.
[12] Tomas Gal. On the structure of the set bases of degenerate point. Journal of Optimization Theory and Applications, 45:577-589, 1985.
[13] Tomas Gal. Degeneracy in mathematical programming and degeneracy graphs concise version of tutorial. Papers of the 19th Annual Meeting/Vorträge der 19. Jahrestagung. pages 73-86. Springer, 1992.
[14] Tomas Gal. Degeneracy graphs: theory and application an updated survey. Annals of Operations Research, 46:81-105, 1993.
[15] Tomas Gal and Ferdinand Geue. A new pivoting rule for solving various degeneracy problems. Operations Research Letters, 11 11(1):23-32, 1992.
[16] Tomas Gal, Hermann-Josef Kruse, and Peter Zörnig. Survey of solved and open problems in the degeneracy phenomenon. In DGOR/NSOR: Papers of the 16th Annual Meeting of DGOR in Cooperation with NSOR/Vorträge der 16. Jahrestagung der DGOR zusammen mit der NSOR, pages 612-621. Springer, 1988.
[17] Ferdinand Geue. An improved n-tree algorithm for the enumeration of all neighbors of degenerate vertex. Annals of Operations Research, 46:361-391, 1993.
[18] Bruce Golden, Linus Schrage, Douglas Shier, and Lida Anna Apergi The unexpected power of linear programming: an updated collection of surprising applications. Annals of Operations Research, 343(2):573-605, 2024.
[19] Clóvis C Gonzaga. Generation of degenerate linear programming problems. Journal of optimization theory and applications, 135:333-344 3323333422-44 2007.
[20] Frederick S Hillier and Gerald Lieberman. Introduction to operations research. McGraw-Hill. 2015.
[21] Michael C Hughes, Gabriel Hope, Leah Weiner, Thomas H McCoy Jr, Roy H Perlis, Erik B Sudderth, and Finale Doshi Velez. Semi-supervised prediction-constrrineedd AISTATS, pages 1067-1076, 2018.
constrained topic models. In
[22] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 14Xiv:1412.69800 2014.
[23] H-J Kruse. Degeneracy graphs and the neighbourhood problem, volume 260. Springer Science & Business Media, 2012.
[24] Jayanta Mandi, Victor Bucarey, Maxime Mulamba Ke Tchomba, and Tias Guns. Decision- focused learning: Through the lens of learning to rank. Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 14935-14944 PMLR, 17-23 Jul 2022.
11

---

[25] Jayanta Mandi and Tias Guns. Interior point solving for Ip-based prediction-opiimisstion In
H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 7272-7282. Curran Associates, Inc., 2020.
[26] Jayanta Mandi, James Kotary, Senne Berden, Maxime Mulamba, Victor Bucarey, Tias Guns, and Ferdinando Fioretto. Decision-focusee learning: Foundations, state of the art, benchmark and future opportunities. Journal of Artificial Intelligence Research, 80:1623-1701, 2024.
[27] Jayanta Mandi, Peter Stuckey, Tias Guns, et al. Smart predict-and-optimize for hard combina- torial optimization problems. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pages 1603-1610, 2020.
[28] Maxime Mulamba, Jayanta Mandi, Michelangelo Diligenti,, Michele Lombardi, Victor Bucarey, and Tias Guns. Contrastive losses and solution caching for gredict-and-otimme In Zhi-Hus Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelli- gence, IJCAI-21, pages 2833-28400 International Joint Conferences on Artificial Intelligence Organization, 8 2021. Main Track.
[29] Mathias Niepert, Pasquale Minervini, and Luca Franceschi. Implicit mle: Backpropagating through discrete exponential family distributions. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 14567-14579, Curran Associates, Inc., 2021.
[30] James B Orlin. A polynomial time primal network simplex algorithm for minimum cost flows. Mathematical Programming, 18:109-129, 1997.
[31] R Kelley Pace and Ronald Barry. Sparse spatial autoregressions. Statistics & Probability Letters, 33(3):291-297, 1997.
[32] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830. 2011.
[33] 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.
[34] Noah Schutte, Krzysztof Postek, and Neil Yorke-Smith. Robust losses for focision learning. 2023.
[35] Sanket Shah, Kai Wang, Bryan Wilder, Andrew Perrault, and Milind Tambe. Decision-focused learning without differentiable optimization: Learning locally optimized decision losses. arXiv preprint arXiv:2203. 16067, 2022.
[36] Sanket Shah, Bryan Wilder, Andrew Perrault, and Milind Tambe. Leaving the nest: Going beyond local loss functions for on Artificial Intelligence, volume 38, pages 14902-14909, 2024.
In Proceedings of the AAAI Conference
[37] Abhishek Sharma, Catherine Zeng, Sanjana Narayanan, Sonali Parbhoo, and Finale Doshi- Velez. On learning prediction-focusee mixtures. arXiv preprint 10.:22100.1322.. 2021.
[38] Bo Tang and Elias B Khalil. Pyepo: A pptorchh based end-to-end predictthenn-ppimiie library with linear objective function. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop), 2022.
[39] Bo Tang and Elias B. Khalil. Cave: A cone-aligned approach for fast predict-then--opimmize with binary linear programs, 2024.
[40] Bryan Wilder, Bistra Dilkina, and Milind Tambe. Melding the data-decisions pipeline: Decision- focused learning for combinatorial optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):1658-16)) -1655 Jul. 2019.
[41] Wayne I. Winston. Operations research: applications and algorithm. Thomson Learning, Inc., 2004.
12

---

A Proof of Proposition 4.1
We start by repeating Proposition here:
Proposition A.1. Let 2 be a vertex of the feasible polytope, and let Zadj(2 be the set of vertices adjacent to 2. Vertex is an optimal solution for cost vector if and only if c S c Zadj for all Zadj Zad (2).
This is well-known property of linear programming. and is the basis of the simplex method S
For instance, stated in standard texthook (20) as 'Property 3', though without formal proof. For the sake of completeness, and to provide some intuition for why it holds, we formally prove the proposition here.
Proof. The forward implication holds trivially: if an optimal solution for cost vector then Vz' E F: c_ < c. c² where F denotes the feasible region (F E R Az b, 2 0}).
Since Zost (z) F. it holds that Vzadi E Zudt (z) c S c Zudj-
We must prove the backward implication. That is, must prove that if VZudj E Zady (2)
c 2 S c. zuzzdj
Radj holds, then is optimal for cost vector
We prove this by contradiction. Assume Viady E Zodz : c. S c_ Zndj holds, but that there exists a a E F for which c. ''' <.
We know that the feasible region FF is convex polytope. Thus, the vector 2' can be written conic combination the differences {Zadj - 2 Zadj E Zudz}:
YE
0: 0:
Σ
Xz(Eadj - =)
(6)
Now, since cT < cT,, z, must hold that
c cT z) <0
1
<>
Σ
de(Zndj - 2) <0
Zusil
Σ Ape [ - -2) =))<0
However, because of the assumption that Vzadj E Zadz (2) : 2 S Zadj. and because each À > 0. each summand Açc (Zadj 2) must be nonnegative. This is a contradiction. Thus, is optimal. _
B Ablation of thresholding in LAVA
In Table I show the importance of thresholding the LAVA loss zero (i.c., e using a small constant (e.g.. = 0.1), in comparison with removing the threshold (i.e., e = oo). In Figure we show the effect of using small non-zero value for on the learning curves, using the random LP benchmark.
Table 1: Test regrets of LAVA for various thresholds
Method
Random LP
Multi-dim. Knapsack
Shortest Path
LAVA (e 0)
0.023 + 0.001
0.127 + 0.007
0.061 + 0.008
LAVA (e 0.1)
0.016 = 0.001
0.086 + 0.002
0.060 +'2 0.012
LAVA (e = oo)
0.166 = 0.009
0.156 + 0.003
0.243 + 0.022
13

---

LAVA (Val)
LAVA (g 0.1) (Train)
LAVA (e D.13 (Val)
Rogret (log
10-1
10
20
60
80
100
Epoch
Figure 5: Learning curves for LAVA on the random LP benchmark, comparing margin parameter
values 0 and 0.1.
C More information on the TNP rule
When vertex is degenerate, has multiple corresponding bases. This makes efficiently computing all adjacent vertices of 2" much more challenging, as they cannot all be obtained by performing pivots on any single basis B z². To ensure that all adjacent vertices of = are identified, one in principle needs to consider all pivot operations across all bases associated with z. However, for o-degenerate n-dimensional vertex z* where a refers to the number of zero-valued basic variables this number
of bases is lower-bounded by Umin 2 (n a + 2) [23]. and upper- hounded by Umaz ("+o)
[1]. For instance, for 100 and a 30, U Unin 3.865 1010 and Umaz 2.6 10 This makes the exhaustive exploration of all bases of 2* intractable.
This has inspired an investigation into more efficient ways of generating all adjacent vertices of a degenerate vertex - problem which sometimes gets referred to as the neighborhood problem 233. Some work has aimed to address this, primarily between the late 1970s and early 1990s, but has since remained relatively obscure, receiving limited attention in recent research. This line of work takes a graph-theoretir approach to the neighborhood problem. It associates with degenerate vertex x* a degeneracy graph G(z*) = (V, E) where = {B] is a feasible basis of 2*} and E = [[B., B. C V B. + B In words, the nodes of the graph are the bases associated with z", and an edge connects two bases if one can obtained from the other through a single pivot operation. The nodes be further separated into two types: internal nodes and transition nodes. Internal nodes correspond to bases from which all possible pivots lead to other bases associated with the same vertex 2². Transition nodes correspond to bases for which at least one basis of an adjacent vertex Zndj can be reached through a pivot. This framework of degeneracy graphs has led numerous valuable insights into various aspects of linear programming. including cycling in the simplex method, the neighhorhood problem, the construction of degenerate solutions, and sensitivity
analysis. For overview, refer the reader to 13 14 16)
Particularly relevant to this paper is the work by Geue [17] and Kruse 223, which showed that to compute all adjacent vertices of a degenerate solution, not all bases of that solution need to be explored. It suffices to only consider those bases that can be reached through lexicographic pivoting (8). To further reduce the required number of pivots, Geue later introduced a dedicated Transition Node Pivoting (TNP) rule [15], which we employ in Algorithm [ The TNP rule is a pivoting rule that only pivots from transition nodes other transition nodes, and that ensures that with each pivot, at least one new basis of an adjacent vertex is discovered. This is a desirable property, internal nodes do not contribute directly the solution of the neighborhood problem.
To apply TNP pivoting, we must start from a transition node associated with z². If our initial basis is not a transition node, can obtain one by applying random pivots (with respect to anti-cycling rule S Since the starting node is now a transition node, there will be a column d of D -- 1
such that min {i|d.<0}
(- (Bowrr())
> i.e. 0" > in the minimum ratio test (line 13 in Algorithm
This column is referred to as the transition column, and is denoted by L. This column will remain a transition column throughout the subsequent TNP pivots. The TNP rule comes into effect when, for an entering variable with index j. 0* 0 (line 13 of Algorithm I and there multiple
14

---

minimizers, i.e.,
3 ( 03. The TNP rule used to decide r() 1, where 7(5) men
{i
d,
which i min select as leaving variable. This selected max | Diy |k 1 which ensures that & remains a transition column. For proof of this statement, as well further details on the TNP rule, we refer the reader to [5] and
D Further details of experimental setup
D.1 Hyperparameters
All methods were tuned that led to the best validation set regret was selected. Considered values for the learning rate were 0.001, 0.01, 0.1 and 1. For all methods, 0.01 performed best. For PFYL, considered values for were 0.01, 0.1, 1 and 10. For the random LPs, 0.1 performed best. For the multi-dimensional knapsack problem and the shortest path problem, performed best. A single perturbed cost vector was sampled per backward pass. For NCE, the solve ratio was set to 5%. For CaVE, both the CaVE-E and Ca variants considered. On random LPs and the shortest path problem, CaVE-E performed best. On the multi-dimmensonall knapsack problem, CaVE+ performed best. For LAVA, e = 0.1 was chosen for all benchmarks.
validation set per benchmark. The hyperparameter configuration
D.2 Optimization problems
Random LPs:
Random linear programs were generated in the form {a E R" A= <, 0}.
which were subsequently converted to standard form. The entries of were sampled uniformly from the interval [0, 1]. The right-hand side vector b was determined in two stages. First, a solution vector 2 was sampled uniformly from [0, 1]. The initial entries b were then set as Az". Subsequently, 50 randomly selected entries of b were increased by a random value sampled uniformly from [0, 0.2). A check was performed to ensure that none of the generated constraints were redundant (i.e., implied by other constraints). No further modifications described above, applied to the specified problem dimensions (100 variables and 50 constraints), did not produce any redundant constraints.
necessary to achieve nonredundancy. The process
Multi-dimensional knapsack: Given a set of items I = (l,..., n). where each item i E Z has value c; and weight wiy for each of knapsack constraints, the nulti-dimensional knapsack problem seeks to find the subset of items with maximum total value without exceeding the capacity W, for each constraint j E [1....,m].
Let
[
if item i is selected
24
0 otherwise
for all i E I. The problem can then be formulated as follows:
max
Σ Ci
(10)
NEI
s.t.
Σ
Wiy2i S W,, Vj (1...,,m)
(11)
NET.
2; E {0,1} VIEI.
(12)
The objective function 100 maximizes the total value of the selected items. Constraints (11) ensure that the weight of the selected items does not exceed the capacity for each dimension j. The domain constraint (12) specifies that each item can either selected in its entirety, or not at all. In generating the multi-dimensional knapsack problems, the item weights were integer values sampled uniformly at random from [1, 10), and the capacity in each constraint was set to 10% of the sum of the weights in that constraint.
15

---

Shortest path problem: This problem is taken from [0], and was also used in [24 26 28 Consider directed 5x5 grid graph G (V, E) where each node (i.j) E V connected its right and upward neighbors, forming directed acyelic graph. Each edge (i,j) E E has an associated cost Caj- The objective to find the shortest path from the bottom-left node (1, 1) to the top-right node (5,
Let
Zij = [1
if edge (i.j) is included in the path otherwise
for all (1,5) E E. The shortest path problem can then be formulated as the following linear program:
min
Σ
(13)
(i,))E
s.t.
Σ
Z1j =
(14)
J: (L,))EE
Σ
215
(15)
#: (1,5)
Σ
2kj
Σ
2sk =0
Ak E V (5,1),
(16)
J: (EJ)EE
8: (3,))EE
(17)
The objective function of flow is sent out from the bottom-left node (1, 1). Constraint (15) ensures that unit of flow is received at the top-right node (5, 5). The flow conservation constraints (16) maintains flow balance at each intermediate node.
1 minimizes the total cost of the path. Constraint [4] ensures that one unit
Since edges only exist to the right or upwards, the set of edges E can explicitly defined as:
E' {((i,)) (i+ 1.5) i< ((.)) 1j < 5}
D.3 True predictive mappings
Polynomial mapping:
This mapping is commonly used in experimental evaluations of DFL
methods. It was introduced [00, and was later considered in (24]] 26
39].
The data generating process is the following. First, we generate the parameters of the true model as 40 matrix B, wherein each entry is sampled from Bernoulli distribution with probability 0.5. We then generate features-targer pairs as follows:
1. First, each element of feature vector x E RR:5 is sampled from the standard normal distribution (0, 1).
2. Then, the corresponding target value cj E IR is generated as follows:
Cj
1
1
[ [Tx
3)de Ej
3.5deg
5
where èj is sampled uniformly from [1 E, 1
+ E).
In our experiments, we use deg = 8 and غ 0.
California house prices: This prediction task is taken from a common machine learning benchmark 31), which offered as a benchmark the scikit-learn Python package (32] this benchmark, the median house prices of districts in California must be predicted from 8 correlated local features, including spatial features, features about the districts' populations and other aggregate housing statistics.
16

---

Table 2: Test regrets with standard errors for different methods
Method
Random LP
Multi-dim. Knapsack
Shortest Path
MSE
0.136 + 0.003
0.103 + 0.002
0.144 + 0.023
SPO+
0.015 = 0.001
0.082 = 0.001
0.052 + 0.007
PFYL
0.017 = 0.001
0.082 = 0.001
0.055 + 0.010
NCE
0.025 = 0.001
0.159 = 0.003
0.151 + 0.016
CaVE
0.017 + 0.001
0.111 + 0.002
0.080 + 0.014
LAVA (Ours)
0.016 + 0.001
0.086 + 0.002
0.060 + 0.012
Table 3: Training times with standard errors for different methods
Method
Random LP
Multi-dim. Knapsack
Shortest Path
MSE
0.0 0.0
0.0 0.0
0,0
SPO+
180.2 + 21.8
303.3 + 74,6
18.6 1.3
PFYL
105.7 + 11.8
581.1 8.4
3.66
NCE
8.1 0.4
15.6 5.3
0.6
CaVE
469. 37.1
173.5
3,4
LAVA (Ours)
5.8 0.1
9.8 1.4
13.0 1.0
E Results in tabular form
Tables and show the results of Figure in tabular form.
F
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: propose new loss function and highlight some of its properties in the abstract and introduction. We elaborate on these in Section 4.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The main limitation of our methodology its limited applicability on highly degenerate problems, as highlight our discussion of the experimental results (Section
5), and in the conclusion (section 6).
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: prove Proposition 4.1 in the appendix.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: We provide detailed pseudocode Algorithm 1, and detail the experimental setup in Section 5.1 Further details and hyperparameter values are provided in the appendix.
5. Open access to data and code
17

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Our code and data are available at https///gghuabacoo///////UUlllls
Free-DFLJ
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: We detail the experimental setup in Section 5.1 Further details and hyperpa- rameter values provided in the appendix.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: standard errors for Figure are reported in the appendix. Stardard errors for Figure 3 are shown on the figure.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: This information is listed in Section 5.1.
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://aaaarg...co/bb/o///ccceee
Answer: [Yes]
Justification: The paper adheres to the code of ethics.
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no direct societal impact of the work performed. We also see no direct path to negative applications.
Guidelines:
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:
The paper poses no such risks.
12. Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
18

---

Justification: We refer to the assets we use in sections 5.1 and 5.3.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Other than the code and data already covered by point 5, the paper does not release assets.
14. 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 participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects. 15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: 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?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
16. Declaration of LLM usage
Does the paper describe the usage of LLMS if 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, formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, non-standard components.
19


Reviews:
[{"review_id": "6pkjxDOq8T", "reviewer": "Reviewer_rtAP", "summary": "- This paper proposes a novel, solve-free decision-focused learning method that eliminates the need to solve optimization problems during the learning process.\n- Focusing on Linear Programs (LPs), the research leverages the property that if the feasible region is non-empty and bounded, at least one optimal solution exists at an extreme point of the polyhedron.\n- Based on this property, the paper introduces a new loss function, LAVA (Loss based on Adjacent Vertices Approximation), which is derived from the difference in objective function values with extreme points adjacent to an observed solution.\n- The proposed regret minimization approach offers the advantage of not requiring an optimization problem to be solved. Numerical experiments demonstrate that the proposed method enables fast learning, especially for non-degenerate problem instances.", "questions": "- As for the first point in the weakness I raised, the rationale behind the margin parameter's contribution to stabilizing the learning process isn't entirely clear. Could the authors explain in more detail how this margin helps stabilize learning?\n- In Line 168, the authors state that LAVA is differentiable. Is this really true? LAVA is a point-wise maximum of linear functions for $\\hat{c}$, so I understand that while its subgradient can be calculated, it is not generally differentiable. Please clarify if I've misunderstood.\n- Can the proposed method be applied even when the observed solution is not an extreme point of the polyhedron? If an observed optimal solution lies on a facet and is not an extreme point, is it still possible to enumerate adjacent extreme points?\n- Figure 4 shows that the training time of the proposed method increases more quickly when the number of items changes from 200 to 400. Might the computational time advantage of the proposed method disappear when dealing with more than 400 items?\n- When training a model to predict the cost vector $c$ by minimizing LAVA, it appears that a model consistently predicting a zero vector for $c$ might be optimal. Such a model would render all feasible solutions optimal, which would be practically worthless in decision-focused learning. Is my understanding correct? Or does the proposed method naturally avoid such an undesirable model?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "- Strengths\n\t- Decision-focused learning, which involves training prediction models by considering the performance of optimal solutions, is a major topic in machine learning. The computational time involved in decision-focused learning is a widely recognized practical challenge. This paper proposes an efficient learning method that leverages the polyhedral structure of LPs, showing a significant reduction in computation time for small-scale problems. This result appears to be a valuable contribution within the decision-focused learning framework.\n\t- Beyond demonstrating the effectiveness of the proposed method, the experiments carefully address and discuss the computational bottleneck of calculating adjacent extreme points when problems are degenerate. The experimental results presented in this research are well-argued and convincing.\n\t- The paper itself is well-written and easy to read. \n- Weaknesses\n\t- The effect of introducing a margin in the proposed method isn't well understood. The paper states that introducing a margin stabilizes the training process, and Appendix B shows it reduces variance and improves the average behavior of regret. However, the reason why such a margin can contribute to stabilizing the learning process needs a more thorough discussion.\n\t- While it is inevitable, given the nature of the proposed method, it strongly relies on the properties of LPs. Consequently, its extensibility to more general Mixed-Integer Programs (MIPs) or convex optimization problems in a decision-focused context appears limited.", "was_revised": true, "final_justification": "The authors have sincerely addressed all of my comments. While I recommend they revise the manuscript to incorporate these points, I believe the paper is suitable for publication.", "rebuttal": "Thank you for your thoughtful and constructive review. We are glad to read that you found our paper a valuable contribution to the decision-focused learning literature, and are pleased that you support acceptance of the paper. Below, we address the questions posed in the review. \n\n \n\n**LAVA for (mixed-)integer linear programs:** For our discussion of this matter we refer to our response to reviewer vtoW. Given that three reviewers posed questions regarding the use of LAVA on (M)ILPs, this point warrants additional attention in the paper, and we will add this discussion to the camera-ready version on acceptance. \n\n \n\n**Rationale behind margin parameter:** The margin $\\epsilon$ is introduced to create a buffer zone: without it, the loss related to a single adjacent vertex becomes zero as soon as the optimal solution is of equal value or preferred. However, subsequent updates (e.g., from other training instances) may shift the predicted cost vector slightly such that this adjacent vertex becomes preferred again. The margin prevents this by requiring a stronger preference for the optimal solution. Empirically, this leads to smoother learning curves and improved decision quality at convergence. We will extend our discussion of this matter in the main text, and can add a figure comparing the learning curves with and without margin to appendix B. \n\n \n\n**Gradient vs subgradient:** We thank the reviewer for pointing this out. Indeed, each term of LAVA is a hinge-like $\\max(\\hat{c}^\\top z^\\star(c) - \\hat{c}^\\top z_{adj}, -\\epsilon)$, which is not smooth at the kink where $\\hat{c}^\\top z^\\star(c) - \\hat{c}^\\top z_{adj} = -\\epsilon$. However, those kink points constitute a measure-zero set (i.e., the probability of ending up exactly at a kink point is zero), so LAVA is differentiable almost everywhere. In practice we optimize it with standard gradient methods without ever encountering nondifferentiable updates. We will update the discussion at line 168 in the paper to clarify this. \n\n \n\n**What if observed point not on a vertex:** If an optimal solution lies on a facet, one can always find at least one optimal vertex solution of the same objective value. In principle, one would first have to compute one of these optimal vertices before applying Algorithm 1. However, this scenario is unlikely in practice because (i) the simplex algorithm always terminates at a vertex and (ii) the set of cost vectors that have optimal solutions on facets of the feasible space has measure zero (i.e., is negligible). \n\n \n\n**Runtime increase going from 200 to 400 items:** We want to note that the training time increase going from 50 to 100 variables and from 100 to 200 variables are not collinear either. Admittedly, this is hard to notice on the figure, since the training times using LAVA are close to zero on the problems with less than 400 variables. This result is not entirely unexpected, however, as the computational complexity of Algorithm 1 (in the non-degenerate case) is $O(n^3)$ (see also our response to reviewer qHeU). We further investigated the runtime on the problem with 400 variables. A large portion of this time was spent precomputing the adjacent vertices of a handful of highly degenerate instances. We expect that on this problem, much faster performance with negligible degradation of decision quality can likely be achieved by, for example, treating Algorithm 1 as an anytime algorithm, and stopping the computation on highly degenerate vertices before completion after some timeout is reached. As discussed in the future work section, we consider the development of such strategies for highly degenerate vertices a promising direction for future work. \n\n \n\n**Predicting zero vectors:** This a good observation that warrants some additional discussion in the main text, which we will include. Each vertex of the feasible space has a convex polyhedral optimality cone of cost vectors that make this vertex optimal. The zero vector is indeed an element of each of these cones. Thus, in principle, predicting the zero vector is one way of minimizing LAVA (at least when margin $\\epsilon$ is set to zero). However, as long as the predictive model’s parameters are initialized randomly (or in some other way that prevents the initial prediction of zero vectors), the use of LAVA is extremely unlikely to converge to this undesirable model. This can be seen as follows. Assume that there is an optimal solution $z^\\star(c)$ in the training set, and that current prediction $\\hat{c}$ prefers an adjacent solution $z_{adj}$ to $z^\\star(c)$. This wrongful preference contributes $\\hat{c}^\\top z^\\star(c) - \\hat{c}^\\top z_{adj}$ to the loss. The corresponding gradient is $z^\\star(c) - z_{adj}$, i.e., a gradient descent step will 'push' the predicted cost vector $\\hat{c}$ in the direction of the difference between the optimal solution and the adjacent solution. If one imagines this update applied to Figure 1 in the paper, one can see that this does not converge to the zero vector (unfortunately, we cannot provide a new figure illustrating this point, as this would violate NeurIPS’ rebuttal policy). That being said, it may be possible to manually construct pathological scenarios in which this gradient direction happens to align exactly with $-\\hat{c}$ simultaneously for every instance in the training set, such that the model would converge to predicting zero vectors. However, this is extremely unlikely and not something we have ever encountered in practice."}, {"review_id": "aoxkF47CtF", "reviewer": "Reviewer_vtoW", "summary": "This paper introduces a new loss called LAVA for decision-focused learning (DFL), which enables solver-free training. In DFL, the parameters of a statistical model are chosen to optimize performance on a downstream optimization task, typically a linear program (LP) or mixed-integer linear program (MILP) whose cost vector $c$ must be predicted. In this setting, the non-differentiability of the mapping from cost $c$ to (MI)LP solution $z^{\\star}(c)$ is the main challenge limiting gradient-based training. While most existing methods require calling the optimization solver or a relaxation of it, LAVA instead relies on the geometric structure of the feasible set (a polytope) to evaluate the quality of a cost vector prediction $\\hat{c}$. If the predicted $\\hat{c}$ favors one of the neighbor vertices of $z^{\\star}(c)$, then it is suboptimal and penalized as such. The resulting loss has nice theoretical properties (differentiability, convexity) and can be obtained very efficiently once the set of adjacent vertices for each optimal solution in the training set has been precomputed. Experiments on three benchmark problems against a variety of DFL algorithms demonstrate that LAVA reaches a new Pareto optimum between training time and solution quality.", "questions": "- Do you have any idea how to generalize this approach to the integer case? The CaVE paper discusses this aspect with their optimal subcone, does any of their insights generalize to your method?", "limitations": "Yes.", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "## Strengths\n\n### Quality\n\n- The LAVA loss is very fast to compute, differentiable, convex, and grounded in an understanding of polytope geometry, which makes it a very promising addition to the DFL arsenal.\n- Initial experimental evaluation is very convincing.\n\n### Clarity\n\n- The exposition is remarkably clear and precise, as is the motivation.\n\n### Significance\n\n- This paper single-handedly changed my mind on solver-free approaches. My previous opinion was that they cannot work since they do not leverage the geometry of the problem, but LAVA proves that geometry awareness does not have to be mediated by solver calls. I strongly expect it to become a reference approach in this field.\n\n### Originality\n\n- The authors did genuinely engage with research on linear programming to precompute neighbors for degenerate vertices. This cross-fertilization between operations research and machine learning is more than welcome.\n- The comparison with CaVE is enlightening: while both methods focus on aligning the objective vector with the normal cone of the optimal vertex, LAVA gets rid of the costly projection step at the cost of additional precomputation.\n\n## Weaknesses\n\n### Clarity\n\n- Figure 4 is slightly hard to read, especially for colorblind readers like myself different linestyles would be helpful here.\n\n### Significance\n\n- My main worry about this method is whether it can truly scale to large instances, because all of the experiments are on very small problems. When facing larger instances, not only would degeneracy become much more of an issue: computational bottlenecks while solving the linear system $B^{-1} N$ might be encountered.", "was_revised": true, "final_justification": "My score was already maximal and the rebuttal comforted it.", "rebuttal": "Thank you for your constructive and positive review. It is especially gratifying to read that our work shifted your perspective on solver-free approaches. We appreciate your strong endorsement and are encouraged by your view that the method may become a reference in the field. Below, we address the questions posed in the review. \n\n \n\n**LAVA for (mixed-)integer linear programs:** When the optimization problem has integer variables, the adjacent vertices can be computed using the LP relaxation of the problem. The effect of doing so depends on the properties of the original problem. \n\n \n\nIf the original problem is a binary ILP, then each optimality cone in the LP relaxation is a subset of the corresponding optimality cone in the binary ILP (Figure 2 in the CaVE paper [39] gives a nice illustration of this). This aspect is indeed discussed in [39], and has the same implications for LAVA. Like for CaVE, the consequence of this is only that the LAVA loss can be somewhat conservative on these problems: it will always try to push predicted cost vectors into the *correct* optimality cone, but it may push them further into the cone than they strictly need to be. \n\n \n\nIf the original problem is a non-binary ILP or a mixed-integer program, then there is no guarantee that the cone in the LP relaxation is a subset of the original optimality cone. In this case, the performance of the strategy described above will largely depend on the integrality gap of the LP relaxation (see, for example, the related discussion on strong formulations of MILPs in Section 1.7 and the linear relaxation of MILPs in Section 2.2 of Laurence A. Wolsey - Integer Programming (1998, Wiley)). For problems with a small integrality gap, LAVA will likely work well. For problems with a large integrality gap, performance may be worse. For this reason, we think that exploring alternative adaptations of LAVA for non-binary ILPs and MILPs with large integrality gaps is a worthwhile direction for future work. \n\n \n\nGiven that other reviewers also posed questions regarding the use of LAVA on (M)ILPs, this matter warrants additional attention in the paper, and we will add this discussion to the camera-ready version on acceptance.  \n\n \n\n**Scaling with instance size:** Solving the linear system $-B^{-1}N$ has a complexity of at most $O(n^3)$ and can be done extremely efficiently with publicly available solvers. We expect that problems would have to be of very large sizes before the solving of this system would start to form a bottleneck. Even if this scenario were to occur, approximate solving methods can be used to quickly compute approximate solutions to the system. After all, even if the adjacent solutions computed would not be correct up to high numerical precision, they would likely still be accurate enough to produce informative gradients to train the predictive model with. \n\n \n\nWe would also like to emphasize that the problems considered in our work are not small compared to those commonly used in the DFL literature. For example, benchmark datasets in the PyEPO library [38] – including shortest path, multidimensional knapsack, and travelling salesperson problems – contain 40, 32, and 190 decision variables, respectively. The Warcraft shortest path problem in [33] involves 144 variables, while the knapsack instance from [28] has 48 variables. Other problems, such as cubic top-k, web advertising, and portfolio optimization from [35] and [36] each involve 50 variables. In comparison, our problems contain 40, 150 and 300 decision variables. These are therefore comparable in size or larger than those used in related work. \n\n \n\n**Clarity of Figure 4:** Thank you for bringing this to our attention, and we apologize for the oversight. We will improve the legibility of Figure 4 and update it using different linestyles."}, {"review_id": "Y1p4eza2Qu", "reviewer": "Reviewer_GG1N", "summary": "This paper proposes a solver-free decision-focused learning (DFL) method for linear optimization problems. Specifically, it considers the prediction-then-optimize problem setting, where we need to train a machine learning model to predict the unknown parameters of an optimization problem, and then solve the optimization problem with predicted parameters. \nDFL is typically computationally expensive as it requires solving the optimization problem with the predicted parameters at each loss evaluation. To address this challenge, this paper proposes a Loss via Adjacent Vertex Alignment (LAVA), which evaluates the predicted cost vector without explicitly solving the optimization problem. Based on the insight that a solution is optimal if and only if it achieves an objective value that is at least as good as that of its adjacent vertices on the feasible polytope, the proposed loss measures how the derived objective of the how well the predicted cost vector distinguishes a true optimal solution from its adjacent vertices.\nExperiments demonstrate that the proposed method can achieve a favorable trade-off between computational efficiency and predictive performance.", "questions": "1.\tAlthough the proposed method may achieve a favorable trade-off between computational efficiency and performance, is it possible to sacrifice training efficiency for better performance, or vice versa? If not, how could we conclude that the proposed method is better than others that are also on the Pareto frontier?\n2.\tIt would be better to present some more real-world applications of the considered settings, especially the incomplete information setting.", "limitations": "This paper focuses on linear optimization problems. However, it seems nontrivial to extend the proposed method to harder problems like mixed-integer linear programs, as it leverages the special properties of linear optimization. Moreover, it focuses on linear regression as the predictor. These limitations may hinder its broad application.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n1.\tThe presentation is good, including the problem formulation, the motivation statement, and the method illustration.\n2.\tThe proposed method mitigates the need to solve the problem and is motivated by the theoretical property presented in Proposition 4.1. The idea makes sense and is easy to implement.\n\nWeaknesses\n1.\tAlthough the loss function is motivated by Proposition 4.1, it would be better if the authors could present more theoretical analysis on the impact of the loss function impact on the final objective. For example, is it possible to present a theorem that if the loss is fewer than some threshold then the final objective would have a quality guarantee?\n2.\tAccording to the experiments on shortest path, the degeneracy may hinder the application of the proposed method. It would be better to conduct experiments on more datasets with degeneracy and to further investigate the relationship between the degree of degeneracy and the performance.\n3.\tIn the experiments, only linear regression is considered as the predictor. I wonder whether stronger predictors would improve the prediction accuracy and thus improve the final objective performance. It would be better to investigate the influence of the prediction accuracy on the final performance.", "was_revised": true, "final_justification": "Although LAVA still has minor limitations, such as its unability to control the trade-off between training time and decision quality and to handle MILP problems, I would like to retain my positive score.", "rebuttal": "Thank you for your review and for acknowledging the clarity of our presentation and the soundness of our approach. We appreciate your positive evaluation and your recommendation for acceptance. Below, we address the questions posed in the review. \n\n \n\n**Trade-off training time and decision quality:** LAVA does not offer a direct control mechanism to balance the trade-off between training time and decision quality. However, looking at Figure 2, we would argue that its performance results in the most desirable trade-off between these two objectives. For instance, on the multi-dimensional knapsack problem, it produces only marginally worse decision quality than the state-of-the-art SPO+ approach, but is two orders of magnitude faster. Other reviewers seem to agree with this sentiment, stating that “*compared to other approaches, the proposed method provides the best trade-off between training time and performance*” (reviewer qHeU) and “*The LAVA loss is very fast to compute, differentiable, convex, and grounded in an understanding of polytope geometry, which makes it a very promising addition to the DFL arsenal*” (reviewer vtoW). \n\n \n\n**LAVA for (mixed-)integer linear programs:** For our discussion of this matter we refer to our response to reviewer vtoW. Given that three reviewers posed questions regarding the use of LAVA on (M)ILPs, this point warrants additional attention in the paper, and we will add this discussion to the camera-ready version on acceptance. \n\n \n\n \n\n**Linear predictive models:** We would like to clarify that the method is not limited to use with a linear predictive model. It can also be used with nonlinear models. The reason for the focus on linear models in the experiments is that this is standard practice in work on DFL for linear optimization problems, including in [10, 24-28, 34-36, 38, 39]. The reason for this, in turn, is that (in the complete information setting) DFL is most valuable under model misspecification, which may for instance occur when training interpretable models [11, 21, 38]. \n\n \n\n**Varying degree of degeneracy:** We want to highlight that the three benchmarks included have varying degrees of degeneracy, and are ordered in increasing order of degeneracy (line 286): random LPs are nondegenerate, the multi-dimensional knapsack problem is somewhat degenerate, and the shortest path problem is highly degenerate. While including even more benchmarks with varying degrees of degeneracy would certainly have additional value, this was not possible to achieve within the page limit."}, {"review_id": "zOoY2OZPk2", "reviewer": "Reviewer_qHeU", "summary": "The method tackles improved training times for so-called predict-then-optimise problem, i.e. linear optimisation problems (LP) where the cost-function is unknown but rather needs to be predicted (an which usually require multiple LPs to be solved during training). The key technical contribution lies in a novel loss, called LAVA (loss via adjacent vertex alignment), which essentially favours clearer decision making w.r.t. the predicted cost. To this end, an optimal solution (vector), and its adjacent solution vectors are taken and the cost vector is pushed in such a direction (through back-propagation) that the decision towards the optimal solution vector is as clear as possible (i.e. the cost vector should not \"lean\" towards one of the adjacent solution vectors). The performance of the the proposed loss is evaluated on multiple instances of three classes of LPs.", "questions": "- l. 35: would be great to give examples on how suboptimal predictions can affect decision making\n- l. 58 - 59 repeat of \"set of optimal solution\"\n- l. 146-147: would be great to add that the fact that z is optimal if it has lower objective value than all its neighbours arises from the fact that the feasible region according to Ax = b is a >> convex << region\n- l.203: explicitly mention that that you refer to line 10 in algorithm 1\n- what is the computational complexity of algorithm 1?\n- why is normalised regret used as the metric to evaluate the performance?\n- who would the performance be on constrained shortest path problems (i.e. shortest path problems with additional constraints stating that \"whenever this edge is taken, the other edge also has to be taken\")?", "limitations": "- generally, an \"optimal\" solution z^star might not be available, i.e. for a given dataset it might be unclear what z^star is (since the cost vector c first has to be predicted) and with that restricts the LAVA loss to the special case where this is clear which in turn poses limited applicability of the method\n- for larger optimisation problems (millions of variables) it might be computationally intractable to find adjacent vertices", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths\n- the paper is very well written, the problem is well motivated and key concepts are explained well and backed up by illustrations\n- compared to other approaches, the proposed method provides the best trade-off between training time and performance\n- code is claimed to be released\n- the main technical contribution is mathematically well-grounded \n\n## Weaknesses\n- the contribution of the paper seems limited to me. While the idea of the loss is well-grounded, its applicability to general predict-then-optimise problems seems not necessarily given as the optimal solution vector generally is not available (see also limitations).\n- the evaluation of the loss is limited as only smaller toy examples are used. It would be interesting to see the performance on large scale LPs in which solving the LP during training would be intractable computationally", "was_revised": true, "final_justification": "The paper is technically solid and my main concern (i.e. solution not availble) seems to be out of scope of the problem setting. Therefore, I raised my score to \"accept\".", "rebuttal": "Thank you for your review and for highlighting the clarity of our writing and the favorable trade-off our method achieves between training time and performance. We appreciate your overall positive assessment and recommendation for acceptance. Below, we address the questions posed in the review. \n\n \n\n**Points 1-4:** Thank you for pointing out these typos and suggesting some improvements to the text. We will incorporate these in the paper. \n\n \n\n**Optimal solution might not be available:** We find the described scenario somewhat unclear. Could you please elaborate on the setting you are envisioning. Generally, the optimal solutions are either assumed to be given or are precomputed using the ground-truth cost vectors prior to training, as in the following references: [4, 10, 24-28, 33-36, 38, 39]. \n\n \n\n**Computational complexity of Algorithm 1:** In the base case of nondegenerate vertices, only one iteration through the while-loop at line 8 is performed. The most expensive step in the algorithm is the computation of the directions of movement (line 10), which involves computing $-B^{-1}N$, which is of complexity $O(n^3)$ for B an $n\\times n$ matrix. The remaining steps only involve simple arithmetic of lower complexity, making the entire algorithm $O(n^3)$. The edge case of a degenerate vertex is more complicated. The answer to this question depends on the number of bases that would be visited by applying the TNP rule (line 20) [15, 17]. The TNP rule is a result coming from a series of works performed between the late 1970s and early 1990s (which we discuss in much more detail in Appendix C). Unfortunately, one of the latest works coming from this line of research reads “*note that the worst-case analysis with respect to the number of nodes of T-transition graphs is not yet completely finished*” [17]. We are not aware of any subsequent work that was able to provide such a worst-case analysis. The matter seems to be an open problem. The implication of this is that also the worst-case complexity of Algorithm 1 in the edge case of degenerate vertices is not known. \n\n \n\n**Why the normalised regret is used:** The (normalised) regret is a widely used performance metric in decision-focused learning [10, 24-28, 34, 38, 39]. It expresses the suboptimality of the decisions obtained using the predictions, compared to the actual optimal decisions (which would be obtained if the predictions were perfectly accurate). The normalized variant is often used as a more interpretable metric [10, 26, 34, 38, 39]. It expresses the regret in a relative manner. For example, a normalized regret of 0.1 expresses that the decisions obtained via the predictions achieve an objective value that is 10% worse than the actual optimal decisions. \n\n \n\n**Constrained shortest path problems:** We used the shortest path problem in the presented form because it is commonly used in this form in existing literature [10, 24, 26, 34, 38, 39]. We do not expect that adding additional side constraints would alter the conclusions of the evaluation. \n\n \n\n**Problems with millions of variables:** Problems with millions of variables are presently far out of reach for DFL, and are not in the scope of our work. For reference, existing work on DFL typically focuses on problems with several dozen up to several hundreds of variables. For example, benchmark datasets in the PyEPO library [38] – including shortest path, multidimensional knapsack, and travelling salesperson problems – contain 40, 32, and 190 decision variables, respectively. The Warcraft shortest path problem in [33] involves 144 variables, while the knapsack instance in [28] has 48 variables. Other problems, such as cubic top-k, web advertising, and portfolio optimization from [35] and [36], each involve 50 variables."}]

Author rebuttal:

Meta-review: The paper proposes a new learning method for LPs that does not need an optimizer. This is done through a new loss function and is based on polyhedral geometric aspects.
Reviewers agree on good experiments, good presentation, the method being efficient and the fact that the method is solver-free is commended. On the other hand, restriction to small instances are noted. Following reviewer consensus, the paper merits acceptance at NeurIPS.
Decision: Accept (poster)