Organizations: School of Architecture, Building and Civil Engineering, Loughborough University, UK · Department of Computer Science, KU Leuven, Leuven, Belgium · Institute of Engineering Sciences, Universidad de O’Higgins, Rancagua, Chile · Department of Statistics and Operations Research, Universidad de Murcia, Murcia, Spain
Many combinatorial optimization (CO) problems involve parameters that are uncertain when the problem must be solved. In such settings, the parameters have to be predicted from correlated contextual information before a solution can be computed. Decision-focused learning (DFL) addresses this by training the predictive model to produce predictions that optimize downstream decision quality. Most existing DFL methods are risk-neutral and minimize the expected regret. In high-stakes applications this can lead to undesirable outcomes, because decision-makers must also account for the tail risk of decision quality. Prior risk-sensitive approaches typically model uncertainty explicitly and solve a stochastic or robust optimization problem at inference time, which increases computational complexity. We instead propose a DFL framework that achieves risk-sensitive behavior while retaining point predictions and deterministic optimization at inference time. Starting from the dual representation of the Conditional Value-at-Risk (CVaR) and adding entropy regularization, we derive a smooth surrogate for the CVaR of regret. Its gradient induces an instance-dependent reweighting within each minibatch that emphasizes high-risk outcomes, so the approach can turn existing surrogate-loss DFL methods, including the SPO+ loss, into risk-sensitive variants. When instantiated with SPO+, the resulting objective admits a generalization bound on the CVaR of the true regret. Experiments on knapsack, portfolio, shortest-path, and energy-aware scheduling problems show substantial reductions in tail regret when the uncertain parameters exhibit heterogeneous tail behavior.
Figures & tables
Case 1
Case 2
A
B
A
B ′
Travel time, normal scenario ( p=0.9 )
30
20
30
40
Travel time, rare scenario ( p=0.1 )
30
60
30
5
Regret, normal scenario
10
0
0
10
Regret, rare scenario
0
30
25
0
\CVaR0.9 of travel time
30
60
30
40
Table 1: Travel times and regrets (in minutes) in the illustrative example. Bold entries mark the route preferred by each CVaR objective.
Problem
Data
Method
Batch size
β
Learning rate
Portfolio (50 assets)
Heterogeneous
MSE
32
–
0.005
Heterogeneous
SPO+
128
–
0.005
Heterogeneous
RESTROSPO+ (exact η )
128
50
0.005
Heterogeneous
RESTROSPO+ (quantile η )
128
10
0.005
Homogeneous
MSE
128
–
0.005
Homogeneous
SPO+
64
–
0.005
Table 2: Selected Hyperparameters for Each Problem, Dataset, and Method.
Problem
MSE
SPO+
RESTROSPO+ (exact η )
RESTROSPO+ (quantile η )
Portfolio
0.00±0.00
0.00±0.00
0.00±0.00
0.00±0.00
Shortest path
0.53±0.11
0.38±0.07
0.38±0.06
0.39±0.07
Knapsack
2.30±0.30
1.61±0.07
1.61±0.11
1.62±0.09
Table 3: CVaR0.9 of Regret on the PyEPO Datasets with Homogeneous Cost Vectors.
Problem
MSE
SPO+
RESTROSPO+ (exact η )
RESTROSPO+ (quantile η )
Portfolio
0.43±0.01
0.42±0.01
0.39±0.01
0.39±0.01
Shortest path
5.36±0.83
11.04±0.96
4.99±0.63
5.07±0.55
Knapsack
10.73±1.50
20.54±5.11
8.18±0.84
8.07±0.90
Table 4: CVaR0.9 of Regret on the Datasets with Heterogeneous Long-Tail Cost Vectors.
Heterogeneous
Homogeneous
Problem
Method
CVaR0.9
Time (s)
CVaR0.9
Time (s)
Shortest path
MSE
5.36±0.83
2.11±0.04
0.53±0.11
2.28±0.07
SPO+
11.04±0.96
10.09±0.33
0.38±0.07
10.54±0.31
RESTROSPO+ (exact η )
4.99±0.63
11.41±0.85
0.38±0.06
11.67±0.85
RESTROSPO+ (quantile η )
5.07±0.55
10.37±0.17
0.39±0.07
10.11±0.20
Knapsack
MSE
10.73±1.50
7.38±0.78
2.30±0.30
7.67±0.53
Table 5: Exact Threshold ηβ⋆ Versus Quantile Approximation ηα : CVaR0.9 of Regret and Training Time (s).
Heterogeneous
Homogeneous
Problem
η
Normalized
CVaR0.9
Time (s)
CVaR0.9
Time (s)
Shortest path
Exact
No
4.99±0.63
11.41±0.85
0.38±0.06
11.67±0.85
Exact
Yes
5.02±0.56
10.67±0.05
0.39±0.07
10.27±0.06
Quantile
No
4.99±0.42
10.08±0.09
0.39±0.07
10.12±0.07
Quantile
Yes
5.07±0.55
10.37±0.17
0.39±0.07
10.11±0.20
Knapsack
Exact
No
8.18±0.84
29.38±4.16
1.61±0.11
38.22±3.58
Table 6: Effect of Normalizing the Losses by the Threshold: CVaR0.9 of Regret and Training Time (s) of RESTROSPO+ .
Data
Method
CVaR0.9
Time (s)
Original
MSE
166,331.07
35.90
SPO+ (cached)
159,213.45
98.10
SPO+ (non-cached)
159,032.17
1,102.86
RESTROSPO+ (exact η )
157,237.15
106.83
RESTROSPO+ (quantile η )
157,176.50
97.88
Heterogeneous
MSE
242,105.05
35.41
Table 7: Energy-Aware Scheduling with 10 Tasks: CVaR0.9 of Regret and Training Time (s).
Many real-world combinatorial problems involve uncertain parameters, which can be predicted given contextual features and historical data. These predict-then-optimize' or contextual optimization' problems have gained significant attention: end-to-end training methods can now minimize the downstream task cost rather than the predictive error. However, despite their effectiveness, these decision-focused learning (DFL) approaches often rely on repeated solving of the underlying combinatorial optimization problem during training, making them computationally expensive and difficult to scale. We reframe the learning problem as a cost-sensitive multi-output regression problem: multi-output due to the combinatorial problem having multiple uncertain parameters, and cost-sensitive due to the downstream task cost being the real target. Our technical contribution is the formalization of multiple loss function components that follow from this reframing: cost-insensitive normalization, decision-aware asymmetric penalization of over- and underpredictions, and instance-based costs that mimic the true downstream task-based loss locally. These components require zero or one solve per training data instance, while requiring no further solves during training. Experiments show that the combination of loss components achieves comparable downstream task quality to the state of the art, while being significantly more efficient, enabling scaling to problem sizes that have not been tackled before with DFL.
Noah Schutte, Senne Berden, Tias Guns +2
Delft University of Technology · KU Leuven · Independent Researcher
When solving optimization problems under uncertainty with contextual data, utilizing machine learning to predict the uncertain parameters' values is a popular and effective approach. Decision-focused learning (DFL) aims at learning a predictive model such that decision quality, instead of prediction accuracy, is maximized. Common practice is to predict a single scenario representing the uncertain parameters, implicitly assuming that there exists a deterministic problem approximation (proxy) that allows for optimal decision-making. The opposite has also been considered, where the underlying distribution is estimated with a parameterized distribution. However, little is known about when either choice is valid. This paper investigates for the first time problem properties that justify using a certain decision proxy. Using this, we present alternative decision proxies for DFL, with little or no compromise on the complexity of the learning task. We show the effectiveness of presented approaches in experiments on continuous and discrete problems, as well as problems with uncertainty in the objective function and in the constraints.
Noah Schutte, Grigorii Veviurko, Krzysztof Postek +1
Delft University of Technology · Independent Researcher
Plugging predictions of unknown parameters into downstream optimization problems, often referred to as the ``predict-then-optimize'' paradigm, has long been a standard approach in decision-making under uncertainty. However, improved predictive accuracy does not, in general, translate into improved decision quality. This disconnect has motivated growing interest in decision-focused learning (DFL) within the operations research community. This tutorial reviews recent developments in DFL and highlights key methodological insights, with a particular focus on stochastic linear programming as the downstream decision-making problem. We discuss why several widely used tools in traditional statistical learning are not directly suited to decision-focused settings and must be rethought, including (i) data collection strategies driven purely by predictive uncertainty and (ii) distributional distance measures such as the Wasserstein distance. We summarize properties of DFL that distinguish it from conventional predictive modeling and provide insights into the development of new decision-focused tools.
Mo Liu
Department of Statistics and Operations Research, University of North Carolina at Chapel Hill