GPU Parallel Pareto Local Search for Multi-objective QUBO
Abstract
We revisit Pareto Local Search (PLS) for multi-objective quadratic unconstrained binary optimization (QUBO) problems. Multi-objective QUBO formulations have gained increasing attention as a universal modeling method and natural input for quantum optimization. While exact methods exist, their unconstrained binary structure makes them well-suited for heuristics such as PLS. At the same time, GPUs offer a powerful classical alternative to quantum-inspired optimization. We develop an efficient GPU-based parallel implementation of PLS for multi-objective QUBO problems. Our approach combines coarse-grained and fine-grained parallelization. On the coarse-grained level, an initial set of supported solutions is generated using weighted-sum optimization, from which multiple PLS processes are started in parallel. At the fine-grained level, neighborhood exploration is parallelized on the GPU by simultaneously evaluating binary-flip candidate solutions across all objectives. Non-dominated solutions are maintained using an ND-Tree data structure to support efficient Pareto updates. The implementation combines several known PLS techniques within a unified CPU/GPU hybrid architecture. We describe the algorithmic components, the GPU-specific design decisions, and report results from a computational study evaluating the effectiveness of the proposed approach.
Related
- Beyond Scalar Leaderboards: Adaptive Sampling for Pareto Frontier Identification in Multi-Objective LLM Arenas
- Pareto-Guided Leader Selection in the Mountain Gazelle Optimizer: A Controlled Multi-Objective Study
- MPFA: A Pareto Front Approximation Method for Riemannian Bi-objective Optimization
- Noether's Second Theorem and the Pareto Front Structure in Multi-Criteria Variational Problems
- textsc{Athanor}: local search over abstract constraint specifications
BibTeX
@misc{riedmuller2026parallel,
title = {{GPU Parallel Pareto Local Search for Multi-objective QUBO}},
author = {Stephanie Riedmüller and Thorsten Koch},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.21890},
eprint = {2610.21890},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.21890},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - GPU Parallel Pareto Local Search for Multi-objective QUBO
AU - Stephanie Riedmüller
AU - Thorsten Koch
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.21890
UR - https://arxiv.org/abs/2610.21890
AB - We revisit Pareto Local Search (PLS) for multi-objective quadratic unconstrained binary optimization (QUBO) problems. Multi-objective QUBO formulations have gained increasing attention as a universal modeling method and natural input for quantum optimization. While exact methods exist, their unconstrained binary structure makes them well-suited for heuristics such as PLS. At the same time, GPUs offer a powerful classical alternative to quantum-inspired optimization. We develop an efficient GPU-based parallel implementation of PLS for multi-objective QUBO problems. Our approach combines coarse-grained and fine-grained parallelization. On the coarse-grained level, an initial set of supported solutions is generated using weighted-sum optimization, from which multiple PLS processes are started in parallel. At the fine-grained level, neighborhood exploration is parallelized on the GPU by simultaneously evaluating binary-flip candidate solutions across all objectives. Non-dominated solutions are maintained using an ND-Tree data structure to support efficient Pareto updates. The implementation combines several known PLS techniques within a unified CPU/GPU hybrid architecture. We describe the algorithmic components, the GPU-specific design decisions, and report results from a computational study evaluating the effectiveness of the proposed approach.
ER -