Source-linked AI summary
B$^3$-PWL: GPU-Batched Branch-and-Bound for Piecewise-Linear Optimization with SOS2 Constraints
Yilin Guan, Shuqing Luo, Pingzhi Li, Tianlong Chen, Kaidi Xu
TL;DR
PWL mixed-integer optimization is costly because branch-and-bound repeatedly solves LP relaxations, while existing GPU approaches do not make those solves the core of general PWL search. B3-PWL batches SOS2-constrained node LP relaxations on GPUs and integrates SOS2 repair with feasibility pumping, achieving a 9.25× geometric-mean speedup over cuOpt on 43 instances. The approach demonstrates GPU-first-order LP branch-and-bound potential, but final dual-gap certification remains a limitation and broader solver machinery is absent.
Problem
PWL-MIP global optimization repeatedly solves LP relaxations, while conventional CPU-centric methods leave GPU parallelism underused and prior GPU approaches do not target general PWL branch-and-bound.
Method
B3-PWL batches node LP relaxations on GPUs with a first-order solver and specialized sparse kernel, combining SOS2 repair with a batched feasibility pump for incumbent search.
Results
9.25× geometric-mean speedup over NVIDIA cuOpt was achieved on 43 PWL-MIP instances while reaching high-quality incumbents on every tested instance.
Takeaways & Limitations
The results support using batched first-order LP methods as the central engine of GPU-accelerated branch-and-bound for PWL optimization.
Takeaways & Limitations
First-order convergence makes final dual-bound certification slow, and some large resource-allocation instances did not close the 1% MIP gap within 300 s despite early near-optimal incumbents.
Abstract
from arXiv · showhide
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.
1 Introduction
PWL optimization is broadly useful but difficult to solve globally because MIP branch-and-bound repeatedly solves LP relaxations that conventional CPU methods parallelize poorly. B3-PWL makes batched GPU LP solving the core of branch-and-bound and adds SOS2-aware feasibility search.
- PWL formulations support portfolio optimization, workforce scheduling, and resource allocation while approximating nonlinear relationships within MIP frameworks.
- Exponential combinatorial growth and sequential simplex-based LP reoptimization make global optimization computationally expensive and difficult to parallelize.
- Prior GPU branch-and-bound work targets neural-network verification or accelerates auxiliary MIP procedures while leaving core node LP solves on CPUs.
- B3-PWL batches node LP relaxations on GPUs using a modified first-order solver and a block-tiled sparse kernel for heterogeneous matrices.
- Its unified feasibility module combines SOS2 repair and a batched feasibility pump to obtain incumbents for more effective pruning.
- 9.25× geometric-mean speedup is reported on 43 instances over cuOpt, alongside higher-quality solutions and further wins on a valve-point unit-commitment benchmark.
2 Related Work
Prior work establishes GPU acceleration for first-order LP methods and branch-and-bound, but general exact LP-based MIP branch-and-bound remains less GPU-integrated than neural-network verification.
- First-order LP methods formulate linear programs as saddle-point problems and solve them with PDHG iterations suited to accelerator execution.
- cuPDLP and cuPDLPx move sparse LP computations to GPUs and improve performance through hardware-aware and algorithm-specific enhancements.
- GPU branch-and-bound is well established in neural-network verification, whereas traditional MIP use remains more limited within exact LP-based search.
3 Preliminaries
The SOS2 formulation represents each PWL function through convex-combination weights restricted to adjacent breakpoints. Branch-and-bound relaxes these restrictions at nodes, uses LP bounds, and branches on unresolved breakpoint ranges.
- Each PWL function is defined over ordered breakpoints partitioning its domain into linear segments and represented using a λ-formulation with SOS2 constraints.
- The λ weights are nonnegative convex-combination weights, with at most two nonzero components at adjacent indices.
- SOS2 adjacency ensures each represented point lies on one PWL segment or exactly at a breakpoint.
- Branch-and-bound searches over exponentially many segment combinations by recursively restricting each function’s admissible breakpoint range.
- The workflow alternates CPU search-tree management with GPU batched LP solving until the active queue empties or the global gap closes.
- Dropping SOS2 constraints gives each node an LP lower bound; nodes are fathomed, accepted, or branched according to feasibility, incumbent comparison, and SOS2 satisfaction.
4 Method
B3-PWL organizes branch-and-bound on the CPU while solving heterogeneous node LP batches on the GPU with cuPDLPx and B2-SpMV. SOS2 repair and feasibility-pump objectives turn LP outputs into feasible incumbents that tighten pruning bounds.
- End-to-end workflow: The CPU assembles active-node batches, the GPU solves them, and CPU postprocessing updates bounds, prunes nodes, and branches unresolved subproblems.
- Heterogeneous batched LP engine: Batched PDHG maintains task-specific stepsizes, projections, restart states, and stopping criteria while executing the inner operator in one GPU dispatch.
- Heterogeneous batched LP engine: Node LP relaxations differ after presolve in dimensions and sparsity, creating a ragged heterogeneous matrix batch.
- B2-SpMV: B2-SpMV partitions matrices into tiles, removes zero tiles, packs nonzero tiles contiguously, and uses index maps for sparse computation and coalesced access.
- Unified feasibility search: SOS2 repair identifies each active segment from the LP solution, resets λ weights to its endpoint interpolation, and verifies original constraints before accepting an incumbent.
- Unified feasibility search: When repair fails, feasibility-pump rounds modify the objective toward the repaired SOS2 target while retaining the original objective and sharing GPU batches with search tasks.
5 Experiments
The experiments evaluate B3-PWL on synthetic PWL-MIP instances and a public valve-point unit-commitment benchmark using solution quality, solve speed, incumbent timing, feasibility-search ablations, and GPU-kernel profiling. B3-PWL consistently obtains feasible, high-quality solutions and outperforms cuOpt and open-source CPU solvers across the reported benchmarks, while GPU-side LP solving dominates runtime.
- Experimental setup: The evaluation covers 43 synthetic PWL-MIP instances and a public valve-point unit-commitment benchmark, with comparisons focused on solution quality and solve speed.The synthetic suite spans portfolio optimization, workforce scheduling, and resource allocation; the public benchmark uses real-world cost data.
- Solution quality: B3-PWL reaches Eff-Opt on all 43 instances versus 30/43 for cuOpt, and matches the Gurobi reference objective on 37/43 versus 9/43.Eff-Opt denotes a feasible incumbent within 1% of the Gurobi reference objective.
- Solve speed: 9.25× aggregate speedup: B3-PWL achieves a 7.0-second shifted geometric-mean runtime versus 55.0 seconds for cuOpt and wins on 38/43 instances.The comparison uses the reported Geo-Spd metric and the stated win criterion based on Eff-Opt attainment and termination time.
- Comparison with CPU solvers: B3-PWL reaches Eff-Opt on all 43 instances and has lower aggregate runtime than SCIP and HiGHS, positioning it as a proof of concept for GPU-centric branch-and-bound.Gurobi remains fastest on this benchmark, while B3-PWL outperforms the open-source CPU solvers in the reported comparison.
- Time to best incumbent: 12.28× geometric-mean TTB speedup over cuOpt is reported overall, with B3-PWL achieving strictly lower time to its best incumbent on every instance.The shifted geometric means are 4.22 seconds for B3-PWL and 45.77 seconds for cuOpt.
- Ablations and profiling: SOS2 repair recovers feasibility on all 43 instances, while feasibility-pump speedups are 2.18× on portfolio, 2.61× on workforce, and 1.00× on resource allocation.Without repair, no feasible incumbent is recorded; batched LP solving consumes over 85% of B&B time, versus under 15% for CPU-side operations.
6 Conclusion
B3-PWL is a GPU-accelerated framework that makes batched LP relaxations the central engine of branch-and-bound for PWL mixed-integer optimization. It achieves substantial benchmark speedups while supporting exact optimization and broader accessibility, with downstream effects depending on application.
- 9.25× geometric-mean speedup over NVIDIA cuOpt was achieved on a 43-instance benchmark, with high-quality incumbents on every tested instance.
- B3-PWL solves piecewise-linear mixed-integer optimization problems to global optimality using GPU acceleration.
- Faster, more accessible exact solvers can reduce computational and energy costs and lower access barriers for smaller organizations and academic users.
- Downstream impact depends on the application rather than on risks specific to the framework.
B Limitations and Future Work
B3-PWL demonstrates GPU-batched first-order LP solving as the central branch-and-bound engine, but its current design remains limited by certification speed, absent warm starts, and basic solver machinery.
- Limitations: First-order convergence makes dual-bound certification slow, with some largest resource-allocation instances failing to close the 1% MIP gap within 300 seconds despite early near-optimal incumbents.The authors suggest simplex- or interior-point-based crossover during high-accuracy phases.
- Limitations: B3-PWL re-solves related child LPs essentially from scratch because PDHG lacks a simplex basis and current batched solves do not warm-start sibling subproblems.Transferring iterate scaling, primal weights, or partial restart history is identified as an open direction.
- Limitations: The current pipeline uses simple branching and omits sophisticated branching, cutting planes, bound tightening, and advanced presolve strategies.GPU-compatible cuts and bound-tightening routines could improve pruning and reduce certification time.
- Core framework: B3-PWL uses cuPDLPx to solve multiple node LP relaxations concurrently through GPU-batched primal-dual iterations.cuPDLPx is based on PDHG, with GPU-suitable matrix-vector operations and several convergence enhancements.
- Solver enhancements: cuPDLPx regulates primal weight with a PID controller and uses adaptive restarts plus a constant stepsize to improve convergence and GPU parallel efficiency.The primal weight responds to logarithmic primal-dual progress, while restarts reset the anchor when progress conditions are met.
D Numerical Robustness and Stopping-Criterion Sensitivity
Numerical checks show stable incumbents and valid lower bounds across tighter solver tolerances, while stricter global MIP-gap targets mainly increase certification cost.
- Incumbent feasibility and stability: Every tested tolerance setting returns an incumbent within 1% of the Gurobi reference objective across all 43 instances.The comparison uses PDLP feasibility and optimality tolerances of 10^-4, 10^-5, and 10^-6.
- Incumbent feasibility and stability: 0.0213% is the maximum change in the solver-reported incumbent objective under tighter 10^-5 and 10^-6 tolerances relative to 10^-4.
- Incumbent validation: 129 independently validated incumbent patterns all yield feasible solutions, with a maximum constraint violation of 2.91 × 10^-11.HiGHS re-solves the continuous LP after fixing each integer/SOS2 pattern at a 10^-9 feasibility tolerance.
- Lower-bound stability and validity: Final lower bounds remain valid for all 43 instances under every tighter tolerance and change only slightly relative to the 10^-4 baseline.Table 8 reports instance-wise relative lower-bound shifts.
- Stopping-criterion sensitivity: 12 runs reach the 300-second limit at a 0.1% target gap, compared with 3 runs at 1%, while solution-quality conclusions remain stable.Tighter stopping criteria primarily increase the computation required for dual-bound certification.
E Per-Instance Detailed Results
Per-instance results are reported for every canonical PWL instance, comparing PWL-BaB and cuOpt with a separately certified Gurobi reference.
- Per-instance comparisons: Tables 10–12 report per-instance wall-clock time and returned objective for PWL-BaB and cuOpt alongside Gurobi certified optima.Gurobi runtime is omitted because it is not directly comparable to the GPU-accelerated PWL and cuOpt times.
- Reporting conventions: The detailed results mark 300-second budget exhaustion as TO and missing feasible incumbents with an em dash.Each instance is tagged by the number of PWL functions and its seed.
F Implementation Details
The implementation maintains GPU utilization by expanding shallow search trees when batches are underfilled and adapting batch size to available memory.
- Multi-level branching for batch filling: When the queue contains fewer than 0.9B nodes, multi-level branching expands each seed into up to 2^d_split leaves to keep GPU batches saturated.Seeds are expanded recursively with BFS-style branching and the existing branching heuristic.
- Benchmark organization: Portfolio results are presented in Table 10 for 18 instances, while workforce results are presented in Table 11 for 9 instances.
- Adaptive batch sizing: Batch size grows as B ← min(2B, floor(γB)) using γ = M_target/M_used and M_target = 0.85 · M_total.The update uses available GPU memory and a minimum increase threshold to avoid out-of-memory failures.
G Benchmark Details
The benchmark suite is designed to characterize GPU batched branch-and-bound across controlled PWL structures rather than claim broad industrial representativeness. It covers three application families with systematically varied dimensions and complementary structural regimes.
- Benchmark motivation: The suite lacks a broadly adopted MIPLIB-like benchmark for large-scale nonconvex PWL optimization preserving native SOS2 structure.MIPLIB 2017 permits SOS and PWL constraints, but its submitted instances did not use them.
- Benchmark construction: Three application classes—portfolio optimization, workforce scheduling, and resource allocation—form the controlled benchmark suite.Their generators support systematic variation of LP size, breakpoint count, sparsity, and SOS2 density.
- Reported results: Table 12 reports per-instance results for 16 resource-allocation instances.
- Benchmark construction: Root-trivial instances are removed so experiments evaluate batched branch-and-bound rather than primarily a single LP relaxation.Synthetic generation also keeps instance difficulty within a range that distinguishes the framework from CPU simplex-based solvers.
- Structural regimes: Portfolio, workforce, and resource-allocation families exercise dense, grid-coupled, and block-structured SOS2 regimes, respectively.The families differ in how local PWL structures interact with global constraints.
G.1 Portfolio Benchmark with Piecewise-Linear Transaction Costs
The benchmark models portfolio allocation with separable PWL transaction costs, SOS2 representations, and global financial coupling constraints. Its controlled construction creates non-root-trivial instances whose many local SOS2 structures scale with asset and breakpoint counts.
- Problem formulation: The portfolio model allocates capital across assets while balancing expected return against separable transaction-cost penalties.It includes a global budget, sparse factor-risk limits, and sector exposure caps.
- Problem formulation: The three coupling-constraint classes are total capital, factor exposure, and sector allocation limits.Capital is bounded by budget C, factor exposures by risk budgets, and sector allocations by sector-specific caps.
- PWL encoding: Each asset’s transaction cost is represented by a univariate PWL curve with convex-combination variables and an SOS2 constraint.At most two adjacent breakpoints can be active, forcing the holding-cost pair onto the PWL graph.
- Data generation: The benchmark deliberately uses tight holding boxes so no single SOS2 segment is admissible at the LP relaxation.This forces branch-and-bound to explore multiple segment combinations instead of terminating at the root LP.
- Problem size: N(J + 2) variables represent N holdings, N cost variables, and NJ SOS2 weights.The formulation adds 1 + F + Ssec global coupling constraints and 3N local PWL constraints.
- Related benchmark formulations: The workforce and resource-allocation benchmarks extend the same PWL-SOS2 pattern to worker-period costs and block-angular production planning.Workforce instances use WP(J + 2) variables, while resource allocation embeds PWL costs in sparse local/global resource structures.
- Solver behavior: Resource allocation can require deeper search because local PWL branches provide limited global tightening, while larger node LPs reduce GPU batch size.These properties weaken pruning and make branching quality more important.