Paperlane

no. 6 · Monday 2 November 2026

A Parallel Heuristic for the Fixed Cardinality Binary Quadratic Program

Thi Thanh Tu Le and Thorsten Koch

math.OC · 7 pp

Abstract

The Fixed Cardinality Binary Quadratic Program (FCBQP) is an optimization problem that requires a prescribed number of variables to take the value 1. We propose a parallel CPU-based heuristic that combines impact-based variable selection, tabu search, guided restarts, and a shared elite pool. Computational experiments on 342 benchmark instances from the maximum dispersion problem, k-clique problem, and minimum graph bisection problem show that the new algorithm is competitive and can reach best-known or reference values on instances with more than 20000 variables within one minute.

comments
7 pages, Proceedings for the Annual International Conference of the German Operations Research Society (GOR2026)
fields
Optimization and Control
pdf ↗ page arXiv:2610.41546 ↗