CS Paper Radar

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

Aabhash Dhakal, Tim Lachner

cs.LG ·submitted 2026-11-17 17:03 UTC · v2
published

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.

Comment
Accepted at the Multi-Objective Decision Making (MODeM) Workshop, ECAI 2025

Closest papers

Nearest neighbours by meaning across the whole index.

In-Context Preference-Conditioned Pareto Set Learning from Limited Offline Data

cs.AI ·2026-10-15 ·Yiming Yao, Liang Zhao, Qingfu Zhang
similarity 0.67
Abstract

Multi-objective optimization involves diverse preferences over conflicting objectives. Rather than returning a finite set of trade-off solutions, preference-conditioned Pareto set learning seeks to map a specified preference directly to a corresponding Pareto optimal solution. Yet in many real-world scenarios, optimization must proceed offline without further objective evaluations, leaving only a limited static dataset that sparsely covers the decision and objective spaces. Existing methods either optimize separately for each preference or train a problem-specific Pareto solution model, requiring repeated search across preferences or repeated training across problems. We introduce in-context preference-conditioned Pareto set learning (ICPSL), a framework that amortizes both preference-wise solution search and problem-specific model construction. ICPSL pretrains a foundation-style hypernetwork on a large and diverse set of synthetic prior data. Given the offline observations of an unseen problem, the pretrained hypernetwork learns to generate a problem-specific, preference-conditioned Pareto solution model in a single forward pass. The generated model can then be reused to predict solutions for arbitrary preferences without problem-specific training or preference-wise search. Experiments on synthetic and real-world problems show that ICPSL produces high-quality Pareto solutions while providing substantial speedups in problem-specific solution-model construction.

0.17

Decision-Driven Regularization: A Blended Model for Learning and Optimization

cs.LG math.OC ·2026-08-15 ·Gar Goei Loke, Qinshen Tang, Yangge Xiao, Xun Zhang
published similarity 0.66
Abstract · 42 pages (including appendix), 7 figures in main, journal paper

In contextual optimization, the decision-maker seeks optimal decisions to minimize a cost function, that varies based on observed features. This context is common in many business applications ranging from on-demand delivery and retail operations to portfolio optimization and inventory management. In this paper, we study the learning and optimization approach, which first learns how outcomes result from the features, and then selects optimal decisions based on these outcomes. We focus on the integrated learning and optimization literature, and identify that a lack of control for prediction accuracy can lead to overfitting and a loss of decision effectiveness against simple separate learning and optimization models. Instead, we propose a bi-objective formulation that balances prediction accuracy and cost minimization, termed decision-driven regularization. It also addresses ambiguity in the definition of the cost function via a surrogate that depends on a new hyperparameter. We additionally show that alternative perspectives for formulating the problem, namely robust optimization and regret minimization, lead to models that are closely related to our proposed model. As a consequence, our framework generalizes models such as SPO+. Our model is shown to be numerically superior to other benchmarks, such as OLS, Random Forest, XGBoost, SPO+, Perturbation Gradient, and Learning and Rank, in our synthetic studies.

0.56

Learning Pareto Stationary Fronts via Single-Pass Backpropagation

cs.LG ·2026-10-05 ·Elina Rojin Celik, Marcos Medeiros Raimundo, Isabel Valera
top venue similarity 0.63
Abstract · 30 pages. Accepted at NeurIPS 2026. Camera-ready version

We propose MOSEL (Multi-Objective Stackelberg Efficient Learning), a framework for a posteriori multi-objective optimization (MOO) in deep neural networks that recovers a full front of Pareto stationary solutions at the computational cost of standard single-objective training. MOSEL reformulates the problem as a bilevel optimization problem that leverages network modularity to decouple representation learning from objective-preference alignment. Casting the bilevel optimization problem as a Stackelberg game enables solving the original a posteriori MOO problem in a single forward-backward pass. As a result, MOSEL matches the time and memory efficiency of standard single-objective training while enabling scalable Pareto stationary front learning. Empirically, MOSEL uncovers diverse and optimal Pareto frontiers in strongly conflicting settings (e.g., fairness-accuracy). Remarkably, even in weakly conflicting regimes such as multi-task learning, it consistently converges to solutions closer to the utopia point, outperforming both standard single-objective training and specialized multi-task learning methods. These results highlight the broader potential of a posteriori MOO learning as a pathway to efficiently learn more diverse and robust representations, ultimately improving generalization.

0.36

Evolving Neural Solvers for Multi-objective Combinatorial Optimization

cs.NE ·2026-11-17 ·Ya-Hui Jia, Le-Xin Wen, Yang Wang, Wei-Neng Chen, Yi Mei
similarity 0.63
Abstract · 17 pages, 3 figures, including appendices

Multi-objective combinatorial optimization (MOCO) seeks high-quality solutions that represent different trade-offs among conflicting objectives. Existing neural methods typically train a dedicated model for each preference or condition a single model on different preferences. Training dedicated models becomes more costly as the number of preferences increases, while a shared model can produce duplicate solutions for different preferences, limiting the benefit of denser preference queries. We propose the Evolving Neural Solver (ENS), which trains only a small set of preference-specific models and takes advantage of evolutionary computation to evolve them into a diverse collection of solvers for better solution quality and Pareto front coverage. ENS first trains a model at an estimated knee-point preference to target a balanced compromise, then obtains the remaining initial models through parameter transfer toward the extremes, so as to preliminarily approximate the Pareto front. It then evolves these models to find more candidates that can generate non-dominated solutions through evolution strategies. Experimental results on classic MOCO problems show that ENS outperforms state-of-the-art neural MOCO methods in terms of hypervolume in most evaluated settings.

