Warcraft shortest path | Linear | Continuous |  Customized python implementation of Dijkstra | CNN
Energy-cost aware scheduling | Linear | Discrete | Gurobi | Linear
Knapsack problem | Linear | Discrete | OR-Tools | Linear
Diverse bipartite matching | Linear | Discrete | OR-Tools | Multi-layer NN
Subset selections | Linear | Continuous | Gurobi | Linear

Table 2: Brief overview of the test problems considered for experimental
evaluation. The objective functions are linear for all the optimization
problem.

###  5.1 Problem Descriptions

All the test problems, which are selected for benchmarking, have been
previously used in the DFL literature and their datasets are publicly
available. All these problems are Predict-Then-Optimize problems, meaning they
encompass the two stages—prediction and optimization. Table 2 provides an
overview of the experimental setups associated with each test problem,
including the specification of the CO problem and the type of predictive
model. Next, these test problems are described in detail.

####  5.1.1 Shortest path problem on a $5\times 5$ grid

This experiment is adopted from the work of ? (?). It is a shortest path
problem on a $5\times 5$ grid, with the objective of going from the southwest
corner of the grid to the northeast corner where the edges can go either north
or east. This grid consists of $25$ nodes and $40$ edges.

##### Formulation of the optimization problem.

The shortest path problem on a graph with a set $V$ of vertices and a set $E$
of edges can be formulated as an LP problem in the following form:

$\displaystyle\min_{\mathbf{x}}$ $\displaystyle\;\
\mathbf{c}^{\top}\mathbf{x}$ (42a) s.t. $\displaystyle A\mathbf{x}=\mathbf{b}$
(42b) $\displaystyle\mathbf{x}\geq\mathbf{0}$ (42c)

Where $A\in\mathbb{R}^{|V|\times|E|}$ is the incidence matrix of the graph.
The decision variable $\mathbf{x}\in\mathbb{R}^{|E|}$ is a binary vector whose
entries are 1 only if the corresponding edge is selected for traversal.
$\mathbf{b}\in\mathbb{R}^{|V|}$ is the vector whose entry corresponding to the
source and sink nodes are 1 and $-1$ respectively; all other entries are 0.
The constraint (42b) must be satisfied to ensure the path will go from the
source to the sink node. The objective is to minimize the cost of the path
with respect to the (predicted) cost vector $\mathbf{c}\in\mathbb{R}^{|E|}$.

##### Synthetic data generation process.

In this problem, the prediction task is to predict the cost vector
$\mathbf{c}$ from the feature vector $\mathbf{z}$. The feature and cost
vectors are generated according to the data generation process defined by ?
(?). For the sake of completeness, the data generation process is described
below.111The generator in
https://github.com/paulgrigas/SmartPredictThenOptimize is used to generate the
dataset. Each problem instance has cost vector of dimension $|E|=40$ and
feature vector of dimension $p=5$. The training data consists of
$\\{(\mathbf{z_{i}},\mathbf{c_{i}})\\}_{i=1}^{N}$, which are generated
synthetically. The feature vectors are sampled from a multivariate Gaussian
distribution with zero mean and unit variance, i.e.,
$\mathbf{z_{i}}\sim\mathbf{N}(0,I_{p})$ To generate the cost vector, first a
matrix $B\in\mathbb{R}^{|E|\times p}$ is generated, which represents the true
underlying model. The cost vectors are then generated according to the
following formula:

$c_{ij}=\bigg{[}\bigg{(}\frac{1}{\sqrt{p}}\big{(}B\mathbf{z_{i}}\big{)}+3\bigg{)}^{\text{Deg}}+1\bigg{]}\xi_{i}^{j}$
(43)

where $c_{ij}$ is the $j^{\text{th}}$ component of cost vector
$\mathbf{c_{i}}$. The _Deg_ parameter specifies the extent of model
misspecification, because a linear model is used as a predictive model in the
experiment. The higher the value of _Deg_ , the more the true relation between
the features and objective parameters deviates from a linear one and the
larger the prediction errors will be. Finally, $\xi_{i}^{j}$ is a
multiplicative noise term sampled randomly from the uniform distribution
$[1-\vartheta,1+\vartheta]$. The experimental evaluation involves five values
of the parameter _Deg_ , which are $1,2,4,6\text{ and }8$, and the noise-
halfwidth parameter $\vartheta$ being $0.5$. Furthermore, for each setting, a
different training set of of size 1000 is used. In each case, the final
performance of the model is evaluated on a test set of size $10,000$.

##### Predictive model.

In each setting, the underlying predictive model is a one-layer feedforward
neural network without any hidden layer, i.e., a linear model. The input to
the model is a $p$ dimensional vector, and output is a $|E|$ dimensional
vector. Note that a multi-layer neural network model can be used to improve
the accuracy of the predictive model. The intuition behind using a simple
predictive model is to test the efficacy of the DFL techniques when the
predictions are not 100% accurate. The DFL techniques are trained to minimize
regret, and the prediction-focused model is trained by minimizing the MSE loss
between the true and predicted cost vectors.

####  5.1.2 Portfolio optimization problem

A classic problem that combines prediction and optimization is the Markowitz
portfolio optimization problem, in which asset prices are predicted by a model
based on empirical data, and then subsequently, a risk-constrained
optimization problem is solved for a portfolio which maximizes expected
return. This experiment is also adopted from the work of ? (?).

##### Formulation of the optimization problem.

In portfolio optimization problem, the objective is to choose a portfolio of
assets having highest return subject to a constraint on the total risk of the
portfolio. The problem is formulated in the following form:

$\displaystyle\max_{\mathbf{x}}$
$\displaystyle\;\;\mathbf{c}^{\top}\mathbf{x}$ (44a) s.t.
$\displaystyle\mathbf{x}^{\top}\Sigma\mathbf{x}\leq\gamma$ (44b)
$\displaystyle\mathbf{1}^{\top}\mathbf{x}\leq 1$ (44c)
$\displaystyle\;\;\;\mathbf{x}\geq 0$ (44d)

where $\mathbf{1}$ is the vector of all-ones of same dimension as
$\mathbf{x}$, $\mathbf{c}$ is the vector of asset prices, and $\Sigma$ is a
predetermined matrix of covariances between asset returns. The objective (44a)
is to maximize the portfolio’s total value. Eq. (44b) is a risk constraint,
which bounds the overall variance of the portfolio, and (44c), (44d) model
$\mathbf{x}$ as a vector of proportional allocations among assets.

##### Synthetic data generation process.

Synthetic input-target pairs $(\mathbf{z},\mathbf{c})$ are randomly generated,
according to a random function with a specified degree of nonlinearity
$\text{Deg}\in\mathbb{N}$. The procedure for generating the random data as
follows:

Given a number of assets $d$ and input features of size $p$, input samples
$\mathbf{x_{i}}\in\mathbb{R}^{p}$ are sampled element wise from i.i.d.
standard normal distributions $\mathbf{N}(0,1)$. A random matrix
$B\in\mathbb{R}^{d\times p}$, whose elements $B_{ij}\in\\{0,1\\}$ are drawn
from i.i.d. Bernoulli distributions which take the value $1$ with probability
$0.5$, is created. For a chosen noise magnitude $\vartheta$,
$L\in\mathbb{R}^{n\times 4}$ whose entries are drawn uniformly over
$[-0.0025\vartheta,0.0025\vartheta]$ is generated. Asset returns are
calculated first in terms of their conditional mean $\bar{c}_{ij}$ as

$\bar{c}_{ij}\coloneqq(\frac{0.05}{\sqrt{p}}(B\mathbf{z_{i}})_{j}+(0.1)^{\frac{1}{\text{Deg}}})^{\text{Deg}}$
(45)

Then the observed return vectors $\mathbf{c_{i}}$ are defined as
$c_{ij}\coloneqq\bar{r}_{i}+Lf+0.01\vartheta\xi$, where
$f\sim\mathbf{N}(0,I_{4})$ and noise $\xi\sim\mathbf{N}(0,I_{d})$ This causes
the $c_{ij}$ to obey the covariance matrix $\Sigma\coloneqq
LL^{\top}+(0.01\zeta)^{2}\mathbf{I}$, which is also used to form the
constraint (44b), along with a bound on risk, defined as $\gamma\coloneqq
2.25\;e^{\top}\Sigma e$ where $e$ is the equal-allocation solution (a constant
vector). Four values of the parameter _Deg_ —$1,4,8,16$ have been used in the
experimal evaluation. The value of noise magnitude parameter $\vartheta$ is
set to $1$. It is assumed that the covariance matrix of the asset returns does
not depend on the features. The values of $\Sigma$ and $\gamma$ are constant,
and randomly generated for each setting.

##### Predictive model.

Like the previous experiment, the underlying predictive model is a linear
model, whose input is a feature vector $\mathbf{z}\in\mathbb{R}^{p}$ and
output is the return vector $\mathbf{c}\in\mathbb{R}^{d}$.

####  5.1.3 Warcraft shortest path problem

This experiment was adopted from the work of ? (?). Each instance in this
problem is an image of a terrain map using the Warcraft II tileset (?). Each
image represents a grid of dimension $d\times d$. Each of the $d^{2}$ pixels
has a fixed underlying cost, which is unknown and to be predicted. The
objective is to identify the minimum cost path from the top-left pixel to the
bottom-right pixel. From one pixel, one can go in eight neighboring pixels—up,
down, front, back, as well as four diagonal ones. Hence, it is a shortest path
problem on a graph with $d^{2}$ vertices and $\mathcal{O}(d^{2})$ edges.

##### Formulation of the optimization problem.

Note that this is a node-weighted shortest path problem, where each node
(pixel) in the grid is assigned a cost value; whereas in the previous shortest
path problem, each edge is assigned a cost value. However, this problem can be
easily reduced to the more familiar edge weighted shortest path problem by
‘node splitting’. ‘Node splitting’ splits each node into two separate
nodes—entry and exit nodes and adds an edge, that has a weight equal to the
node weight, from the entry node to the exit node. For each original edge, an
edge, with null weight, from the exit node of the source node to the entry
node of the sink node, is constructed.

##### Predictive model.

The prediction task is to predict the cost associated with each pixel. The
actual cost ranges from 0.8 to 9.2 and is dependent on visible characteristics
of the pixel. For instance, cost changes depending on whether the pixel
represents a water-body, land or wood. To predicts the cost of each node
(pixel), a convolutional neural network (CNN) is employed. The CNN takes the
$d\times d$ image as an input and outputs costs of the $d^{2}$ pixels. The
ResNet18 (?) architecture is slightly modified to form the ML model. The first
five layers of ResNet18 are followed by a max-pooling operation to predict the
underlying cost of each pixel. Furthermore, a Relu activation function (?) is
used to ensure the predicted cost remains positive, thereby avoiding the
existence of negative cycles in the shortest path edge weights.

####  5.1.4 Energy-cost aware scheduling

This experiment setup was adopted from the work of ? (?). This is a resource-
constrained day-ahead job scheduling problem (?) with the objective of
minimizing energy cost. Tasks must be assigned to a given number of machines,
where each task has a duration, an earliest start, a latest end, a resource
requirement and a power usage. Each machine has a resource capacity
constraint. Also, tasks cannot be interrupted once started, nor migrated to
another machine and must be completed before midnight. The scheduling is done
one day in advance. So, the prediction task is to predict the energy prices of
the next day.

##### Formulation of the optimization problem.

The scheduling problem is formulated as an ILP. Let $J$ be the set of tasks to
be scheduled on a set of machines $I$ while maintaining resource requirement
of $W$ resources. The tasks must be scheduled over $T$ number of time slots.
Each task $j$ is specified by its duration $\zeta_{j}$, earliest start time
$\zeta_{j}^{(1)}$, latest end time $\zeta_{j}^{(2)}$, power usage $\phi_{j}$.
Let $\rho_{jw}$ be the resource usage of task $j$ for resource $w$ and
$q_{iw}$ is the capacity of machine $i$ for resource $w$. Let $x_{jit}$ be a
binary variable that takes the value 1 only if task $j$ starts at time $t$ on
machine $i$. The objective of minimizing energy cost while satisfying the
required constraints can be expressed by the following ILP:

$\displaystyle\min_{x_{jit}}\sum_{j\in J}\sum_{i\in I}\sum_{t\in T}$
$\displaystyle x_{jit}\Big{(}\sum_{t\leq
t\prime<t+\zeta_{j}}\phi_{j}c_{t\prime}\Big{)}$ (46a)
$\displaystyle\texttt{s.t.}\;\;\;\sum_{i\in I}\sum_{t\in T}x_{jit}$
$\displaystyle=1\ ,\forall_{j\in J}$ (46b) $\displaystyle x_{jit}$
$\displaystyle=0\ \ \forall_{j\in J}\forall_{i\in
I}\forall_{t<\zeta_{j}^{(1)}}$ (46c) $\displaystyle x_{jit}$ $\displaystyle=0\
\ \forall_{j\in J}\forall_{i\in I}\forall_{t+\zeta_{j}>\zeta_{j}^{(2)}}$ (46d)
$\displaystyle\sum_{j\in J}\sum_{t-\zeta_{j}<t^{\prime}\leq
t}x_{jit\prime}\rho_{jw}$ $\displaystyle\leq q_{iw},\forall_{i\in
I}\forall_{w\in W}\forall_{t\in T}$ (46e) $\displaystyle x_{jit}\in\\{0,1\\}$
$\displaystyle\forall_{j\in J}\forall_{i\in I}\forall_{t\in T}$ (46f)

