Research map / Learning theory and algorithms / Combinatorial and search optimization
Preference-Driven Multi-Objective Combinatorial Optimization with Conditional Computation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes POCCO, a plug-and-play framework that adds a sparse conditional computation block to the decoder of neural MOCOP solvers (CNH, WE-CA) and trains them with a Bradley-Terry preference loss on average log-likelihoods instead of REINFORCE.
Problem
Neural deep RL solvers for multi-objective combinatorial optimization (MOCOPs) treat all weight-vector subproblems equally with a single capacity-limited model and rely on high-variance REINFORCE with scalarized rewards, limiting exploration and solution quality.
Approach
Route each subproblem through top-k sparse gating over several feed-forward experts plus a parameter-free identity expert in the decoder, and replace scalarized reward REINFORCE with pairwise preference learning where the winner/loser pair is trained via a BT likelihood over length-normalized log-probabilities.
Key results
- POCCO-W improves over WE-CA across all benchmarks; e.g., Bi-TSP100 HV 0.7055 vs 0.7034 for WE-CA (non-augmented).
- POCCO-C outperforms CNH in every case, e.g., Bi-TSP50 HV 0.6409 vs 0.6387.
- Preference learning converges faster: training WE-CA with PL for 100 epochs matches 200 epochs of REINFORCE.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add preference learning instead of REINFORCE (ablation) | WE-CA and POCCO-W · Bi-TSP100 | convergence speed | Helped |
| Add preference learning instead of REINFORCE (ablation) | POCCO-W · MOTSP20, MOTSP50, MOTSP100 | gradient variance: 0.054648 -> 0.000314; 0.474784 -> 0.000142; 10.124832 -> 0.000059 | Helped |
| Add a conditional computation block to WE-CA's decoder (ablation) | WE-CA · Bi-TSP100 | HV | Helped |
| Move CCO to the encoder, replacing its FF layer (ablation) | POCCO-W · Bi-TSP200 | HV | Hurt |
| Replace CCO with a standard MoE layer (ablation) | POCCO-W · Bi-TSP100 | HV | Helped |
| Replace CCO with a standard MoE layer (ablation) | POCCO-W · Bi-TSP200 | HV | Hurt |
| Replace the identity expert with an empty expert (ablation) | POCCO-W · Bi-TSP100 | HV | Helped |
| Replace the identity expert with an empty expert (ablation) | POCCO-W · Bi-TSP200 | HV | Helped |
| Use instance augmentation at inference (ablation) | POCCO · Bi-TSP20 | HV | Hurt |
| Use instance augmentation at inference (ablation) | POCCO · MOCOP benchmarks other than Bi-TSP20 | HV | Helped |
| Set preference signals for mutually non-dominated pairs to 0 (ablation) | POCCO · Bi-TSP instances | HV | Hurt |
| Add a CCO block to WE-CA (ablation) | WE-CA · Bi-TSP200 | HV | Helped |
Surprising findings
- Setting preference signals to zero for mutually non-dominated pairs (NDS) significantly degrades performance across Bi-TSP instances.
- POCCO with instance augmentation yields lower HV than its non-augmented counterpart on Bi-TSP20.
Limitations
- Limited capability for real-world MOCOPs with complex constraints
- Limited capability for large problem sizes
Experimental setup
Datasets: Bi-TSP Bi-CVRP Bi-KP Tri-TSP KroAB100 KroAB150 KroAB200
Benchmarks: Bi-TSP20 Bi-TSP50 Bi-TSP100 Bi-CVRP20 Bi-CVRP50 Bi-CVRP100 Bi-KP50 Bi-KP100 Bi-KP200 Tri-TSP20 Tri-TSP50 Tri-TSP100
Metrics: hypervolume gap to POCCO-W runtime
Baselines: PMOCO CNH WE-CA DRL-MOA MDRL EMNH MOEA/D NSGA-II MOGLS PPLS/D-C WS-LKH WS-DP
Builds on: CNH WE-CA POMO REINFORCE SimPO
Closest papers by meaning
- Preference Optimization for Combinatorial Optimization Problems (ICML 2025 · similarity 0.89)
- BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization (ICML 2025 · similarity 0.87)
- Graph-Supported Dynamic Algorithm Configuration for Multi-Objective Combinatorial Optimization (ICML 2025 · similarity 0.87)
- Preference Conditioned Multi-Objective Reinforcement Learning: Decomposed, Diversity-Driven Policy Optimization (NeurIPS 2026 · similarity 0.87)
- Improving Reward Model Generalization from Adversarial Process Enhanced Preferences (ICML 2025 · similarity 0.85)
- FERERO: A Flexible Framework for Preference-Guided Multi-Objective Learning (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.