B$^3$-PWL: GPU-Batched Branch-and-Bound for Piecewise-Linear Optimization with SOS2 Constraints

A GPU-centric batched branch-and-bound framework that solves LP relaxations concurrently with a first-order primal-dual method, achieving a 9.25x geometric-mean speedup over NVIDIA cuOpt on PWL-MIP benchmarks.

Yilin Guan; Shuqing Luo; Pingzhi Li; Tianlong Chen; Kaidi Xu· 2026· DOI 10.48550/arXiv.2608.28988

The core problem

Piecewise-linear (PWL) optimization problems arise in many mixed-integer programming (MIP) applications, including portfolio optimization, workforce scheduling, and resource allocation. Solving these problems 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. Prior GPU-accelerated branch-and-bound approaches either target neural networks, which are not suitable for general PWL optimization, or accelerate only auxiliary subroutines such as strong branching heuristics within CPU-centric MIP solvers. This work bridges that gap by proposing B^{3} -PWL, a GPU-centric batched branch-and-bound framework for piecewise-linear optimization with Special Ordered Set of type 2 (SOS2) constraints. The central idea is to solve 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, the authors introduce a unified feasibility search module that combines an SOS2 repair primal heuristic with

Innovation

The authors evaluate B^{3} -PWL on a benchmark of 43 PWL-MIP instances. The method 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, B^{3} -PWL further outperforms NVIDIA cuOpt and the open-source CPU solvers SCIP and HiGHS. These results demonstrate the potential of first-order LP methods as the central engine of GPU-accelerated branch-and-bound. The speedup is attributed to the concurrent solution of LP relaxations on the GPU and the effectiveness of the unified feasibility search module in finding feasible incumbents quickly, which improves pruning efficiency.

Piecewise-linear (PWL) optimization problems arise in many mixed-integer programming (MIP) applications, including portfolio optimization, workforce scheduling, and resource allocation. Solving these problems 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. Prior GPU-accelerated branch-and-bound approaches either target neural networks, which are not suitable for general PWL optimization, or accelerate only auxiliary subroutines such as strong branching heuristics within CPU-centric MIP solvers. This work bridges that gap by proposing B^{3} -PWL, a GPU-centric batched branch-and-bound framework for piecewise-linear optimization with Special Ordered Set of type 2 (SOS2) constraints. The central idea is to solve 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, the authors 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.

B^{3} -PWL is a GPU-centric batched branch-and-bound framework designed for PWL optimization with SOS2 constraints. Its architecture consists of three main components: (1) a batched LP relaxation solver, (2) a unified feasibility search module, and (3) a branch-and-bound orchestration layer that manages the search tree on the GPU.

Why it matters

The results indicate that GPU-centric batched branch-and-bound with first-order LP methods can significantly accelerate PWL optimization with SOS2 constraints. The 9.25x geometric-mean speedup over NVIDIA cuOpt is notable because cuOpt is a state-of-the-art GPU-accelerated solver. The approach also outperforms established CPU solvers SCIP and HiGHS on the valve-point unit-commitment benchmark, suggesting that the benefits extend beyond a single problem class. The key innovation is the use of a first-order primal-dual solver for LP relaxations, which avoids the sequential nature of simplex and the expensive linear algebra of interior-point methods. This makes it possible to solve many LP subproblems in parallel on the GPU. The batched block-tiled sparse matrix kernel is crucial for efficiency, as it handles the sparse structure of PWL formulations. The unified feasibility search module addresses the challenge of finding feasible incumbents in branch-and-bound. By combining an SOS2 repair heuristic with a batched feasibility pump, the method rapidly obtains feasible solutions that can be used to prune the search tree. This is particularly important for PWL problems where SOS2 constraints can make feasibility difficult. Limitations include the reliance on first-order methods, which may converge slowly for ill-conditioned problems, and the focus on SOS2 constraints, which may not cover all PWL formulations. Future work could explore extensions to other types of disjunctions and hybrid approaches that combine first-order and second-order methods. Overall, B^{3} -PWL represents a significant step toward fully GPU-accelerated MIP solvers for PWL optimization, with potential impact in portfolio optimization, workforce scheduling, and resource allocation.

Who should read this

CS practitioners and researchers

Opening member content…