The (46b) constraint ensures each task is scheduled once and only once. The
constraints in (46c) and (46d) ensure that the task scheduling abides by
earliest start time and latest end time constraints. (46e) imposes the
constraints of resource requirement.

##### Data description.

The prediction task is to predict the energy prices one day in advance. The
energy price dataset comes from the Irish Single Electricity Market Operator
(SEMO) (?). This dataset consists of historical energy price data at 30-minute
intervals starting from midnight on the 1st of November, 2011 until the 31st
of December, 2013. In this setup, each day forms an optimization instance,
which comprises of $48$ time slots, corresponding to $48$ half-hour slots.
Each half-hour instance of the data has calendar attributes, day-ahead
estimates of weather characteristics, SEMO day-ahead forecasted energy-load,
wind-energy production and prices, actual wind-speed, temperature and $CO_{2}$
intensity, which are used as features. So, the dimension of feature vector is
8. Note that, in this dataset, each $c_{t}$ in the cost vector is associated
with an eight dimensional feature vector, i.e., $\mathbf{c}\in\mathbb{R}^{48}$
and $\mathbf{z}\in\mathbb{R}^{48\times 8}$.

##### Predictive model.

As energy prices of each half-hour slot is associated with $8$ features, the
input to the predictive model is a feature vector of dimension $8$ and output
is a scalar. In this case also, the predictive model is a linear model, i.e.,
a feed forward neural network without any hidden layer.

####  5.1.5 Knapsack problem

This problem setup was also adopted from the work of ? (?). The objective of
the knapsack problem is to choose a maximal value subset from a given set of
items, subject to a capacity constraint. In this case, the weights of all
items and the knapsack capacity are known. What is unknown are the values of
each item. Hence, the prediction task is to predict the value of each item.

##### Formulation of the optimization problem.

The formulation of the knapsack optimization problem with unit weights has
already been provided in Eq. (4). However, in general the weights of all items
are not equal. So, a general knapsack optimization problem can be formulated
as follows:

$\displaystyle\max_{\mathbf{x}}\;\;$
$\displaystyle\mathbf{c}^{\top}\mathbf{x}$ (47a) s.t.
$\displaystyle\mathbf{w}^{\top}\mathbf{x}\leq\text{Capacity}$ (47b)
$\displaystyle\mathbf{x}\in\\{0,1\\}$ (47c)

where $\mathbf{w}$, $\mathbf{c}$ are the vector of weights and values
respectively.

##### Data description.

For this problem again, the dataset is adapted from the Irish Single
Electricity Market Operator (SEMO) (?). In this setup, each day forms an
optimization instance and each half-hour corresponds to a knapsack item. So
the cost vector $\mathbf{c}$ and the weights $\mathbf{w}$ are of length 48,
corresponding to 48 half-hours. The motivation can be framed as identifying
half-hour slots that yield maximum revenue while adhering to the constraint of
booking each slot. Similar to the energy scheduling problem, each item of the
cost vector is associated with a feature vector of dimension 8. The weight
vector is fixed. The weights are generated synthetically as done by ? (?). The
data generation is as follows. First a weight $w_{i}$ is assigned to each of
the 48 half-hour slots, by sampling from the set $\\{3,5,7\\}$. In order to
introduce correlation between the item weights and the item values, the energy
price vector is multiplied with the weight vector and then a randomness is
incorporated by adding Gaussian noise $\xi\sim\mathbf{N}(0,25)$, which
produces the final item values $c_{i}$. The motivation behind introducing
correlation between the item weights and the item values stems from the fact
that solving a knapsack problem with correlated item weights and values is
considered to be hard to solve (?). The sum of the weights of each instance is
$240$. 60, 120, and 180 are the three values of capacity with which the
experiments are performed.

##### Predictive model.

The predictive model is same as the previous problem, i.e., a feed forward
neural network without any hidden layer.

####  5.1.6 Diverse bipartite matching

This experimental setup is adopted from ? (?). In this problem, two disjoint
sets of nodes are provided and the objective is to match between the nodes of
the two sets. The graph topologies are taken from the CORA citation network
(?), where a node represent an published article and an edge represent a
citation. So the goal of the matching problem is to identify the citations
between the two sets of articles. Furthermore, the matching must obey
diversity constraints, as described later.

##### Optimization problem formulation.

Let $S_{1}$ and $S_{2}$ denote the two sets. The matching must satisfy the
following diversity constraints: a minimum $\rho_{1}\%$ and $\rho_{2}\%$ of
the suggested pairings should belong to same and distinct fields of study
respectively. In this matching problem, each edge does not have an associated
cost in the true sense. The DFL approaches consider the likelihood of the
existence of each edge as the edge weights and then determine which edges
should be present while ensuring all the constraints are satisfied. Let
$c_{ij}$ be the likelihood of an edge existing between article $i$ and $j$,
$\forall i\in S_{1},j\in S_{2}$. With this likelihood value, the matching can
be performed by solving the following ILP, which ensures the diversity
constraints:

$\displaystyle\max_{\mathbf{x}}$ $\displaystyle\sum_{i,j}c_{ij}x_{ij}$ (48a)
s.t. $\displaystyle\sum_{j}x_{ij}\leq 1$ $\displaystyle\forall i\in S_{1}$
(48b) $\displaystyle\sum_{i}x_{ij}\leq 1$ $\displaystyle\forall j\in S_{2}$
(48c) $\displaystyle\sum_{i,j}\phi_{i,j}x_{ij}\geq\rho_{1}\sum_{i,j}x_{ij}$
(48d) $\displaystyle\sum_{i,j}(1-\phi_{ij})x_{ij}\geq\rho_{2}\sum_{i,j}x_{ij}$
(48e) $\displaystyle x_{ij}\in\\{0,1\\}$ $\displaystyle\forall i\in S_{1},j\in
S_{2}$ (48f)

where $\phi_{ij}$ is an indicator, which takes the value $1$ only if article
$i$ and $j$ are of same field, and $0$ if they belong to two different fields.

##### Data description.

The network is divided into 27 disjoint topologies, each of which forms a
distinct optimization problem instance containing 100 nodes. In each instance,
the $100$ nodes are split into two sets of 50 nodes $S_{1}$ and $S_{2}$; so
each instance forms a bipartite matching problem between two sets of
cardinality 50. Each publication (node) has 1433 bag-of-words features. The
feature of an edge is formed by concatenating features of the two
corresponding nodes. The prediction task is to estimate $c_{ij}$ values. In
this problem, each individual $c_{ij}$ is associated with a feature vector of
length 2866.

##### Predictive model.

Although the DFL paradigm considers the likelihood of the existence of each
edge as the edge weights, in the prediction-focused approach the model is
trained by directly predicting the presence or absence of each edge. The
predictive model is a neural network model. The input to the neural network is
a 2866 dimensional vector and final output is a scalar between 0 and 1. The
neural network has one hidden layer and uses a sigmoid activation function on
the output.

####  5.1.7 Subset selections

This experiment is a structured prediction task, in which the object is to
learn a mapping from feature vectors to binary vectors which represent subset
selections. Unlike the other experiments above, the ground-truth data take the
form of optimal solutions to an optimization problem, rather than its
corresponding problem parameters. Thus, the regret loss is not suitable for
training a prediction model. Instead, a task loss based on the error of the
predicted solutions with respect to ground-truth solutions is used in this
experiment.

##### Optimization problem formulation.

For any $\mathbf{c}\in\mathbb{R}^{n}$, the objective of the optimization
problem is to output a binary vector in $\mathbb{R}^{n}$, where the non-zero
values correspond to the top-$k$ values of $\mathbf{c}$. This can be
formulated as an LP problem in the following form:

$\displaystyle\operatorname*{argmax}_{\mathbf{x}}$
$\displaystyle\;\;\mathbf{c}^{\top}\mathbf{x}$ (49a) s.t. $\displaystyle
1^{\top}\mathbf{x}=k$ (49b) $\displaystyle 0\leq\mathbf{x}\leq 1$ (49c)

As a totally unimodular linear program with integral parameters, this problem
has (binary) integer optimal solutions. This mapping is known for its ability
to represent subset selections in structured prediction, and is useful for
multilabel classification (?) .

##### Data Description.

Let $\mathbf{U}(0,1)$ be a uniform random distribution; then a collection of
feature vectors $\mathbf{z}$ are generated by
$\mathbf{z}\sim\mathbf{U}(0,1)^{n}$. For each $\mathbf{z}$, its corresponding
target data is a binary vector containing unit values corresponding to the
top-$k$ values of $\mathbf{z}$, and zero values elsewhere. Three datasets are
generated, each of $1000$ training samples, in which the selection problem
takes size $n=25$, $n=50$, and $n=100$ respectively. The subset size $k$ is
chosen to be one fifth of $n$, in each case.

##### Predictive model.

Like the previous problem, the predictive model here also is a linear model,
i.e., a feed forward neural network without any hidden layer. In this problem,
the task loss to train the predicative model is the negated inner product
between true selection $\mathbf{x}$ and prescribed selection
$\mathbf{\hat{x}}$, i.e.,
$\mathcal{L}(\mathbf{\hat{x}},\mathbf{x})=\mathbf{\hat{x}}^{\top}\mathbf{x}$,
which is minimized when $\mathbf{\hat{x}}=\mathbf{x}$. Since the model is not
regret-based, and does not assume access to the ground-truth parameters
$\mathbf{c}$, techniques which rely on such assumptions are not tested on this
problem.

Hyperparameter |  Techniques Utilizing the Hyperparameter | Range
---|---|---
learning rate | All | $\\{5\times 10^{-4},1\times 10^{-3},5\times 10^{-3},0.01,0.05,0.1,0.5,1.0\\}$
$\lambda$ | I-MLE, DBB | $\\{0.1,1,10,100\\}$
$\epsilon$ | I-MLE, FY | $\\{0.05,0.1,0.5,1,2,5\\}$
$\kappa$ | I-MLE | $\\{5,10,50\\}$
$\tau$ | Listwise | $\\{0.05,0.1,0.5,1,2,5\\}$
$\Theta$ | Pairwise | $\\{0.01,0.05,0.1,1.,10.,50.\\}$
$\mu$ | QPTL, HSD | $\\{0.01,0.1,1.,10.,\\}$
damping | HSD | $\\{1\times 10^{-4},0.01,0.1,1.,10\\}$

Table 3: The range of hyperparameters for hyperparameter tuning by grid
search.

###  5.2 Experimental Results and Analysis

In this subsection, results of comparative evaluations of some of the
techniques introduced in Section 3 on the datasets mentioned in Section 5 are
presented. The following techniques are considered for evaluations: 1\.
Prediction-focused (PF) approach, 2\. Smart “Predict, Then Optimize” (32)
[SPO], 3\. Differentiation of blackbox combinatorial solvers (24) [DBB], 4\.
Implicit maximum likelihood estimation (30) [I-MLE], 5\. Fenchel-Young loss
(29) [FY], 6\. Differentiation of homogeneous self-dual embedding (20) [HSD],
7\. Quadratic programming task loss (19) [QPTL], 8\. Listwise LTR loss (40)
[Listwise], 9\. Pairwise LTR loss (38) [Pairwise], 10\. Pairwise difference
LTR loss (39) [Pairwise(diff)], 11\. Maximum a posteriori contrastive loss
(37) [MAP]. The reason behind including prediction-focused approach is that it
is considered as a benchmark. Note that among these techniques, Listwise,
Pairwise, Pairwise(diff), and MAP make use of a solution cache. The solution
cache is implemented using the procedure proposed by ? (?). In this approach,
the solution cache is initialized by caching all the solutions in the training
data and the cache is later expanded by employing a $p_{solve}$ parameter
value greater than zero. As in (?, ?) it is reported that $p_{solve}=5\%$ is
adequate for most applications, the value of $p_{solve}$ is set to $5\%$.
Next, the procedure systematically followed for the empirical evaluations is
explained.

##### Experimental setup and procedures.

The performance of a technique is sensitive to the choice of the technique
specific hyperparameters as well as some other fundamental hyperparameters,
common in any neural network training such as learning rate. These are called
hyperparameters because they cannot be estimated by training the model, rather
they must be selected before training begins. Tuning hyperparameters is the
process of identifying the set of hyperparameter values that are expected to
produce the best model outcome. In the experimental evaluations,
hyperparameter tuning is performed via grid search. In the grid search, each
of the hyperparameters is tried for a set of values. The set of values to be
tested for each hyperparameter is predetermined. Grid search suffers from the
curse of dimensionality in the hyperparameter space, as the number of
combinations grows exponentially with the number of hyperparameters. However,
it is possible to train the different models for different combinations of
hyperparameters in parallel as the combinations are independent.

