Pareto-Informed Smart "Predict, then Optimize" for Multi-Objective Combinatorial Problems
Organizations: University of Würzburg
Abstract
Many real-world planning applications, from logistics, routing to resource allocation, give rise to optimization problems that need to balance multiple, conflicting objectives. While machine learning is often used to predict the unknown parameters or costs of these problems, standard models trained on prediction accuracy can lead to suboptimal plans. Decision-Focused Learning (DFL) addresses this by integrating the downstream optimization task into the training objective. However, existing DFL methods for multi-objective problems rely on simple scalarization, which fails to capture the rich trade-offs of the Pareto Frontier. To address this gap, we propose a Pareto-aware extension to single-objective Smart "Predict, then Optimize" (SPO+) for multi-objective combinatorial optimization problems. Our loss function leverages the true Pareto Frontier, forming a target decision that aligns with a sampled preference vector, and minimizes regret against this target. Experiments on multi-objective shortest path and multi-objective knapsack problems show that our approach outperforms traditional two-stage Mean Squared Error (MSE) baselines. It also surpasses scalarization-based SPO+ approaches.
Figures & tables
| Problem | Method | = 0 | = 0.25 | = 0.5 |
|---|---|---|---|---|
| MOSPP | Avg. Cost | 13.90 2.69 | 17.28 3.18 | 24.57 4.14 |
| MSE | 1.15 0.06 | 5.51 0.23 | 13.43 0.56 | |
| SPO+ (LS) | 0.98 0.07 | 5.10 0.26 | 12.47 0.48 | |
| ParetoSPO | 0.70 0.04 | 4.82 0.20 | 12.00 0.31 | |
| MOMDKP | Avg. Cost | 32.87 6.46 | 37.53 7.76 | 46.63 8.15 |
| MSE | 12.65 4.60 | 20.41 6.35 | 33.48 5.96 |
Predict-Then-Optimize
Predict-then-optimize trains or evaluates predictors by how well their outputs support downstream decisions under constraints.
See all 43 papersScalable Decision-Focused Learning through Cost-Sensitive Regression
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.