Research map / Learning theory and algorithms / Combinatorial and search optimization
B$^3$-PWL: GPU-Batched Branch-and-Bound for Piecewise-Linear Optimization with SOS2 Constraints
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes B³-PWL, a GPU-centric batched branch-and-bound that solves batches of node LP relaxations with a batched cuPDLPx-style first-order solver (plus a block-tiled ragged SpMV kernel and an SOS2 repair + batched feasibility pump), reporting 9.25x geomean speedup over cuOpt on 43 synthetic PWL-MIP instances.
Problem
Solving piecewise-linear optimization problems with SOS2 constraints to global optimality via branch-and-bound is expensive, and existing solvers are CPU-centric; GPU acceleration of B&B so far targets neural network verification or auxiliary subroutines in MIP solvers.
Approach
Use batched first-order PDHG LP solves (cuPDLPx extended to heterogeneous ragged batches with a batched block-tiled SpMV) as the core node-LP engine of a GPU-resident B&B loop, combined with an SOS2 repair heuristic and a batched objective feasibility pump to find incumbents early.
Key results
- On 43 PWL-MIP instances, B³-PWL achieves 9.25x geometric-mean speedup over cuOpt (shifted geomean 7.0 s vs 55.0 s) and reaches Eff-Opt on 43/43 vs 30/43 for cuOpt.
- On the valve-point UC benchmark, B³-PWL is faster than SCIP (10.34x geomean) and HiGHS (5.13x) but slower than Gurobi (0.47x geomean ratio).
- The feasibility-search ablation shows no feasible incumbents without a heuristic on any of 43 instances; repair alone recovers 43/43, and adding FP gives 1.69x overall speedup.
Surprising findings
- Without an SOS2 repair step, PDHG solutions yield zero feasible incumbents on all 43 instances because interior iterates leave small nonzero SOS2 mass.
- Gurobi remains faster than B³-PWL on all benchmarks (shifted geomean 1.0 s vs 7.0 s), and B³-PWL is slower than Gurobi on the valve-point UC T=1 case by design of GPU setup overhead.
Limitations
- Slow dual-bound certification due to sublinear PDHG convergence; many runs spend most time closing the gap.
- No warm starting between sibling node LPs; each subproblem is solved essentially from scratch.
- Simple branching and no cutting planes; results are on synthetic benchmarks with limited industrial representativeness.
Experimental setup
Datasets: 43 synthetic PWL-MIP instances (portfolio, workforce, resource allocation) valve-point unit commitment benchmark (eld40/ucp40)
Benchmarks: 43 synthetic PWL-MIP instances valve-point unit commitment benchmark
Metrics: wall-clock time shifted geometric mean time geometric-mean speedup Eff-Opt Exact Match time to best incumbent relative MIP gap
Baselines: NVIDIA cuOpt Gurobi SCIP HiGHS
Builds on: cuPDLPx PDLP PDHG objective feasibility pump alpha-beta-CROWN
Closest papers by meaning
- Batched First-Order Methods for Parallel LP Solving in MIP (ICML 2026 · similarity 0.88)
- DOGE-Train: Discrete Optimization on GPU with End-to-End Training (AAAI 2024 · similarity 0.87)
- Predicting Lagrangian Multipliers for Mixed Integer Linear Programs (ICML 2024 · similarity 0.84)
- Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching (ICML 2024 · similarity 0.84)
- Deep Distributed Optimization for Large-Scale Quadratic Programming (ICLR 2025 · similarity 0.83)
- OptiBench Meets ReSocratic: Measure and Improve LLMs for Optimization Modeling (ICLR 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.