Metraipolis › archive › dc_dd2cfc124797
B$^3$-PWL: GPU-Batched Branch-and-Bound for Piecewise-Linear Optimization with SOS2 Constraints — arXiv:2608.28988
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.28988
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T08:19:03.898Z
- SHA-256 of the archived text
12a446e397c5eff3005ae48424a002d1566d67657570ef9e5b637b188458464f- Stable URL of this page
https://metraipolis.com/documento/dc_dd2cfc124797
How to cite
B$^3$-PWL: GPU-Batched Branch-and-Bound for Piecewise-Linear Optimization with SOS2 Constraints — arXiv:2608.28988 — arXiv (en), https://arxiv.org/abs/2608.28988 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dd2cfc124797 (Metraipolis archive dc_dd2cfc124797, sha256 12a446e397c5eff3005ae48424a002d1566d67657570ef9e5b637b188458464f)
BibTeX
@misc{dcdd2cfc124797,
title = {B$^3$-PWL: GPU-Batched Branch-and-Bound for Piecewise-Linear Optimization with SOS2 Constraints — arXiv:2608.28988},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.28988},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dd2cfc124797; sha256 12a446e397c5eff3005ae48424a002d1566d67657570ef9e5b637b188458464f},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.28988. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Piecewise-linear (PWL) optimization problems arise in many mixed-integer programming (MIP) optimization applications, including portfolio optimization, workforce scheduling, and resource allocation. But solving them to global optimality remains computationally expensive because branch-and-bound repeatedly solves LP relaxation subproblems. Existing solvers are largely CPU-centric, leaving the scalability of modern GPUs underutilized. Few prior GPU-accelerated branch-and-bound either targets neural network which is not suitable for general PWL optimization, or accelerates only auxiliary subroutines such as strong branching heuristics within CPU-centric MIP solvers. To bridge this gap, we propose B$^3$-PWL, a GPU-centric batched branch-and-bound framework for piecewise-linear optimization with Special Ordered Set of type 2 (SOS2) constraints. Our method solves batches of LP relaxation subproblems concurrently on the GPU using a first-order primal-dual solver, enabled by a specialized batched block-tiled sparse matrix kernel. To complement bound computation, we further introduce a unified feasibility search module that combines an SOS2 repair primal heuristic with a batched feasibility pump to rapidly obtain feasible incumbents and improve pruning efficiency. On a benchmark of 43 PWL-MIP instances, B$^3$-PWL achieves a 9.25x geometric-mean speedup over NVIDIA cuOpt while reaching high-quality feasible incumbents on every tested instance. On a public valve-point unit-commitment benchmark, it further outperforms NVIDIA cuOpt and the open-source CPU solvers SCIP and HiGHS, demonstrating the potential of first-order LP methods as the central engine of GPU-accelerated branch-and-bound. Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-09-01 in cs.DC). Categorie arXiv: Optimization and Control (math.OC) ; Distributed, Parallel, and Cluster Computing (cs.DC). Pagina del lavoro: https://arxiv.org/abs/2608.28988 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-17T08:07:11.122Z dalla pagina https://arxiv.org/catchup/cs.DC/2026-09-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).