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).