The hyperparameter of each model for each experiment is selected based on
performance on the validation dataset. For each hyperparameter a range of
values as defined in Table 3 is considered. The hyperparameter combination
which produces the lowest average regret on the validation dataset is
considered to be the ‘optimal’ one. For both validation and testing, $10$
trials are run where in every trial the network weights are initialized with a
different seed. To be specific, values of seed from 0 to 9 have been
considered. Each model for each setup is trained using pytorch (?) and
pytorch-lightning (?) with the adam optimizer (?) and ‘reduceLROnPlateau’(?)
learning rate scheduler. As mentioned before, the learning rate of adam
optimizer is treated as a hyperparameter. For QPTL, the QP problems are solved
using cvxpylayers (?). For other techniques, which treat the CO solver as a
blackbox solver, gurobi (?) or ortools (?) is used as the solver.

##### Evaluation metric.

After selecting the ‘optimal’ hyperparameter combination for each test
problem, 10 trials of all the techniques with the ‘optimal’ hyperparameter
combination are run on test dataset. Unless otherwise mentioned the
comparative evaluation is made based on relative regret on the test dataset.
The relative regret is defined as follows:

$\frac{1}{N_{test}}\sum_{i=1}^{N_{test}}\frac{\mathbf{c_{i}}^{\top}(\mathbf{x}^{\star}(\mathbf{\hat{c_{i}}})-\mathbf{x}^{\star}(\mathbf{c_{i}}))}{\mathbf{c_{i}}^{\top}\mathbf{x}^{\star}(\mathbf{c_{i}})}.$
(50)

In practice, $\mathbf{c}$ (or $\mathbf{\hat{c}}$) can have non-unique optimal
solutions. However, note that if all the entries in $\mathbf{c}$ are
continuous, it is very unlikely that $\mathbf{c}$ will have non-unique
solutions. For instance, in the case of an LP, the only circumstance in which
the LP can have multiple solutions is when $\mathbf{c}$ is parallel to one of
the faces of the LP polyhedron. Nevertheless, if the cost vector is predicted
by an ML model, a pathological case might occur, especially at the beginning
of model training, when all the cost parameters are zero. This results in all
feasible solutions being optimal with zero cost. However, to avoid this
complexity in the experiments, it is assumed that the solution
$\mathbf{x}^{\star}(\mathbf{\hat{c}})$ is obtained by calling a CO solver as
an oracle and that if there exist non-unique solutions, the oracle returns a
single optimal solution by breaking ties in a pre-specified manner. This is
true if a commercial solver such as Gurobi is used to solve the CO problem.

####  5.2.1 Comparative Evaluations

(a) $\text{Deg}=1$

(b) $\text{Deg}=8$

Figure 5: Comparative evaluations on the synthetic shortest path problem with
noise-halfwidth parameter $\vartheta$ = 0.5. The boxplots show the
distributions of relative regrets.

Next, the performances of the 11 DFL techniques across the 7 problems are
presented for comparative evaluation.

##### Shortest path problem on a $5\times 5$ grid.

The comparative evaluation for the synthetic shortest path problem is shown in
Figure 5 with the aid of box plots. To conserve space, boxplots for two values
of Deg are shown in Figure 5. The boxplots for all the five degrees are shown
in Figure A1 in the Appendix. In Figure 5, the value of $\vartheta$, the
noise-halfwidth parameter is 0.5 for all the experiments and the training set
for each Deg contains 1000 instances. The predictive model is a simple linear
model implemented as a neural network model with no hidden layers.

For Deg 1, the linear predictive model perfectly captures the data generation
process. Consequently, the PF approach is very accurate and it results in the
lowest regret. SPO has slightly higher regret than the PF approach. All the
other DFL techniques have considerably higher regrets compared to PF. In
contrast, the relative regret worsens for the PF approach, as the value of Deg
parameter is increased. For Deg 8, PF is not the best as the predictive model
is misspecified. In this case, FY has the lowest regret; while DFL techniques,
other than Pairwise(diff) results in lower regret than the PF approach. For
Deg 6, the best one FY, although its test regret is not very different from
SPO, I-MLE and QPTL. For Deg 4, I-MLE has the lowest regret, closely followed
by FY and SPO. For Deg 2, both PF and SPO have lowest regret.

Among the DFL techniques, HSD exhibits higher regret and higher variances than
the other DFL approaches. It performs better than the PF approach only for Deg
6 and 8.

(a) $\text{Deg}=1$

(b) $\text{Deg}=16$

Figure 6: Comparative evaluations on the synthetic portfolio optimization
problem with noise magnitude $\vartheta=1$. The boxplots show the
distributions of absolute regrets.

##### Portfolio optimization problem.

Note that this is an optimization problem with continuous decision variables
having quadratic constraints and a linear objective function. Hence, the HSD
approach is not applicable for this problem, as it cannot handle non-linear
constraints. However, as cvxpylayers is used to implement QPTL, it can be
applied in this problem. The boxplots of test regrets for noise magnitude
parameter $\vartheta$ being 1 are shown in Figure 6.

In this problem, in some problem instances, all the return values are
negative, which makes a portfolio with zero return to be the optimal
portfolio. In such cases, relative regret turns infinite as the denominator is
zero in Eq. (50). Hence, for this problem set, the absolute regret instead of
relative regret is reported in Figure 6. The boxplots for Deg values of 1 and
16 are shown in The boxplots for all the four degrees are shown in Figure A2
in the Appendix.

Apparently, the PF approach performs very well in this problem; but SPO
manages to outperform PF slightly in all cases except for Deg 1. It is evident
in Figure 6 that DBB, I-MLE, FY and QPTL perform miserably as they generate
regret even higher than the PF approach. All these techniques were proposed
considering problems with linear constraints. Hence concerns arise that these
techniques might not be suitable in the presence of quadratic constraints. On
the other hand, LTR losses—Pairwise and Pairwise(diff) and contrastive loss
function, MAP, perform even better than SPO for Deg 16. The Listwise LTR loss
exhibits high variance for Deg 1 and for Deg values of 4 and 8. For Deg 16, it
generates average test regret lower than SPO. In general, Figure 6 reveals
DBB, I-MLE, FY and QPTL perform poorly in this problem, whereas, SPO, MAP
Pairwise and Pairwise(diff) seem to be the best performing DFL techniques for
this problem.

(a) $\text{Image Size }12\times 12$

(b) $\text{Image Size }30\times 30$

Figure 7: Comparative evaluations on the Warcraft shortest path problem
instances. The boxplots show the distributions of relative regrets.

##### Warcraft shortest path problem.

Recall that this a shortest path problem in an image with dimension $d\times
d$. The optimization problem can be efficiently solved using Dijkstra’s
algorithm (?), as underlying costs of all the pixel values are non-negative.
Hence the shortest path problem is solved using Dijkstra’s algorithm for the
techniques which view the CO solver as a blackbox oracle. However, HSD and
QPTL require the problem to be formulated as an LP and require a primal-dual
solver. Note that in this experiment, the predictive ML model is a CNN, which
predicts the cost of each pixel. In this case, training the ML model is
challenging due to the large number of parameters. Hence, combining this ML
model with computation-intensive modules such as a primal-dual solver poses
significant challenges. We could not run the experiments with HSD and QPTL
because of this computational burden.

The dataset contains four values of $d$: $12,18,24,30$. Clearly, as the value
of $d$ increases, the number of parameters of the CO problem increases. The
boxplots of comparative evaluations are summarized in Figure 7. The boxplots
of the other two values of $d$ can be found in Figure A3 in the Appendix.
First, note that the PF approach, which is trained by minimizing MSE loss
between the predicted cost and the true cost, performs significantly worse
than the DFL techniques. In fact, the performance of the PF approach
deteriorates as the image size increases. As the size of the image increases,
the same level of prediction error induces greater inaccuracies in the
solution. This is because an increase in the area of the image involves
dealing with a greater number of decision variables in the CO problem. When
the level of prediction error remains constant, the probability of the error
in prediction changing at least one of the decision variables also increases.
Consequently, there is a higher likelihood of error in the final solution. As
the regret of the PF approach is significantly higher, note that the scale of
the y-axis is changed to fit it into the plot.

Among the DFL techniques, Listwise performs best for sizes 12, 18, and 30 and
SPO performs best for size 30. In fact, for sizes 12, 18, and 24, there are
not many variations between SPO, Listwise, and MAP. After them, the next three
best-performing techniques are Pairwise (diff), I-MLE and DBB. However, for
size 30, DBB comes third after Listwise and MAP, followed by Pairwise (diff),
SPO, and I-MLE in that order. FY and Pairwise perform slightly worse than the
other DFL techniques. In general, this set of experiments shows the advantage
of the DFL approaches as all of them outperform the PF approach.

(a) Instance 1 Figure 8: Comparative evaluations on the energy-cost aware
scheduling problem instances. This boxplot shows the distributions of relative
regrets.

##### Energy-cost aware scheduling.

There are three instances of this scheduling problem. All the instances have 3
machines. The first, second, and third instances contain 10, 15, and 20 tasks,
respectively. In this problem, the underlying ML model is a simple linear
model implemented as a neural network model with no hidden layers. The boxplot
of comparative evaluations for the first instance is presented in Figure 8.
The boxplots of the other instances can be found in Figure A4 in the Appendix.

Note that the scheduling problem is an ILP problem. For HSD and QPTL, the LPs
obtained by relaxing the integrality constraints have been considered. QPTL
and HSD also perform poorly in all three instances. Listwise and Pairwise LTR
losses also result to higher regret than the PF approach. On the other hand,
FY, SPO, I-MLE, Pairwise(diff) and MAP come out as the best performing ones
closely followed by DBB.

In general, across the three problem instances, it is possible to identify
some common patterns. The first one is relaxing the integrality constraints
fails to capture the essence of the combinatorial nature of the LP.
Consequently, HSD and QPTL perform poorly. Secondly, Listwise and Pairwise
ranking performances are significantly worse than the PF approaches. The
learning curve suggests (refer to Appendix B), these methods fail to converge
in these problem instances, although in some epochs, they are able to perform
significantly better than the PF approach, their performances never plateau.
Lastly, SPO, MAP, FY, and I-MLE perform consistently better than the rest.

(a) Capacity= 60 Figure 9: Comparative evaluations on the knapsack problem
instances. This boxplot shows the distributions of relative regrets

##### Knapsack problem.

Three instantiations of the knapsack problem are considered for the
experiment—each instantiation with a different capacity. The three capacity
values are—60, 120 and 180. The boxplot corresponding to capacity value 60 is
presented in Figure 9. The boxplots of the other two capacities can be found
in Figure A5 in the Appendix. With a capacity of 60, QPTL performs the best,
whereas DBB, and I-MLE, HSD, SPO, and MAP also results in lower regret than
the PF approach. With capacity values of 120 and 180, DBB has the lowest
regret. Again I-MLE and SPO, HSD and QPTL result in lower regret than PF.
However, MAP, LTR losses, and FY perform poorly especially for high capacity
values.

##### Diverse bipartite matching.

Three instantiations of the diverse bipartite matching problem are formed by
changing the values of $\rho_{1}$ and $\rho_{2}$. The values of
$(\rho_{1},\rho_{2})$ for the three instantiations are $(10\%,10\%)$,
$(25\%,25\%)$, $(50\%,50\%)$ respectively. As mentioned before, in this
problem, each edge is not associated with an edge weight in the true sense.
Hence, the PF approach is trained by directly learning to predict whether an
edge exists. So the loss used for supervised learning for the PF approach is
BCE loss. The DFL approaches consider the predicted probability of each edge
as the edge weight and then aim to minimize regret.

The boxplot of comparative evaluations for $(\rho_{1},\rho_{2})$ being
$(50\%,50\%)$, is presented in Figure 10. The boxplots of the other two
instances can be found in Figure A6 in the Appendix. Firstly note that
relative regrets of all the techniques are very high (higher than 80%) for all
three instances. With $\rho_{1}$ and $\rho_{2}$ being $10\%$, I-MLE performs
considerably better than all the other DFL techniques. When $\rho_{1}$ and
$\rho_{2}$ take the value of $25\%$, QPTL, I-MLE and HSD are the top there
techniques, with significantly lower regret than the rest. In the first two
instances, other than I-MLE and QPTL, other DFL techniques do not
significantly better than the PF approach. DFL techniques such as SPO, FY,
Listwise, Pairwise and MAP perform considerably better than the PF approach
only in the third instances.

(a) $\rho_{1}=\rho_{2}=50\%$ Figure 10: Comparative evaluations on the diverse
bipartite matching problem instances. This boxplot shows the distributions of
relative regrets.

##### Learning subset selections.

Subset selection problems of three dimensions: $n=25$, $n=50$, and $n=100$ are
considered for evaluation. In each case, the subset size $k$ is chosen to be
$\frac{n}{5}$. The error of any predicted subset $\hat{x}$, with respect to
ground truth $x$, is considered to be the fraction of items which are selected
in $x$ but not in $\hat{x}$. Such occurrences are referred to as mismatches.

Figure 11 shows the average mismatch rates over the size $n=25$ instances that
were achieved by each DFL technique listed in Table 1, excluding those which
assume ground-truth data in the form of problem parameters. Here, the ground-
truth data are optimal solutions of (49) representing subset selections. For
each assessed technique, a distribution of results is shown, corresponding to
$10$ different randomly generated training datsets. Figure A7 shows similar
results over the larger problem instances.

Note that it is suggested in (?) that the entropy function
$H(\mathbf{x})=\sum_{i}x_{i}\log x_{i}$ is particularly well-suited as a
regularizer of the objective in (49), for the purpose of multilabel
classification, which is identical to the task in terms of its optimization
component and the form of its target data. Hence a Cvxpylayers implementation
of this model is included and referred to as ENT.

