Pareto-Informed Smart "Predict, then Optimize" for Multi-Objective Combinatorial Problems

Aabhash Dhakal, Tim Lachner

TL;DR

This paper introduces ParetoSPO, a novel Decision-Focused Learning (DFL) framework that extends the popular "Smart Predict, then Optimize" (SPO+) approach to multi-objective problems. By leveraging the true Pareto Frontier during training, ParetoSPO overcomes the limitations of simple scalarization, allowing models to make high-quality decisions even in complex, non-convex trade-off spaces.

What Problem Does This Paper Address?

In many real-world scenarios—like routing a delivery truck or managing a power grid—we face two major hurdles:

  1. Uncertainty: We don't know the exact costs (e.g., traffic delays, fuel prices) and must predict them using machine learning.
  2. Conflicting Goals: We want to minimize time and cost and emissions simultaneously.

The traditional "Predict, then Optimize" approach treats these as separate steps: first, minimize prediction error (like Mean Squared Error), then feed those predictions into a solver. However, minimizing prediction error doesn't always lead to the best decisions—a small error in a critical cost can lead to a disastrously bad plan. This is the prediction-decision gap.

Prediction Focused Learning vs. Decision Focused Learning

Decision-Focused Learning (DFL) closes this gap by training the ML model directly on the quality of the final decision. But for multi-objective problems, existing DFL methods rely on "scalarization"—turning multiple goals into one weighted sum. This fails for many combinatorial problems where the "Pareto Frontier" (the set of optimal trade-offs) is non-convex; scalarization simply cannot "see" solutions in those non-convex regions.

Methods

The authors propose ParetoSPO, which bridges the gap between efficient single-objective DFL and complex Pareto-based optimization.

  • Model Committee: Instead of one giant model, they train a "committee" of expert models. Each expert is specialized for a specific user preference (e.g., one expert for "fastest delivery," another for "lowest fuel cost").
  • Pareto-Informed Target Selection: This is the core innovation. During training, the system uses a multi-objective solver offline to find the true Pareto Frontier for the training data. For a given preference, it selects the "best" target solution from this true frontier using cosine similarity.
  • Hybrid Loss Function: The model then calculates a loss based on the difference between the decision made using its current predictions and this high-quality, Pareto-optimal target. This provides a geometrically sound learning signal that guides the model toward the correct region of the solution space, regardless of non-convexity.
The ParetoSPO training and inference pipeline

Datasets

The researchers evaluated their method using the PyEPO framework on two classic combinatorial problems:

  • Multi-Objective Shortest Path Problem (MOSPP): Finding paths in grid graphs (4x4 and 5x5) with two conflicting costs per edge.
  • Multi-Objective Multi-Dimensional Knapsack Problem (MOMDKP): Selecting items (32 items total) to maximize two value objectives while staying within multiple capacity constraints.

They generated synthetic datasets where features map to costs through non-linear functions, adding varying levels of noise ($\epsilon = 0, 0.25, 0.5$) to test robustness.

Key Insights and Ideas

  • Geometry Matters: Standard SPO+ is "blind" to non-convex parts of the Pareto front because it always targets a vertex on the convex hull. By picking a target directly from the true Pareto set, ParetoSPO provides a much richer learning signal.
  • Efficiency through Pre-computation: Multi-objective solvers are notoriously slow. By solving the optimization problems offline during data preparation, the authors keep the actual training loop fast, as it only requires a standard single-objective solver.
  • The "Aha" Moment: Even in zero-noise settings, standard SPO+ struggles because of the non-convexity of combinatorial problems. ParetoSPO's ability to "see" the whole frontier gives it a fundamental advantage that isn't just about handling noise, but about understanding the problem's structure.

Key Results

The performance was measured using Hypervolume Regret—the percentage of the optimal trade-off space the model fails to capture. Lower is better.

  • Consistent Superiority: ParetoSPO outperformed both standard MSE (two-stage) and scalarized SPO+ baselines across all noise levels.
  • Shortest Path (MOSPP): At zero noise, ParetoSPO achieved a regret of 0.70%, compared to 0.98% for scalarized SPO+ and 1.15% for MSE.
  • Knapsack (MOMDKP): The gap was even wider here. At zero noise, ParetoSPO had 8.36% regret, while scalarized SPO+ trailed at 10.96% and MSE at 12.65%.
  • Robustness: As noise increased to $\epsilon=0.5$, ParetoSPO maintained its lead, showing it learns more robust cost representations.

Limitations and Future Work

  • Scalability: The "model committee" approach requires training a separate model for every discrete preference. This doesn't scale well if there are thousands of different user preferences.
  • Generalization: Currently, an expert model only knows about its specific preference. It cannot generalize to a new, unseen trade-off requested by a user at runtime.
  • Future Directions: The authors suggest developing a single preference-conditioned model that takes both features and a preference vector as input. This would allow a single model to generalize across the entire Pareto Frontier, combining the accuracy of ParetoSPO with the flexibility of a unified architecture.

Summary updated

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.
BibTeX
@misc{dhakal2026pareto,
  author = {Aabhash Dhakal and Tim Lachner},
  title = {{Pareto-Informed Smart "Predict, then Optimize" for Multi-Objective Combinatorial Problems}},
  year = {2026},
  eprint = {2611.23076},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.23076},
}
Figure