0.17

MOBO-CAPS: Multi-Objective Bayesian Optimization with Cardinality-Aware Pareto Selection

cs.LG ·2026-11-15 ·Hanyang Wang, Juergen Branke, Matthias Poloczek
theory similarity 0.62
Abstract

Multi-objective Bayesian optimization (MOBO) traditionally aims to approximate the entire Pareto front, but, due to resource constraints, real-world deployment is often limited to testing a small, representative subset of solutions. Hence current methods first approximate the full front before selecting solutions, potentially wasting costly evaluations. We formalize this problem as Multi-objective Bayesian Optimization with Cardinality-aware Pareto Selection (MOBO-CAPS), where the goal is to identify a set of exactly M solutions with high hypervolume. We propose two practical cardinality-aware acquisition strategies: REHVI, a replacement-aware approximation to expected hypervolume improvement, and CHO-UCB, which constructs an optimistic M-point set by optimizing a collective UCB-based hypervolume objective. We prove a sublinear simple regret bound for the batched version of CHO-UCB, and empirically show that cardinality-aware acquisition design improves over standard MOBO followed by post-hoc subset selection across nine benchmarks.

0.11

Solver-Free Decision-Focused Learning via Neural Optimization Layers for Edge Selection

cs.LG math.OC ·2026-11-06 ·Xinda Zheng, Frits de Nijs, Edward Lam
similarity 0.62
Abstract

Decision-focused learning trains prediction models to improve downstream decisions, but many methods require costly solver calls or optimal-solution labels. We propose a solver-free decision-focused learning framework for NP-hard edge-selection problems with uncertain parameters in the objective, the constraints, or both. A neural optimization layer is first trained without solution labels, using problem objectives and constraint penalties. Graph-informed edge scoring and iterative refinement encourage concentrated and structurally consistent continuous decisions. The layer is then frozen, and a prediction model is trained through its continuous output using a problem-specific loss evaluated under observed parameters. At deployment, the predictor, optimization layer, and a lightweight decoder produce decisions without solving the original NP-hard problem. Experiments on the asymmetric traveling salesperson and endpoint-free orienteering problems show consistently better decision quality than prediction-focused learning and improvements over most evaluated decision-focused baselines. Our framework requires less training time than the evaluated decision-focused baselines, even when optimization-layer pretraining is included. Neural deployment also produces decisions faster than solver-based deployment, offering a better quality-efficiency trade-off. The layer also reduces training cost in existing decision-focused methods when used as an approximate optimization oracle.

0.48

A Better Spur Should Start From Each Objective

cs.AI cs.LG ·2026-09-08 ·Shanwen Mao, Hao Zhang, Guangtao nie, Zhiheng Li, Huimu Wang +2 more
top venue similarity 0.61
Abstract · Accepted to EMNLP 2026

Real-world Multi-Objective Reinforcement Learning (MORL) often suffers from sparse rewards, reward conflicts, and late-stage reward tug-of-war, causing traditional linear scalarization to experience severe metric oscillations. To address optimization conflicts among multiple objectives in real-world deployment scenarios, we propose Multi-Marginal Preference Optimization (MMPO), a fine-grained framework that intervenes at the data, gradient, and constraint levels rather than relying on coarse-grained global scalarization. Specifically, MMPO performs exposure debiasing to mitigate sparse and biased rewards, applies priority-aware orthogonal projection to decouple conflicting gradients, and introduces self-prompted gradient constraints to prevent dominant objectives from overwhelming weaker ones. Experiments on real-world e-commerce datasets show that MMPO improves training stability and consistently achieves better performance across conflicting metrics. Moreover, it generalizes robustly to broader tasks such as ToolRL and code generation, demonstrating its effectiveness as a practical paradigm for multi-objective alignment.

0.58

Learning Where to Steer: Noise-Space Geometry for Efficient Offline Multi-Objective Optimization with Generative Models

cs.LG ·2026-09-30 ·Yuan Lu, Esha Singh, Yi-An Ma, Yusu Wang
theory similarity 0.61
Abstract · 65 pages, including appendices

Offline multi-objective optimization (MOO) seeks solutions with better objective trade-offs using only a fixed dataset, without querying the objectives. Diffusion models trained on such data have emerged as a promising approach, but their samples are not inherently better than the data and must be steered toward the Pareto front. Existing methods guide or condition every sampling step. We instead act on the initial noise and leave the sampling process unchanged. Across Off-MOO-Bench, we observe that the objectives, as functions of the noise, are sensitive to only a few directions. We estimate these directions once per task via a Recursive Feature Machine using function values alone, and a small cache serves every trade-off, so each candidate costs one noise displacement and one ODE solve. We prove that this displacement increases the learned scalarized objective in expectation, and that sweeping trade-offs recovers the flow's attainable front up to proxy and steering errors. With additional guidance, for which we introduce novel data-adaptive and Pareto-aware operators, our method attains the best average hypervolume rank among generative methods on 47 tasks, at comparable or lower sampling cost. Steering alone outranks the best prior generative method at a fraction of its sampling cost.

0.51