Figure A7 shows that most of the assessed techniques perform similarly, with
DBB performing worst regardless of the problem’s dimension. HSD is most
sensitive with respect to the randomly generated training set; the rest show
consistent performance across datasets. QPTL and IMLE each show a marginal
advantage over the other techniques, but DPO and ENT are also competitive.
Across all techniques, variation in performance over the randomly generated
datasets tends to diminish as problem size increases.

Figure 11: Comparative evaluations on the subset selection problem instances
of Size $25$. This boxplot shows the distributions of mismatch rates.

####  5.2.2 Comparison on Runtime

While training the ML model to minimize the task loss is the primary challenge
of DFL, the computational cost associated with repeatedly solving CO problems
gives rise to the second challenge. DFL techniques with low computational cost
are essential for scalability for implementing DFL for real-world large-scale
Predict-Then-Optimize problems. The importance of scalability and low
computational cost becomes significant while dealing with large-scale CO
problems, especially NP-hard combinatorial optimization problems. Note that
while the shortest path and the knapsack problems are relatively easy to
solve; the energy-cost aware scheduling problem is much more challenging. That
is why the scheduling problem is considered to compare the computational costs
of the DFL techniques.

(a) Instance 2

(b) Instance 3

Figure 12: Comparative evaluations of per epoch training time of different DFL
techniques on the energy-cost aware scheduling problem.

The median training time of an epoch during training of each technique for two
instances of the scheduling problem is shown Figure 12. Recall that the first,
second and third instances contain 10, 15 and 20 tasks respectively. So, the
first one is the easiest of the three and the third one is the hardest one.
The complexity of the scheduling problem is evident from the fact that a
single instance of the knapsack problem takes $0.001$ seconds to solve, while
solving the most difficult instance of the scheduling problem takes $0.1$
seconds, both using Gurobi MIP solver. The readers are cautioned against
placing excessive emphasis on the absolute values of training times in Figure
12, as they are subject to system overhead. However, some general conclusions
can be drawn from the relative ordering of the training times. The training
time of the PF approach is the lowest, as it does not require solving the CO
problem for training. Training times of SPO, DBB, I-MLE and FY are almost 100
times higher than the PF approach. Although QPTL and HSD consider the relaxed
LP problem, it is not always the case that they have lower training times.
Recall that QPTL and HSD solve and differentiate the optimization problem
using a primal-dual solver, which involves matrix factorization. On the other
hand, SPO, DBB, I-MLE and FY can leverage faster commercial CO solvers, as
they only require the optimal solution. However, for Instance 3, it seems
solving the ILP problem by calling a CO solver, is more computationally
expensive than solving and differentiating the underlying QP problem using
cvxpylayers.

On the other hand, Listwise, Pairwise, Pairwise(diff) and MAP, all of which
are run with $p_{solve}=5\%$, exhibit significantly lower training time than
the other DFL techniques. From this perspective, these techniques lie between
PF and DFL approaches, balancing the trade-off between scalability and
quality. The same conclusion generally holds true for other experiments as
well. However, for relatively easier CO problems, the system overhead time may
dominate over training time, which might disrupt the ordering of the training
time.

####  5.2.3 Discussion

The experimental evaluations reveal that no single DFL technique performs the
best across all experiments. Some techniques work well on particular test
problems, while others work better on other test problems. Nevertheless, the
following interesting characteristics can be observed in the experimental
evaluations:

  1. (i)

The performance of SPO is consistently robust across the test problems, even
though it may not outperform other techniques in every experiment.

  2. (ii)

I-MLE, FY, DBB and QPTL perform worse than the PF approach for the portfolio
optimization problem, where a quadratic constraint is present.

  3. (iii)

QPTL demonstrates robust performance when the relaxed LP is a good
approximation of the ILP. QPTL outperforms other techniques by a substantial
margin in the bipartite matching problem. However, QPTL performs poorly
compared to others in the scheduling problem, which is an ILP. In this case,
the poor performance may be attributed to the fact that QPTL considers a
relaxation of the ILP. In this problem, the LP solution might differ
significantly from the true ILP solution. This is not the case for the
knapsack problem, because the solution of the relaxed LP does not deviate
significantly from the ILP solution for the knapsack problem.

  4. (iv)

MAP also demonstrates consistent performance across most test problems; it
exhibits higher regret specifically in the knapsack problem for Capacity=180
and in the bipartite matching problem when $\rho_{1}$ and $\rho_{2}$ are
$25\%$. It results in low regret in the portfolio optimization problem; where
some DFL techniques perform poorly.

  5. (v)

Among the LTR losses, Listwise and Pairwise often exhibit high variances,
especially in the scheduling and the knapsack problems. The performance of
Pairwise(diff) stands out among the LTR losses due to its lower variance. Its
performance is comparable to or slightly worse than MAP for most problems
other than the synthetic shortest path problem with high values of Deg, i.e.,
when the underlying predictive model is completely misspecified.

  6. (vi)

Due to the limitation of computational resources, it was not possible to run
QPTL and HSD on the Warcraft shortest path problem. This highlights the
advantage of DFL techniques which can make use of any blackbox combinatorial
solver (Dijkstra’s shortest path solver for instance) to solve the CO problem.

  7. (vii)

Continuing on this topic of computational cost, MAP and the LTR losses are
considerably faster and less computationally intensive when they are run with
low values of $p_{solve}$. For large-scale real-world CO problems, the
repeated solving of which might be prohibitive, MAP could be used to implement
DFL, as MAP tends to have regret as low as SPO in most test problems.

##  6 Future Research Directions

While there is increasing interest in decision-focused learning research, more
work is required to enable its application in a wider range of real-world
problems. This section aims to summarize some challenges in DFL research that
remain open.

##### Generalizing DFL across related tasks.

Existing DFL methods typically tailor the machine learning model to a specific
combinatorial optimization task. However, in many real-world applications, the
CO problem can vary across different instances. For instance, in the MIT-
Amazon Last Mile Routing Challenge (?), a Traveling Salesman Problem is solved
daily to determine the routing of last-mile package delivery. The nodes in
these Traveling Salesman Problem instances change daily as delivery locations
vary. A promising research direction would be to investigate the performance
of a model trained to minimize regret on one CO problem instance when
evaluated on similar but different CO problem instances. Other research
directions could involve the integration of multi-task learning with decision
focused learning. This exploration could lead to the development of more
versatile and robust DFL models capable of generalizing across a range of
related tasks, thereby greatly enhancing their practical applicability.

##### Non-linear objective function.

Most DFL research has focused on optimization problems with linear objective
functions, as those emphasized in the experimental evaluations in this
article. However, many real-world combinatorial optimization problems feature
non-linear objective functions and discrete decision variables. For instance,
optimally locating substations in an electrical network to minimize
distribution costs is a problem often formulated as non-linear programming
(?). Similarly, minimizing the makespan in flowshop scheduling is another
classic operations research problem that lacks a linear objective function.
While cvxpylayers (?) allows for differentiation through convex optimization
problems with non-linear objective functions, most techniques discussed in
this paper are not equipped to handle such scenarios. Future research should
focus on developing and evaluating DFL techniques that can effectively address
combinatorial optimization problems with non-linear objective functions. This
advancement would significantly expand the applicability and impact of DFL in
solving complex real-world problems.

##### Robust risk-sensitive DFL.

Most DFL techniques formulate empirical risk minimization problems to minimize
expected regret. However, in many real-world applications, particularly those
that are risk-sensitive, safety concerns renders the focus from expected
regret less relevant. A more viable alternative in these cases would be to
focus on regret in distributional worst-case scenarios. This necessitates
minimizing risk-sensitive losses, such as value-at-risk or min-max regret. To
address these cases, future research could draw inspiration from robust
optimization (?), a well-established field within operations research that
addresses worst-case regret within an uncertainty set. The prediction-focused
approach could be adapted to design an “estimate-then-optimize” strategy (?),
incorporating risk-sensitive loss functions by creating a weight-based
empirical distribution to represent the uncertainty set (?). However, the DFL
methodologies reviewed in this article are not designed to minimize risk-
sensitive losses. While a recent work (?) proposes a data-driven approach for
constructing uncertainty sets using contextual features, the literature on
robust DFL remains sparse, offering ample opportunities for future research.

##### Decision-focused learning by zeroth-order gradient.

An alternative approach to gradient estimation is to adopt zeroth-order
gradient estimation, particularly through the score function gradient
estimation technique (?). This method has been recently adapted to DFL, where
it assumes that the predicted parameter adheres to a specific distribution,
and the model is trained accordingly to predict this distribution’s parameters
(?). In principle, this method can also be used to predict parameters in the
constraints of CO problems. However, despite providing an unbiased gradient, a
significant drawback of the score function gradient estimation is its
susceptibility to high variances, which can destabilize the learning process.
Addressing this challenge could lead to substantial improvements. Enhancements
could focus on variance reduction techniques or the development of more robust
estimation algorithms.

##### Bilevel Optimization Techniques for DFL.

As mentioned in Section 2.2, the empirical regret minimization problem can be
cast as a pessimistic bilevel optimization problem. A deeper understanding of
the mathematical foundations behind this learning process can lead to the
development of more effective algorithms for DFL. Recent efforts by ? (?) have
reformulated the problem as a quadratic non-convex optimization problem.
However, the scalability of this approach remains a significant challenge.
This presents a valuable opportunity for the bilevel optimization community to
develop scalable and efficient solutions, advancing the field of DFL and
enhancing its practical applications.

##### Scalable DFL.

While surrogate solvers and solution caching aim to address the scalability
challenges in DFL, the trade-off between quality and scalability of these
methods is not yet understood. In the context of solution caching, there is
ample space for research to investigate the trade-off between the solution
cache size and the resulting solution quality. Determining the optimal cache
size that balances computational efficiency with high-quality solutions could
lead to significant improvements in DFL performance. Additionally, the
effectiveness of using pre-trained surrogate models as proxy CO solvers
remains an open question. Specifically, it is unclear whether these surrogates
can achieve regret levels comparable to those obtained using traditional CO
solvers. Future research should explore the conditions under which surrogate
solvers can approximate the performance of CO solvers, and identify strategies
to enhance their accuracy and reliability. This line of research could reveal
new insights into the design of more scalable DFL systems, which is one of the
most important challenges to broaden their applicability to a wide range of
complex problems.

##### Theoretical guarantees.

While there has been extensive work on providing theoretical guarantees for
the SPO+ loss, not all DFL methods offer theoretical guarantees on minimizing
regret. Empirical results presented in this article suggest that the
performance of some DFL methods may be suboptimal when dealing with
combinatorial optimization problems that contain non-linear constraints. This
gap underscores the need for further theoretical developments to establish the
reliability and effectiveness of DFL methods across a broader range of
optimization scenarios. Ensuring robust theoretical guarantees for DFL
methods, particularly in the presence of non-linear constraints, would
significantly enhance their trustworthiness especially important for safety-
critical applications. This involves developing new analytical tools and
techniques to prove the regret-minimizing properties of DFL methods under
various conditions. Moreover, research should also focus on extending existing
theoretical frameworks to encompass a wider array of CO problems.

##### Uncertainty in the constraints.

As reviewed in Section 3.3.3, some recent works have focused on DFL methods
for predicting parameters within the constraints of optimization problems.
However, these methods have not been explored to the same extent as those
predicting objective function parameters, leaving several open research
directions for future investigation. For instance, future studies could extend
the Neural Combinatorial Optimization (?) and NCE (?) approaches by
considering the prediction of parameters within the constraints. A significant
challenge to implement the NCE approach in this setting is determining how to
form the solution cache. Moreover, when predicting parameters in the
constraints, the incorporation of risk-sensitive losses becomes particularly
important. In these scenarios, the prescribed decision might not be feasible
with respect to the true parameters. An intriguing research direction is to
develop methods that recommend solutions feasible under extreme distributional
variations of the parameters. This would involve creating a framework that
jointly optimizes average performance while minimizing worst-case constraint
violations. Such a framework could reveal new tracks for both theoretical
research and practical applications, ultimately enhancing the practical
utility of DFL in problems where constraint parameters are often uncertain and
variable.

##### Extending DFL to multistage settings.

DFL primarily aims to predict parameters for single combinatorial optimization
problems. However, in many practical settings, decision-making occurs over
multiple time periods, resulting in multistage optimization problems (?). This
setting is prevalent in production and inventory management (?), where optimal
decisions are made over an extended time horizon in successive stages. At each
stage, a subset of uncertain parameters is revealed sequentially, and the
decision-maker adjusts their decisions to account for this new information. To
date, no studies have investigated whether applying DFL to predict parameters
in multistage optimization leads to improved final objectives.

Furthermore, in numerous AI and ML applications, optimization tasks often
serve as intermediate steps between two machine learning stages. For example,
consider the task of selecting relevant patches in high-resolution images for
a downstream image recognition task. The patch selection task can be modeled
as a Top-$k$ selection problem (?) and embedded as an intermediate layer
between two neural networks. Here, the upstream neural network assigns scores
to each patch, and the downstream neural network performs the recognition task
using the Top-$k$ patches. Techniques that implement differentiable
optimization layers, such as I-MLE (?), DBB (?), QPTL (?), and DPO (?) can be
applied embedded between the two neural networks. However, their effectiveness
in these contexts needs to be empirically evaluated. Exploring DFL in
multistage settings and its integration in intermediate ML tasks presents a
promising research direction that could lead to the development of methods
capable of handling sequential decision-making processes and complex
optimization tasks embedded within broader ML frameworks.

