PreprintCC BY-NC-SA 4.0arXiv
A Parallel Heuristic for the Fixed Cardinality Binary Quadratic Program
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.
Related
- Polynomially Solvable Cases of the Quadratic Binary Optimization Problem with a Fixed Cardinality Constraint
- A Frank-Wolfe-based primal heuristic for quadratic mixed-integer optimization
- New binary optimal LCD codes using heuristic embedding
- On the Cardinality of Optimal Representations in the Binary-Source Information Bottleneck
- S-squareful values of binary quadratic forms
BibTeX
@misc{le2026parallel,
title = {{A Parallel Heuristic for the Fixed Cardinality Binary Quadratic Program}},
author = {Thi Thanh Tu Le and Thorsten Koch},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41546},
eprint = {2610.41546},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41546},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - A Parallel Heuristic for the Fixed Cardinality Binary Quadratic Program
AU - Thi Thanh Tu Le
AU - Thorsten Koch
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41546
UR - https://arxiv.org/abs/2610.41546
AB - 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.
ER -