##### DFL with Real-World Multimodal Datasets.

In real-world applications, uncertainty can arise from various sources.
Multimodal ML aims to train models that process data from diverse sources (?).
In a “multimodal” CO problem, different parameters may be unknown and
associated with distinct sets of features. For instance, in a facility
location problem, both the transport cost and customer demands might be
unknown (?). Each of these parameters could be predicted by different ML
models tailored to their respective feature sets. Integrating DFL with
multimodal datasets introduces several new challenges and opportunities.
Firstly, coordinating the predictions from multiple ML models to inform a
single CO problem requires new methods to ensure coherence and compatibility
between different predicted parameters. This might involve developing novel
fusion techniques to combine information from different modalities
effectively. Secondly, the interdependencies between different parameters need
to be accurately captured. In multimodal settings, the prediction errors from
different models might interact in complex ways, affecting the overall
optimization outcome. Research should explore ways to model these
interdependencies and mitigate the compounded impact of prediction errors.
Finally, empirical evaluation of DFL methodologies on real-world multimodal
datasets would be a crucial avenue to understand their practical utility and
limitations. Such studies have the potential to significantly enhance the
applicability of DFL in solving complex, real-world optimization problems
characterized by diverse and uncertain data sources.

##  7 Conclusion

The survey article began by highligting the significance of Predict-Then-
Optimize problem formulations, wherein an ML model is followed by a CO
problem. The Predict-Then-Optimize problem has emerged as a powerful driving
force in numerous real-world applications of AI, OR and business analytics.
The key challenge in Predict-Then-Optimize problems is predicting the unknown
CO problem parameters in a manner that yields high-quality solutions, in
comparison to the retrospective solutions obtained when using the groundtruth
parameters. To address this challenge, the DFL paradigm has been proposed,
wherein the ML models are directly trained considering the CO problems using
task losses that capture the error encountered after the CO problems.

This survey article provides a comprehensive overview of DFL, highlighting
recent technological advancements, applications and identifying potential
future research directions. Section 2, laid out the problem description with
examples and then presented the two fundamental challenges of DFL:
differentiation through the solutions of combinatorial optimization mapping
and the computational cost associated with solving CO problems in the ML
training loop. Section 3 then distinguished gradient-based DFL techniques from
gradient-free DFL techniques, as well as categorizing gradient-based DFL into
four distinct classes, thoroughly reviewing the trade-offs among them. Section
4 provided examples of DFL applications addressing real-world Predict-Then-
Optimize problems across various domains. Furthermore, Section 5 offered
extensive comparative evaluations on different problem sets, covering 11 DFL
techniques.

Finally, Section 6 discussed some of the open challenges in DFL and outlined
potential research directions. Addressing these challenges can pave the way
for more robust and effective DFL methodologies, further enhancing their
practical utility in solving complex optimization problems. We hope this
survey and corresponding datasets and codes will serve as a catalyst,
inspiring the application of decision-focused learning in diverse domains and
contexts as well as stimulating further methodological research and
advancements.

Acknowledgments

This research was partly funded by the European Research Council (ERC) under
the EU Horizon 2020 research and innovation programme (Grant No 101002802,
CHAT-Opt) and the European Union’s Horizon 2020 research and innovation
programme under grant agreement No 101070149, project Tuples. This research is
also partially supported by NSF grants 2242931, 2232054, 2007164, and NSF
CAREER award 2143706. Victor Bucarey was funded by the ANID Fondecyt
Iniciacion Grant no. 11220864.

## References

  * Abbas and Swoboda Abbas, A., and Swoboda, P. (2021).  Combinatorial optimization for panoptic segmentation: A fully differentiable approach.  In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (Eds.), Advances in Neural Information Processing Systems, Vol. 34, pp. 15635–15649. Curran Associates, Inc.
  * Abernethy, Lee, and Tewari Abernethy, J., Lee, C., and Tewari, A. (2016).  Perturbation techniques in online learning and optimization.  Perturbations, Optimization, and Statistics, 233.
  * Agarap Agarap, A. F. (2019).  Deep learning using rectified linear units (relu)..
  * Agrawal, Amos, Barratt, Boyd, Diamond, and Kolter Agrawal, A., Amos, B., Barratt, S., Boyd, S., Diamond, S., and Kolter, J. Z. (2019a).  Differentiable convex optimization layers.  Advances in neural information processing systems, 32.
  * Agrawal, Barratt, Boyd, Busseti, and Moursi Agrawal, A., Barratt, S., Boyd, S., Busseti, E., and Moursi, W. M. (2019b).  Differentiating through a cone program.  Journal of Applied and Numerical Optimization, 1(2), 107 – 115.
  * Amos and Kolter Amos, B., and Kolter, J. Z. (2017).  Optnet: Differentiable optimization as a layer in neural networks.  In International Conference on Machine Learning, pp. 136–145. PMLR.
  * Amos, Koltun, and Kolter Amos, B., Koltun, V., and Kolter, J. Z. (2019).  The limited multi-label projection layer..
  * Baltrušaitis, Ahuja, and Morency Baltrušaitis, T., Ahuja, C., and Morency, L.-P. (2019).  Multimodal machine learning: A survey and taxonomy.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 41(2), 423–443.
  * Barndorff-Nielsen Barndorff-Nielsen, O. (1978).  Information and exponential families: in statistical theory.  John Wiley & Sons.
  * Baydin, Pearlmutter, Radul, and Siskind Baydin, A. G., Pearlmutter, B. A., Radul, A. A., and Siskind, J. M. (2018).  Automatic differentiation in machine learning: a survey.  Journal of Machine Learning Research, 18(153), 1–43.
  * Bazaraa, Jarvis, and Sherali Bazaraa, M. S., Jarvis, J. J., and Sherali, H. D. (2008).  Linear programming and network flows.  John Wiley & Sons.
  * Bello, Pham, Le, Norouzi, and Bengio Bello, I., Pham, H., Le, Q. V., Norouzi, M., and Bengio, S. (2017).  Neural combinatorial optimization with reinforcement learning.  In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings. OpenReview.net.
  * Ben-Tal, El Ghaoui, and Nemirovski Ben-Tal, A., El Ghaoui, L., and Nemirovski, A. (2009).  Robust optimization, Vol. 28.  Princeton university press.
  * Berthet, Blondel, Teboul, Cuturi, Vert, and Bach Berthet, Q., Blondel, M., Teboul, O., Cuturi, M., Vert, J.-P., and Bach, F. (2020).  Learning with differentiable perturbed optimizers.  In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., and Lin, H. (Eds.), Advances in Neural Information Processing Systems, Vol. 33, pp. 9508–9519.
  * Bertsimas and Kallus Bertsimas, D., and Kallus, N. (2020).  From predictive to prescriptive analytics.  Management Science, 66(3), 1025–1044.
  * Blondel, Teboul, Berthet, and Djolonga Blondel, M., Teboul, O., Berthet, Q., and Djolonga, J. (2020).  Fast differentiable sorting and ranking.  In International Conference on Machine Learning, pp. 950–959. PMLR.
  * Bollobás Bollobás, B. (2013).  Modern graph theory, Vol. 184.  Springer Science & Business Media.
  * Boyd and Vandenberghe Boyd, S. P., and Vandenberghe, L. (2014).  Convex Optimization.  Cambridge University Press.
  * Bucarey, Calderón, Muñoz, and Semet Bucarey, V., Calderón, S., Muñoz, G., and Semet, F. (2023).  Decision-focused predictions via pessimistic bilevel optimization: a computational study..
  * Busseti, Moursi, and Boyd Busseti, E., Moursi, W. M., and Boyd, S. (2019).  Solution refinement at regular points of conic problems.  Computational Optimization and Applications, 74(3), 627–643.
  * Cameron, Hartford, Lundy, and Leyton-Brown Cameron, C., Hartford, J., Lundy, T., and Leyton-Brown, K. (2022).  The perils of learning before optimizing.  Proceedings of the AAAI Conference on Artificial Intelligence, 36(4), 3708–3715.
  * Cao, Qin, Liu, Tsai, and Li Cao, Z., Qin, T., Liu, T.-Y., Tsai, M.-F., and Li, H. (2007).  Learning to rank: from pairwise approach to listwise approach.  In Proceedings of the 24th international conference on Machine learning, pp. 129–136.
  * Chai, Wong, Tong, Chen, and Zhang Chai, Z., Wong, K.-K., Tong, K.-F., Chen, Y., and Zhang, Y. (2022).  Port selection for fluid antenna systems.  IEEE Communications Letters, 26(5), 1180–1184.
  * Chenreddy, Bandi, and Delage Chenreddy, A. R., Bandi, N., and Delage, E. (2022).  Data-driven conditional robust optimization.  In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (Eds.), Advances in Neural Information Processing Systems, Vol. 35, pp. 9525–9537. Curran Associates, Inc.
  * Chu, Zhang, Bai, and Chen Chu, H., Zhang, W., Bai, P., and Chen, Y. (2023).  Data-driven optimization for last-mile delivery.  Complex & Intelligent Systems, 9(3), 2271–2284.
  * Cordonnier, Mahendran, Dosovitskiy, Weissenborn, Uszkoreit, and Unterthiner Cordonnier, J.-B., Mahendran, A., Dosovitskiy, A., Weissenborn, D., Uszkoreit, J., and Unterthiner, T. (2021).  Differentiable patch selection for image recognition.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2351–2360.
  * Dalle, Baty, Bouvier, and Parmentier Dalle, G., Baty, L., Bouvier, L., and Parmentier, A. (2022).  Learning with combinatorial optimization layers: a probabilistic approach..
  * Delage and Ye Delage, E., and Ye, Y. (2010).  Distributionally robust optimization under moment uncertainty with application to data-driven problems.  Operations research, 58(3), 595–612.
  * Demirović, Stuckey, Bailey, Chan, Leckie, Ramamohanarao, and Guns Demirović, E., Stuckey, P. J., Bailey, J., Chan, J., Leckie, C., Ramamohanarao, K., and Guns, T. (2019).  An investigation into prediction+ optimisation for the knapsack problem.  In Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 16th International Conference, CPAIOR 2019, Thessaloniki, Greece, June 4–7, 2019, Proceedings 16, pp. 241–257. Springer.
  * Demirović, Stuckey, Guns, Bailey, Leckie, Ramamohanarao, and Chan Demirović, E., Stuckey, P. J., Guns, T., Bailey, J., Leckie, C., Ramamohanarao, K., and Chan, J. (2020).  Dynamic programming for predict+optimise.  Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), 1444–1451.
  * den Hertog and Postek den Hertog, D., and Postek, K. (2016).  Bridging the gap between predictive and prescriptive analytics-new optimization methodology needed.  In Tilburg Univ, Tilburg, The Netherlands.
  * Dijkstra Dijkstra, E. (1959).  A note on two problems in connexion with graphs.  Numerische Mathematik, 1(1), 269–271.
  * Dinh, Kotary, and Fioretto Dinh, M. H., Kotary, J., and Fioretto, F. (2024).  End-to-end learning for fair multiobjective optimization under uncertainty..
  * Djolonga and Krause Djolonga, J., and Krause, A. (2017).  Differentiable learning of submodular models.  In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (Eds.), Advances in Neural Information Processing Systems, Vol. 30. Curran Associates, Inc.
  * Domke Domke, J. (2010).  Implicit differentiation by perturbation.  In Lafferty, J., Williams, C., Shawe-Taylor, J., Zemel, R., and Culotta, A. (Eds.), Advances in Neural Information Processing Systems, Vol. 23. Curran Associates, Inc.
  * Domke Domke, J. (2012).  Generic methods for optimization-based modeling.  In Artificial Intelligence and Statistics, pp. 318–326. PMLR.
  * Donti, Kolter, and Amos Donti, P. L., Kolter, J. Z., and Amos, B. (2017).  Task-based end-to-end model learning in stochastic optimization.  In Guyon, I., von Luxburg, U., Bengio, S., Wallach, H. M., Fergus, R., Vishwanathan, S. V. N., and Garnett, R. (Eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 5484–5494.
  * El Balghiti, Elmachtoub, Grigas, and Tewari El Balghiti, O., Elmachtoub, A. N., Grigas, P., and Tewari, A. (2019).  Generalization bounds in the predict-then-optimize framework.  In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R. (Eds.), Advances in Neural Information Processing Systems, Vol. 32. Curran Associates, Inc.
  * Elmachtoub, Liang, and McNellis Elmachtoub, A., Liang, J. C. N., and McNellis, R. (2020).  Decision trees for decision-making under the predict-then-optimize framework.  In International Conference on Machine Learning, pp. 2858–2867. PMLR.
  * Elmachtoub and Grigas Elmachtoub, A. N., and Grigas, P. (2022).  Smart “predict, then optimize”.  Management Science, 68(1), 9–26.
  * Elmachtoub, Lam, Zhang, and Zhao Elmachtoub, A. N., Lam, H., Zhang, H., and Zhao, Y. (2023).  Estimate-then-optimize versus integrated-estimation-optimization: A stochastic dominance perspective..
  * Falcon et al. Falcon, W., et al. (2019).  Pytorch lightning.  GitHub. Note: https://github. com/PyTorchLightning/pytorch-lightning, 3(6), 11.
  * Ferber, Griffin, Dilkina, Keskin, and Gore Ferber, A., Griffin, E., Dilkina, B., Keskin, B., and Gore, M. (2023a).  Predicting wildlife trafficking routes with differentiable shortest paths.  In Proceedings of the Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 20th International Conference, CPAIOR 2023.
  * Ferber, Huang, Zha, Schubert, Steiner, Dilkina, and Tian Ferber, A. M., Huang, T., Zha, D., Schubert, M., Steiner, B., Dilkina, B., and Tian, Y. (2023b).  Surco: Learning linear surrogates for combinatorial nonlinear optimization problems.  In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (Eds.), International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, Vol. 202 of Proceedings of Machine Learning Research, pp. 10034–10052. PMLR.
  * Ferber, Wilder, Dilkina, and Tambe Ferber, A. M., Wilder, B., Dilkina, B., and Tambe, M. (2020).  Mipaal: Mixed integer program as a layer.  In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pp. 1504–1511. AAAI Press.
  * Garcia, Street, Homem-de Mello, and Muñoz Garcia, J. D., Street, A., Homem-de Mello, T., and Muñoz, F. D. (2021).  Application-driven learning: A closed-loop prediction and optimization approach applied to dynamic reserves and demand forecasting..
  * Garlappi, Uppal, and Wang Garlappi, L., Uppal, R., and Wang, T. (2006).  Portfolio Selection with Parameter and Model Uncertainty: A Multi-Prior Approach.  The Review of Financial Studies, 20(1), 41–81.
  * Gillick, Kulkarni, Lansing, Presta, Baldridge, Ie, and Garcia-Olano Gillick, D., Kulkarni, S., Lansing, L., Presta, A., Baldridge, J., Ie, E., and Garcia-Olano, D. (2019).  Learning dense representations for entity retrieval.  In Proceedings of the 23rd Conference on Computational Natural Language Learning (CoNLL), pp. 528–537, Hong Kong, China. Association for Computational Linguistics.
  * Gomes, Kautz, Sabharwal, and Selman Gomes, C. P., Kautz, H., Sabharwal, A., and Selman, B. (2008).  Satisfiability solvers.  Foundations of Artificial Intelligence, 3, 89–134.
  * Goodfellow Goodfellow, I. J. (2015).  On distinguishability criteria for estimating generative models.  In Proceedings of ICLR.
  * Goodfellow, Shlens, and Szegedy Goodfellow, I. J., Shlens, J., and Szegedy, C. (2015).  Explaining and harnessing adversarial examples.  In Bengio, Y., and LeCun, Y. (Eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings.
  * Gould, Fernando, Cherian, Anderson, Cruz, and Guo Gould, S., Fernando, B., Cherian, A., Anderson, P., Cruz, R. S., and Guo, E. (2016).  On differentiating parameterized argmin and argmax problems with application to bi-level optimization..
  * Goyal and Gunasekaran Goyal, S. K., and Gunasekaran, A. (1990).  Multi-stage production-inventory systems.  European Journal of Operational Research, 46(1), 1–20.
  * Grant and Boyd Grant, M. C., and Boyd, S. P. (2008).  Graph implementations for nonsmooth convex programs.  In Recent advances in learning and control, pp. 95–110. Springer.
  * Guler, Demirović, Chan, Bailey, Leckie, and Stuckey Guler, A. U., Demirović, E., Chan, J., Bailey, J., Leckie, C., and Stuckey, P. J. (2022).  A divide and conquer algorithm for predict+optimize with non-convex problems.  Proceedings of the AAAI Conference on Artificial Intelligence, 36(4), 3749–3757.
  * Gurobi Optimization Gurobi Optimization, L. (2021).  Gurobi optimizer reference manual.  http://www.gurobi.com.
  * Gutmann and Hyvärinen Gutmann, M., and Hyvärinen, A. (2010).  Noise-contrastive estimation: A new estimation principle for unnormalized statistical models.  In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pp. 297–304.
  * Guyomarch Guyomarch, J. (2017).  Warcraft ii open-source map editor.  http://github.com/war2/war2edit.
  * He, Zhang, Ren, and Sun He, K., Zhang, X., Ren, S., and Sun, J. (2016).  Deep residual learning for image recognition.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR).
  * Hinton, Vinyals, and Dean Hinton, G., Vinyals, O., and Dean, J. (2015).  Distilling the knowledge in a neural network..
  * Hu, Wang, and Gooi Hu, W., Wang, P., and Gooi, H. B. (2016).  Toward optimal energy management of microgrids via robust two-stage optimization.  IEEE Transactions on smart grid, 9(2), 1161–1174.
  * Hu, Lee, and Lee Hu, X., Lee, J. C. H., and Lee, J. H. M. (2023a).  Branch & learn with post-hoc correction for predict+optimize with unknown parameters in constraints.  In Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 264–280. Springer Nature Switzerland.
  * Hu, Lee, and Lee Hu, X., Lee, J. C. H., and Lee, J. H. (2023b).  Two-stage predict+optimize for milps with unknown parameters in constraints.  In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (Eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023.
  * Hu, Lee, and Lee Hu, X., Lee, J. C., and Lee, J. H. (2023c).  Predict+optimize for packing and covering lps with unknown parameters in constraints.  Proceedings of the AAAI Conference on Artificial Intelligence, 37(4), 3987–3995.
  * Hu, Lee, Lee, and Zhong Hu, X., Lee, J. C., Lee, J. H., and Zhong, A. Z. (2022).  Branch & learn for recursively and iteratively solvable problems in predict+optimize.  In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (Eds.), Advances in Neural Information Processing Systems.
  * Huang, He, Gao, Deng, Acero, and Heck Huang, P., He, X., Gao, J., Deng, L., Acero, A., and Heck, L. P. (2013).  Learning deep structured semantic models for web search using clickthrough data.  In He, Q., Iyengar, A., Nejdl, W., Pei, J., and Rastogi, R. (Eds.), 22nd ACM International Conference on Information and Knowledge Management, CIKM’13, San Francisco, CA, USA, October 27 - November 1, 2013, pp. 2333–2338. ACM.
  * Ifrim, O’Sullivan, and Simonis Ifrim, G., O’Sullivan, B., and Simonis, H. (2012).  Properties of energy-price forecasts for scheduling.  In International Conference on Principles and Practice of Constraint Programming, pp. 957–972. Springer.
  * Ignizio and Cavalier Ignizio, J. P., and Cavalier, T. M. (1994).  Linear programming.  Prentice-Hall, Inc.
  * Jeong, Jaggi, Butler, and Sanner Jeong, J., Jaggi, P., Butler, A., and Sanner, S. (2022).  An exact symbolic reduction of linear smart Predict+Optimize to mixed integer linear programming.  In Proceedings of the 39th International Conference on Machine Learning, Vol. 162 of Proceedings of Machine Learning Research, pp. 10053–10067. PMLR.
  * Joachims Joachims, T. (2002).  Optimizing search engines using clickthrough data.  In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, July 23-26, 2002, Edmonton, Alberta, Canada, pp. 133–142. ACM.
  * Johnson-Yu, Wang, Finocchiaro, Taneja, and Tambe Johnson-Yu, S., Wang, K., Finocchiaro, J., Taneja, A., and Tambe, M. (2023).  Modeling robustness in decision-focused learning as a stackelberg game.  In The 22nd International Conference on Autonomous Agents and Multiagent Systems.
  * Kainmueller, Jug, Rother, and Myers Kainmueller, D., Jug, F., Rother, C., and Myers, G. (2014).  Active graph matching for automatic joint segmentation and annotation of c. elegans.  In Golland, P., Hata, N., Barillot, C., Hornegger, J., and Howe, R. D. (Eds.), Medical Image Computing and Computer-Assisted Intervention \- MICCAI 2014 - 17th International Conference, Boston, MA, USA, September 14-18, 2014, Proceedings, Part I, Vol. 8673 of Lecture Notes in Computer Science, pp. 81–88. Springer.
  * Kim, Lewis, and White Kim, S., Lewis, M. E., and White, C. C. (2005).  Optimal vehicle routing with real-time traffic information.  IEEE Transactions on Intelligent Transportation Systems, 6(2), 178–188.
  * Kingma and Ba Kingma, D. P., and Ba, J. (2015).  Adam: A method for stochastic optimization.  In Bengio, Y., and LeCun, Y. (Eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings.
  * Kingma and Welling Kingma, D. P., and Welling, M. (2014).  Auto-encoding variational bayes.  In Bengio, Y., and LeCun, Y. (Eds.), 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings.
  * Kinsey, Tuck, Sinha, and Nguyen Kinsey, S. E., Tuck, W. W., Sinha, A., and Nguyen, T. H. (2023).  An exploration of poisoning attacks on data-based decision making.  In Decision and Game Theory for Security: 13th International Conference, GameSec 2022, Pittsburgh, PA, USA, October 26–28, 2022, Proceedings, pp. 231–252. Springer.
  * Koller and Friedman Koller, D., and Friedman, N. (2009).  Probabilistic graphical models: principles and techniques.  MIT press.
  * Konishi and Fukunaga Konishi, T., and Fukunaga, T. (2021).  End-to-end learning for prediction and optimization with gradient boosting.  In Hutter, F., Kersting, K., Lijffijt, J., and Valera, I. (Eds.), Machine Learning and Knowledge Discovery in Databases, pp. 191–207, Cham. Springer International Publishing.
  * Kotary, Di Vito, Christopher, Van Hentenryck, and Fioretto Kotary, J., Di Vito, V., Christopher, J., Van Hentenryck, P., and Fioretto, F. (2023a).  Predict-then-optimize by proxy: Learning joint models of prediction and optimization..
  * Kotary, Dinh, and Fioretto Kotary, J., Dinh, M. H., and Fioretto, F. (2023b).  Backpropagation of unrolled solvers with folded optimization.  In Elkind, E. (Ed.), Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23, pp. 1963–1970. International Joint Conferences on Artificial Intelligence Organization.
  * Kotary, Fioretto, Van Hentenryck, and Wilder Kotary, J., Fioretto, F., Van Hentenryck, P., and Wilder, B. (2021).  End-to-end constrained optimization learning: A survey.  In Zhou, Z.-H. (Ed.), Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pp. 4475–4482. International Joint Conferences on Artificial Intelligence Organization.  Survey Track.
  * Kotary, Fioretto, Van Hentenryck, and Zhu Kotary, J., Fioretto, F., Van Hentenryck, P., and Zhu, Z. (2022).  End-to-end learning for fair ranking systems.  In Proceedings of the ACM Web Conference 2022, pp. 3520–3530.
  * Lakhera, Shanbhag, and McInerney Lakhera, S., Shanbhag, U. V., and McInerney, M. K. (2011).  Approximating electrical distribution networks via mixed-integer nonlinear programming.  International Journal of Electrical Power & Energy Systems, 33(2), 245–257.
  * Levy, Carmon, Duchi, and Sidford Levy, D., Carmon, Y., Duchi, J. C., and Sidford, A. (2020).  Large-scale methods for distributionally robust optimization.  Advances in Neural Information Processing Systems, 33, 8847–8860.
  * Liu and Liu Liu, B., and Liu, B. (2009).  Theory and practice of uncertain programming, Vol. 239.  Springer.
  * Liu and Grigas Liu, H., and Grigas, P. (2021).  Risk bounds and calibration for a smart predict-then-optimize method.  In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (Eds.), Advances in Neural Information Processing Systems, Vol. 34, pp. 22083–22094. Curran Associates, Inc.
  * Liu, Grigas, Liu, and Shen Liu, M., Grigas, P., Liu, H., and Shen, Z.-J. M. (2023).  Active learning in the predict-then-optimize framework: A margin-based approach..
  * Mandi, Bucarey, Tchomba, and Guns Mandi, J., Bucarey, V., Tchomba, M. M. K., and Guns, T. (2022).  Decision-focused learning: Through the lens of learning to rank.  In Proceedings of the 39th International Conference on Machine Learning, Vol. 162 of Proceedings of Machine Learning Research, pp. 14935–14947. PMLR.
  * Mandi, Canoy, Bucarey, and Guns Mandi, J., Canoy, R., Bucarey, V., and Guns, T. (2021).  Data Driven VRP: A Neural Network Model to Learn Hidden Preferences for VRP.  In Michel, L. D. (Ed.), 27th International Conference on Principles and Practice of Constraint Programming (CP 2021), Vol. 210 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 42:1–42:17.
  * Mandi, Demirović, Stuckey, and Guns Mandi, J., Demirović, E., Stuckey, P. J., and Guns, T. (2020).  Smart predict-and-optimize for hard combinatorial optimization problems.  Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), 1603–1610.
  * Mandi and Guns Mandi, J., and Guns, T. (2020).  Interior point solving for lp-based prediction+optimisation.  In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., and Lin, H. (Eds.), Advances in Neural Information Processing Systems, Vol. 33, pp. 7272–7282.
  * Martins and Astudillo Martins, A., and Astudillo, R. (2016).  From softmax to sparsemax: A sparse model of attention and multi-label classification.  In International conference on machine learning, pp. 1614–1623. PMLR.
  * Massart and Nédélec Massart, P., and Nédélec, É. (2006).  Risk bounds for statistical learning.  The Annals of Statistics, 34(5), 2326–2366.
  * Merchán, Arora, Pachon, Konduri, Winkenbach, Parks, and Noszek Merchán, D., Arora, J., Pachon, J., Konduri, K., Winkenbach, M., Parks, S., and Noszek, J. (2024).  2021 amazon last mile routing research challenge: Data set.  Transportation Science, 58(1), 8–11.
  * Minervini, Franceschi, and Niepert Minervini, P., Franceschi, L., and Niepert, M. (2023).  Adaptive perturbation-based gradient estimation for discrete latent variable models.  Proceedings of the AAAI Conference on Artificial Intelligence, 37(8), 9200–9208.
  * Mišić and Perakis Mišić, V. V., and Perakis, G. (2020).  Data analytics in operations management: A review.  Manufacturing & Service Operations Management, 22(1), 158–169.
  * Mnih and Teh Mnih, A., and Teh, Y. W. (2012).  A fast and simple algorithm for training neural probabilistic language models.  In Proceedings of the 29th International Conference on Machine Learning, ICML 2012, Edinburgh, Scotland, UK, June 26 - July 1, 2012. icml.cc / Omnipress.
  * Monga, Li, and Eldar Monga, V., Li, Y., and Eldar, Y. C. (2021).  Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing.  IEEE Signal Processing Magazine, 38(2), 18–44.
  * Mulamba, Mandi, Diligenti, Lombardi, Bucarey, and Guns Mulamba, M., Mandi, J., Diligenti, M., Lombardi, M., Bucarey, V., and Guns, T. (2021).  Contrastive losses and solution caching for predict-and-optimize.  In Zhou, Z.-H. (Ed.), Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pp. 2833–2840. International Joint Conferences on Artificial Intelligence Organization.
  * Nandwani, Ranjan, Mausam, and Singla Nandwani, Y., Ranjan, R., Mausam, and Singla, P. (2022).  A solver-free framework for scalable learning in neural ilp architectures.  In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (Eds.), Advances in Neural Information Processing Systems, Vol. 35, pp. 7972–7986. Curran Associates, Inc.
  * Nemirovski Nemirovski, A. (2007).  Advances in convex optimization: conic programming.  In International Congress of Mathematicians, Vol. 1, pp. 413–444.
  * Niepert, Minervini, and Franceschi Niepert, M., Minervini, P., and Franceschi, L. (2021).  Implicit mle: Backpropagating through discrete exponential family distributions.  In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (Eds.), Advances in Neural Information Processing Systems, Vol. 34, pp. 14567–14579. Curran Associates, Inc.
  * Ogryczak and Śliwiński Ogryczak, W., and Śliwiński, T. (2003).  On solving linear programs with the ordered weighted averaging objective.  European Journal of Operational Research, 148(1), 80–91.
  * Papandreou and Yuille Papandreou, G., and Yuille, A. L. (2011).  Perturb-and-map random fields: Using discrete optimization to learn and sample from energy models.  In Metaxas, D. N., Quan, L., Sanfeliu, A., and Gool, L. V. (Eds.), IEEE International Conference on Computer Vision, ICCV 2011, Barcelona, Spain, November 6-13, 2011, pp. 193–200. IEEE Computer Society.
  * Paszke, Gross, Massa, Lerer, Bradbury, Chanan, Killeen, Lin, Gimelshein, Antiga, et al. Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al. (2019).  Pytorch: An imperative style, high-performance deep learning library.  Advances in neural information processing systems, 32.
  * Paulus, Rolínek, Musil, Amos, and Martius Paulus, A., Rolínek, M., Musil, V., Amos, B., and Martius, G. (2021).  Comboptnet: Fit the right np-hard problem by learning integer programming constraints.  In International Conference on Machine Learning, pp. 8443–8453. PMLR.
  * Paulus, Choi, Tarlow, Krause, and Maddison Paulus, M., Choi, D., Tarlow, D., Krause, A., and Maddison, C. J. (2020).  Gradient estimation with stochastic softmax tricks.  In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (Eds.), Advances in Neural Information Processing Systems, Vol. 33, pp. 5691–5704. Curran Associates, Inc.
  * Perron and Furnon Perron, L., and Furnon, V. (2020).  Or-tools..
  * Pflug and Pichler Pflug, G. C., and Pichler, A. (2014).  Multistage stochastic optimization, Vol. 1104.  Springer.
  * Pisinger Pisinger, D. (2005).  Where are the hard knapsack problems?.  Computers & Operations Research, 32(9), 2271–2284.
  * Pisinger and Toth Pisinger, D., and Toth, P. (1998).  Knapsack problems.  In Handbook of combinatorial optimization, pp. 299–428. Springer.
  * Pogančić, Paulus, Musil, Martius, and Rolinek Pogančić, M. V., Paulus, A., Musil, V., Martius, G., and Rolinek, M. (2020).  Differentiation of blackbox combinatorial solvers.  In International Conference on Learning Representations.
  * PyTorch PyTorch (2017).  Pytorch: Reducelronplateau — pytorch 1.9.0 documentation..  https://pytorch.org/docs/stable/generated/torch.optim.lr_scheduler.ReduceLROnPlateau.html#torch.optim.lr_scheduler.ReduceLROnPlateau.
  * Qi, Grigas, and Shen Qi, M., Grigas, P., and Shen, Z.-J. M. (2023).  Integrated conditional estimation-optimization..
  * Qi and Shen Qi, M., and Shen, Z.-J. (2022).  Integrating prediction/estimation and optimization with applications in operations management, pp. 36–58.  INFORMS.
  * Rezende, Mohamed, and Wierstra Rezende, D. J., Mohamed, S., and Wierstra, D. (2014).  Stochastic backpropagation and approximate inference in deep generative models.  In Xing, E. P., and Jebara, T. (Eds.), Proceedings of the 31st International Conference on Machine Learning, Vol. 32 of Proceedings of Machine Learning Research, pp. 1278–1286, Bejing, China. PMLR.
  * Rolinek, Musil, Paulus, Vlastelica, Michaelis, and Martius Rolinek, M., Musil, V., Paulus, A., Vlastelica, M., Michaelis, C., and Martius, G. (2020a).  Optimizing rank-based metrics with blackbox differentiation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR).
  * Rolínek, Swoboda, Zietlow, Paulus, Musil, and Martius Rolínek, M., Swoboda, P., Zietlow, D., Paulus, A., Musil, V., and Martius, G. (2020b).  Deep graph matching via blackbox differentiation of combinatorial solvers.  In Vedaldi, A., Bischof, H., Brox, T., and Frahm, J. (Eds.), Computer Vision - ECCV 2020 - 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XXVIII, Vol. 12373 of Lecture Notes in Computer Science, pp. 407–424. Springer.
  * Rossi, van Beek, and Walsh Rossi, F., van Beek, P., and Walsh, T. (Eds.). (2006).  Handbook of Constraint Programming, Vol. 2 of Foundations of Artificial Intelligence.  Elsevier.
  * Ruszczyński and Shapiro Ruszczyński, A., and Shapiro, A. (2003).  Stochastic programming models.  Handbooks in operations research and management science, 10, 1–64.
  * Sadana, Chenreddy, Delage, Forel, Frejinger, and Vidal Sadana, U., Chenreddy, A., Delage, E., Forel, A., Frejinger, E., and Vidal, T. (2024).  A survey of contextual optimization methods for decision-making under uncertainty.  In European Journal of Operational Research.
  * Sahinidis Sahinidis, N. V. (2004).  Optimization under uncertainty: state-of-the-art and opportunities.  Computers & Chemical Engineering, 28(6), 971–983.
  * Sahoo, Paulus, Vlastelica, Musil, Kuleshov, and Martius Sahoo, S. S., Paulus, A., Vlastelica, M., Musil, V., Kuleshov, V., and Martius, G. (2023).  Backpropagation through combinatorial algorithms: Identity with projection works.  In The Eleventh International Conference on Learning Representations.
  * Sang, Xu, Long, Hu, and Sun Sang, L., Xu, Y., Long, H., Hu, Q., and Sun, H. (2022).  Electricity price prediction for energy storage system arbitrage: A decision-focused approach.  IEEE Transactions on Smart Grid, 13(4), 2822–2832.
  * Sen, Namata, Bilgic, Getoor, Galligher, and Eliassi-Rad Sen, P., Namata, G., Bilgic, M., Getoor, L., Galligher, B., and Eliassi-Rad, T. (2008).  Collective classification in network data.  AI Magazine, 29(3), 93.
  * Settles Settles, B. (2009).  Active learning literature survey.  Computer sciences technical report 1648, University of Wisconsin–Madison.
  * Shah, Wang, Wilder, Perrault, and Tambe Shah, S., Wang, K., Wilder, B., Perrault, A., and Tambe, M. (2022).  Decision-focused learning without decision-making: Learning locally optimized decision losses.  In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (Eds.), Advances in Neural Information Processing Systems.
  * Shah, Wilder, Perrault, and Tambe Shah, S., Wilder, B., Perrault, A., and Tambe, M. (2024).  Leaving the nest: Going beyond local loss functions for predict-then-optimize.  In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38, pp. 14902–14909.
  * Silvestri, Berden, Mandi, İrfan Mahmutoğulları, Mulamba, Filippo, Guns, and Lombardi Silvestri, M., Berden, S., Mandi, J., İrfan Mahmutoğulları, A., Mulamba, M., Filippo, A. D., Guns, T., and Lombardi, M. (2023).  Score function gradient estimation to widen the applicability of decision-focused learning..
  * Simonis, O’Sullivan, Mehta, Hurley, and Cauwer Simonis, H., O’Sullivan, B., Mehta, D., Hurley, B., and Cauwer, M. D. (1999).  CSPLib problem 059: Energy-cost aware scheduling.  http://www.csplib.org/Problems/prob059.
  * Singh and Joachims Singh, A., and Joachims, T. (2018).  Fairness of exposure in rankings.  In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2219–2228.
  * Sun, Liu, and Li Sun, C., Liu, L., and Li, X. (2023).  Predict-then-calibrate: A new perspective of robust contextual lp.  In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (Eds.), Advances in Neural Information Processing Systems, Vol. 36, pp. 17713–17741. Curran Associates, Inc.
  * Tan, Delong, and Terekhov Tan, Y., Delong, A., and Terekhov, D. (2019).  Deep inverse optimization.  In Rousseau, L., and Stergiou, K. (Eds.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 16th International Conference, CPAIOR 2019, Thessaloniki, Greece, June 4-7, 2019, Proceedings, Vol. 11494 of Lecture Notes in Computer Science, pp. 540–556. Springer.
  * Tan, Terekhov, and Delong Tan, Y., Terekhov, D., and Delong, A. (2020).  Learning linear programs from optimal decisions.  In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (Eds.), Advances in Neural Information Processing Systems, Vol. 33, pp. 19738–19749.
  * Tang and Khalil Tang, B., and Khalil, E. B. (2023a).  Multi-task predict-then-optimize.  In Sellmann, M., and Tierney, K. (Eds.), Learning and Intelligent Optimization, pp. 506–522. Springer International Publishing.
  * Tang and Khalil Tang, B., and Khalil, E. B. (2023b).  Pyepo: A pytorch-based end-to-end predict-then-optimize library for linear and integer programming..
  * Tian, Yan, Liu, and Wang Tian, X., Yan, R., Liu, Y., and Wang, S. (2023).  A smart predict-then-optimize method for targeted and cost-effective maritime transportation.  Transportation Research Part B: Methodological, 172, 32–52.
  * Toth and Vigo Toth, P., and Vigo, D. (2015).  Vehicle routing: Problems, methods, and applications.  Society for Industrial and Applied Mathematics.
  * Tschiatschek, Sahin, and Krause Tschiatschek, S., Sahin, A., and Krause, A. (2018).  Differentiable submodular maximization.  In Lang, J. (Ed.), Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, pp. 2731–2738. ijcai.org.
  * Tschora, Guns, Pierre, Plantevit, and Robardet Tschora, L., Guns, T., Pierre, E., Plantevit, M., and Robardet, C. (2023).  Electricity price forecasting based on order books: a differentiable optimization approach.  In 2023 IEEE 10th International Conference on Data Science and Advanced Analytics (DSAA), pp. 1–10.
  * Vapnik Vapnik, V. (1999).  An overview of statistical learning theory.  IEEE Trans. Neural Networks, 10(5), 988–999.
  * Wahdany, Schmitt, and Cremer Wahdany, D., Schmitt, C., and Cremer, J. L. (2023).  More than accuracy: end-to-end wind power forecasting that optimises the energy system.  Electric Power Systems Research, 221, 109384.
  * Wang, Shah, Chen, Perrault, Doshi-Velez, and Tambe Wang, K., Shah, S., Chen, H., Perrault, A., Doshi-Velez, F., and Tambe, M. (2021).  Learning mdps from features: Predict-then-optimize for sequential decision making by reinforcement learning.  Advances in Neural Information Processing Systems, 34, 8795–8806.
  * Wang, Donti, Wilder, and Kolter Wang, P.-W., Donti, P., Wilder, B., and Kolter, Z. (2019).  Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver.  In International Conference on Machine Learning, pp. 6545–6554. PMLR.
  * Wang, Zhang, Guo, Chen, Yang, and Yan Wang, R., Zhang, Y., Guo, Z., Chen, T., Yang, X., and Yan, J. (2023).  LinSATNet: The positive linear satisfiability neural networks.  In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (Eds.), Proceedings of the 40th International Conference on Machine Learning, Vol. 202 of Proceedings of Machine Learning Research, pp. 36605–36625. PMLR.
  * Wilder, Dilkina, and Tambe Wilder, B., Dilkina, B., and Tambe, M. (2019a).  Melding the data-decisions pipeline: Decision-focused learning for combinatorial optimization.  In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019, pp. 1658–1665. AAAI Press.
  * Wilder, Ewing, Dilkina, and Tambe Wilder, B., Ewing, E., Dilkina, B., and Tambe, M. (2019b).  End to end learning and optimization on graphs.  In Wallach, H. M., Larochelle, H., Beygelzimer, A., d’Alché-Buc, F., Fox, E. B., and Garnett, R. (Eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 4674–4685.
  * Williams Williams, R. J. (1992).  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  Mach. Learn., 8, 229–256.
  * Wong, Tong, Zhang, and Zhongbin Wong, K.-K., Tong, K.-F., Zhang, Y., and Zhongbin, Z. (2020).  Fluid antenna system for 6g: When bruce lee inspires wireless communications.  Electronics Letters, 56(24), 1288–1290.
  * Yang, Yan, and Wang Yang, Y., Yan, R., and Wang, H. (2022).  Pairwise-comparison based semi-spo method for ship inspection planning in maritime transportation.  Journal of Marine Science and Engineering, 10(11), 1696\.
  * Zou, Zhu, and Hastie Zou, H., Zhu, J., and Hastie, T. (2008).  New multicategory boosting algorithms based on multicategory fisher-consistent losses.  The Annals of Applied Statistics, 2(4), 1290.

##  A Results on All Problem Instances

In the main text, boxplots of some problem instances are presented to save
space in the main text. In this section of Appendix, the boxplots of all the
instances are provided. Figure A1, Figure A2, Figure A3, Figure A4, Figure A5,
Figure A6, and Figure A7 display the boxplots for all the instances of the
grid shortest path problem, the portfolio optimization problem, the Warcraft
shortest path problem, the energy-cost aware scheduling problem, the knapsack
problem, the diverse bipartite matching problem, and the subset selection
problem respectively.

Figure A1: Comparative evaluations on the synthetic shortest path problem with
noise-halfwidth parameter $\vartheta$ = 0.5. These boxplots show the
distributions of relative regrets. Figure A2: Comparative evaluations on the
synthetic portfolio optimization problem with noise magnitude $\vartheta=1$.
These boxplots show the distributions of absolute regrets. Figure A3:
Comparative evaluations on the Warcraft shortest path problem instances. These
boxplots show the distributions of relative regrets. Figure A4: Comparative
evaluations on the energy-cost aware scheduling problem instances. These
boxplots show the distributions of relative regrets. Figure A5: Comparative
evaluations on the knapsack problem instances. These boxplots show the
distributions of relative regrets. Figure A6: Comparative evaluations on the
diverse bipartite matching problem instances. These boxplots show the
distributions of relative regrets. Figure A7: Comparative evaluations on the
subset selection problem instances. This boxplot shows the distributions of
mismatch rates.

##  B Learning Curves

In this section, the learning curves of the LTR loss functions on the three
instances of the scheduling problem are presented. Figure A8 reveals that
learning with Pairwise (diff) ranking loss is stable whereas learning with
Listwise and Pairwise ranking losses do not stabilize.

Figure A8: Learning Curves on the energy scheduling problem instances of for
the LTR losses.

(a) $\rho_{1}=\rho_{2}=10\%$

(b) $\rho_{1}=\rho_{2}=25\%$

(c) $\rho_{1}=\rho_{2}=50\%$

(d)

Figure A9: Learning Curves on the diverse bipartite matching problem.

##  C Details about Hyperparameter Configuration

The hyperparameters for each methodology in each experiment are selected
through grid search, as described in Section 5.2. For the sake of
reproducibility, this section provides the lists of optimal hyperparameter
combinations found by grid search and used to evaluate all the methodologies.
Table A1, Table A2, Table A3, Table A4, Table A5, Table A6 present the
hyperaprameter combinations for the instances of the shortest path problem on
the grid, portfolio optimization problem, Warcraft shortest path problem,
energy-cost aware scheduling, knapsack problem and diverse bipartite matching
problem respectively.

Deg |  1 | 2 | 4 | 6 | 8
---|---|---|---|---|---
PF (lr) | 1. | 0.05 | 0.05 | 1. | 0.05
SPO (lr) | 0.01 | 0.05 | 0.1 | 1. | 1.
DBB (lr, $\lambda$) | (0.1, 10.) | (0.1,1.) | (0.05, 1.) | (0.05, 0.1) | (0.1, 0.1)
I-MLE (lr, $\lambda$, $\epsilon$, $\kappa$) | (0.5, 100, 1, 5) | (0.5, 100, 0.1, 5) | (0.5, 100.,2.,5) | (0.5, 10., 0.5, 5) | (0.5, 100., 2., 5)
FY (lr, $\epsilon$) | (1., 5) | (0.1, 0.1) | (0.1, 0.1) | (0.05, 5.) | (0.1, 5.)
HSD (lr, $\mu$, damping) | (0.1, 0.001, 1.0) | (0.1, 0.1, 0.01) | (0.1, $10^{-6}$, 0.1) | (0.1, 0.001, $10^{-6}$) | (0.1, 10., 1.)
QPTL (lr, $\mu$) | (0.1, 10.) | (0.5, 10.) | (0.1, 1.) | (0.1, 10.) | (0.1, 10.)
Listwise (lr, $\tau$) | (0.1, 0.1) | (0.1, 0.1) | (1., 0.1) | (0.1, 1.) | (1., 1.)
Pairwise (lr, $\Theta$ ) | (1., 1.) | (0.1, 0.5) | (0.1, 1.) | (1., 10.) | (1., 10.)
Pairwise(diff) (lr) | 0.1 | 0.1 | 0.5 | 0.1 | 1.
MAP (lr) | 0.1 | 0.1 | 1. | 1. | 1.

Table A1: Optimal Hyperparameter Combination for the shortest path problems on
a $5\times 5$ grid.

Deg |  1 | 4 | 8 | 16
---|---|---|---|---
PF (lr) | 0.01 | 0.05 | 0.1 | 0.05
SPO (lr) | 0.5 | 1. | 0.5 | 0.5
DBB (lr, $\lambda$) | (1., 0.1) | (1., 0.1) | (1., 0.1) | (1., 0.1)
I-MLE (lr, $\lambda$, $\epsilon$, $\kappa$) | (0.5, 0.1, 0.1, 5) | (0.5, 0.1, 0.5, 5) | (0.5, 0.1, 0.05,5) | (0.5, 0.1, 0.05,5)
FY (lr, $\epsilon$) | (0.1, 0.01) | (0.5, 0.01) | (1, 0.01) | (1., 2.)
QPTL (lr, $\mu$) | (0.1, 10.) | (0.05, 10.) | (0.1, 10.) | (0.05, 10.)
Listwise (lr, $\tau$) | (0.1, 0.01) | (0.1, 0.01) | (0.1, 0.01) | (0.05, 0.005)
Pairwise (lr, $\Theta$ ) | (0.01, 0.01) | (0.01, 0.1) | (0.01, 0.01) | (0.1, 0.05)
Pairwise(diff) (lr) | 0.1 | 0.1 | 0.1 | 0.05
MAP (lr) | 0.01 | 1. | 0.05 | 1.

Table A2: Optimal Hyperparameter Combination for the portfolio optimization
problem instances.

Image Size | 30 | 24 | 18 | 12
---|---|---|---|---
PF (lr) | 0.01 | 0.001 | 0.0005 | 0.001
SPO (lr) | 0.0005 | 0.005 | 0.01 | 0.005
DBB (lr, $\lambda$) | (0.005, 10.) | (0.001, 100.) | (0.001, 10.) | (0.001, 10.)
I-MLE (lr, $\lambda$, $\epsilon$, $\kappa$) | (.001, 100, 0.05, 50) | (0.001, 10., 0.05, 50) | (0.01, 10., 0.05, 5) | (0.001, 10., 0.05, 50)
FY (lr, $\epsilon$) | (0.001, 0.01) | (0.01, 0.01) | (0.01, 0.01) | (0.01, 0.01)
Listwise (lr, $\tau$) | (0.005, 1.) | (0.005, 0.5) | ( 0.005, 0.05) | (0.005, 0.5)
Pairwise (lr, $\Theta$ ) | (0.01, 0.1) | (0.01 ,0.1) | (0.005, 0.1) | (0.01, 0.1)
Pairwise(diff) (lr) | 0.005 | 0.005 | 0.005 | 0.005
MAP (lr) | 0.01 | 0.005 | 0.005 | 0.005

Table A3: Optimal Hyperparameter Combination for the Warcraft shortest path problem instances. Instance | 1 | 2 | 3
---|---|---|---
PF (lr) | 0.5 | 0.5 | 0.5
SPO (lr) | 1. | 0.5 | 0.5
DBB (lr, $\lambda$) | (0.01, 0.1) | (0.5, 1.) | (0.5, 1.)
I-MLE (lr, $\lambda$, $\epsilon$, $\kappa$) | (0.5, 1., 2., 5) | (0.5, 1., 1., 5) | (0.5, 1., 1., 5)
FY (lr, $\epsilon$) | (0.01, 0.1) | (0.5, 5) | (0.01, 0.1)
HSD (lr, $\mu$, damping) | (0.1, 0.1, $10^{-6}$ ) | (0.1, 0.001, $10^{-6}$) | (0.1, 0.1, 0.1)
QPTL (lr, $\mu$) | (0.1, 1.) | (0.1, 1.) | (0.1, 1.)
Listwise (lr, $\tau$) | (0.1, 5.) | (0.1, 5.) | (0.1, 5.)
Pairwise (lr, $\Theta$ ) | (0.1, 1.) | (0.1, 5.) | (0.1, 50.)
Pairwise(diff) (lr) | 0.5 | 0.5 | 0.1
MAP (lr) | 0.5 | 0.5 | 0.5
Table A4: Optimal Hyperparameter Combination for the energy-cost aware scheduling problem instances. Capacity | 60 | 120 | 180
---|---|---|---
PF (lr) | 0.5 | 1. | 1.
SPO (lr) | 0.5 | 1. | 1.
DBB (lr, $\lambda$) | (0.5, 0.1) | (1., 1.) | (0.5, 1.)
I-MLE (lr, $\lambda$, $\epsilon$, $\kappa$) | (0.5, 0.1, 0.5, 5) | (0.5, 0.1, 0.1, 5) | (0.5, 0.1, 5., 5)
FY (lr, $\epsilon$) | (1., 0.005) | (1., 0.5) | (0.5, 0.5)
HSD (lr, $\mu$, damping) | (0.5, 0.01, 10.) | (0.5, 0.1, 10.) | (1., 0.01, 0.1)
QPTL (lr, $\mu$) | (0.5, 10.) | (0.5, 1.) | (0.5, 0.1)
Listwise (lr, $\tau$) | (1., 0.001) | (1., 0.001) | (0.5, 0.0001)
Pairwise (lr, $\Theta$ ) | (0.5, 10.) | (0.5, 10.) | (0.5, 10.)
Pairwise(diff) (lr) | 1. | 1. | 1.
MAP (lr) | 1. | 1. | 1.
Table A5: Optimal Hyperparameter Combination for the knapsack problem instances. $(\rho_{1},\rho_{2})$ | (10%, 10%) | (25%, 25%) | (50%, 50%)
---|---|---|---
PF (lr) | 0.01 | 0.01 | 0.0005
SPO (lr) | 0.001 | 0.001 | 0.005
DBB (lr, $\lambda$) | (0.01, 10.) | (0.01, 0.1) | (0.01, 1.)
I-MLE (lr, $\lambda$, $\epsilon$, $\kappa$) | (0.001, 100, 0.5, 5) | (0.001, 100., 0.5, 5) | ( 0.001, 100., 0.5, 5)
FY (lr, $\epsilon$) | ( 0.001, 0.5) | (0.001, 0.01) | (0.001, 5.)
HSD (lr, $\mu$, damping) | (0.001, 1., 0.1) | (0.05, 0.1, 10.) | (0.001, 0.1, 0.1)
QPTL (lr, $\mu$) | ( 0.01, 100.) | (0.001. 10.) | (0.001, 10.)
Listwise (lr, $\tau$) | (0.001, 5.) | (0.01, 5.) | (0.01, 5.)
Pairwise (lr, $\Theta$ ) | ( 0.005, 5) | (0.01, 50.) | (0.01, 50.)
Pairwise(diff) (lr) | 0.001 | 0.01 | 0.005
MAP (lr) | 0.001 | 0.01 | 0.005
Table A6: Optimal Hyperparameter Combination for the diverse bipartite
matching problem instances.