CS Paper Radar

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

cs.DC math.OC ·submitted 2026-08-29 01:48 UTC · v1
benchmarkcode/datahot direction

Abstract

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.

Comment
23 pages, 3 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Advancing Weighted Partial MaxSAT Solving via Differentiable GPU Guidance

cs.AI ·2026-11-11 ·Mingju Liu, Curie Kim, Steve Dai, Cunxi Yu
benchmark similarity 0.66
Abstract · 13 pages, 6 figures

We present a GPU-CPU hybrid framework for Weighted Partial MaxSAT (WPMAX-SAT) that complements state-of-the-art CPU solvers with differentiable GPU optimization. The GPU stage directly optimizes instance-specific categorical decision parameters without a training dataset or a pretrained predictive model. The central challenge in extending differentiable optimization to WPMAX-SAT is the hard/soft clause asymmetry: hard clauses represent inviolable feasibility constraints while soft clauses carry weights. We introduce a hierarchical differentiable loss that prioritizes hard clause satisfaction before optimizing the weighted soft objective, ensuring that GPU gradient descent leans towards the constraint structure of WPMAX-SAT. Our framework transforms the GPU-optimized variable logits to high-confidence assignments and transfers them to CPU solvers via two complementary modes: partial guidance, which injects the most confident perturbed partial variable assignments as soft clauses into $N$ parallel solver instances, and phase initialization, which guides the CDCL solver's internal branching polarity with the full GPU assignment as a warm start to preserve the problem's originality. We evaluate on all 229 instances of the MSE 2024 (most recent due to cancellation in 2025) anytime weighted benchmark with the top 2 winners as baselines; our hybrid framework improves the average solution score by up to 4.9% over tt-open-wbo-inc-Glucose and 4.8% over SPB-MaxSAT-c-FPS at a 300-second time limit, with the potential to obtain better solutions surpassing the best known solution recorded in the competition evaluation.

0.10

Graph Coarsening Enables Escaping Local Optima in Compute-Constrained Nonconvex MAX-CUT

cs.LG cs.AIcs.CLmath.NA+1 ·2026-10-13 ·M. Harper Langston, Pierre-David Letourneau, Dalton Jones, Harris Teague, Peter Scott +5 more
publishedbenchmark similarity 0.65
Abstract

Because its binary optimization landscape contains exponentially many local optima, MAX-CUT is highly sensitive to initialization. We study Particle Polynomial Relaxation (PPR), a moment-based nonconvex continuous reformulation possessing an advantageous optimization landscape. We warm-start PPR with Combinatorial Multigrid (CMG), a spectral graph-coarsening method that produces structure-aware initial solutions in near-linear time without training data. On \texttt{t2g20} ($n=400$), benchmark instance with known exact optimum, the combined CMG+PPR pipeline reaches $97.5\%$ of optimum on average and $98.4\%$ on the best run. An extended variant with discrete local-search refinement reaches the published optimum on all sixty Biq Mac instances evaluated by a recent neural branch-and-bound method. Using a sparse CSR representation, the same approach scales to G-set instances with up to $20{,}000$ vertices reducing memory requirements by up to $3333\times$ while maintaining a consistent improvement over the CMG warm start. Gains are largest on sparse weighted graphs; on dense graphs we complement the pipeline with spectral sparsification.

0.31

PaNGEA: Parallel Node Generation and Exploration Algorithm on GPU

cs.DC math.OC ·2026-10-02 ·Jean Pauphilet, Yupeng Wu
similarity 0.63
Abstract

Primal heuristics for finding high-quality feasible solutions are an important component in mixed-integer optimization (MIO) solvers. Recent advances in GPU-accelerated optimization algorithms show the potential of GPU acceleration for continuous optimization. In this paper, we introduce the Parallel Node Generation and Exploration Algorithm (PaNGEA), a GPU-friendly MIO primal heuristic. PaNGEA explores restricted subproblems by combining linear-relaxation solves with a local-search procedure designed for efficient batched execution on GPUs. In addition, instead of relying on a single heuristic for iterative variable fixing, we leverage GPU batching capabilities to generate and explore multiple subproblems in parallel. PaNGEA leverages GPU capabilities in two ways. First, on 283 MIPcc26 and MIPLIB instances, implementing a single-node primal heuristic on the GPU reduces the average gap integral by 8-18% relative to its CPU counterpart. Second, generating and exploring multiple nodes in parallel further reduces the average gap integral by 12-19%.

0.22

Jointly Optimizing Memory, Computing and Offloading for Energy-Efficient DNN Inference

cs.LG cs.AI ·2026-11-08 ·Yunchu Han, Zhaojun Nan, Sheng Zhou, Zhisheng Niu
top venue similarity 0.63
Abstract

In edge intelligence systems, computation offloading and dynamic voltage and frequency scaling (DVFS) are widely used to improve energy efficiency. However, as applications like deep neural network (DNN) inference evolve in complexity, their demands for memory resources have progressively increased, establishing memory as a critical bottleneck that impacts both latency and energy consumption. In this paper, we propose a joint optimization scheme integrating memory, computing and offloading for energy-efficient DNN inference. We formulate the energy minimization problem under deadline constraints as a mixed-integer nonlinear programming (MINLP) problem, where the main challenge arises from the coupling between offloading and resource optimization. To address this issue, we decompose the original problem into two subproblems under a fixed offloading policy. The local subproblem is transformed into an equivalent geometric programming (GP) problem to derive the optimal memory frequency and computing frequency, while the edge subproblem is solved via convex optimization. An efficient coordinate descent (CD) algorithm is further developed to jointly optimize all variables. Simulation results demonstrate that our proposed algorithm achieves near-optimal performance with the gap from the optimal policy being at most 9.3%, and reduces the energy consumption of devices by up to 16.1% compared with benchmarks without memory frequency optimization.

0.18

GPU-Accelerated Conic Quadratic Programming with Local Linear Convergence under Strict Complementarity

cs.DC math.OCcs.MS ·2026-08-10 ·Hongpei Li, Yicheng Huang, Huikang Liu, Dongdong Ge, Yinyu Ye
code/datahighly cited similarity 0.63
Abstract · Source code available at https://github.com/Lhongpei/PDHCG

We present PDHCG-CQP, a GPU-accelerated first-order solver for large-scale conic convex quadratic programming. PDHCG-CQP supports affine constraints and Cartesian products of nonnegative, second-order, rotated second-order, exponential, and three-dimensional power cones. At its core is a restarted averaged primal-dual hybrid gradient (PDHG) method, whose primal update is computed inexactly by solving a conic quadratic proximal subproblem with projected gradient iterations. We establish local linear convergence of the restarted averaged scheme with both exact and inexact primal proximal evaluations under a uniform local quadratic-growth condition on the smoothed primal-dual gap. We further show that this condition holds under strict complementarity by exploiting a rotated second-order-cone lifting together with local primal and dual regularity conditions. Our C/CUDA implementation combines matrix-free linear algebra, batched cone projections, adaptive inner solves, reflected-Halpern acceleration, and fully device-resident KKT residual computations. It also supports multi-GPU execution through a two-dimensional partitioning of the problem data. Extensive experiments on standard and large-scale quadratic programming (QP), convex quadratically constrained quadratic programming (QCQP), second-order cone programming (SOCP), and quasilinear Fisher equilibrium benchmarks demonstrate that PDHCG-CQP achieves state-of-the-art robustness among first-order solvers while scaling efficiently to 8 GPUs and instances with up to $4.4\times10^8$ stored primal coordinates. PDHCG-CQP is open source and available at https://github.com/Lhongpei/PDHCG.

0.62

GEAR: A GPU-Accelerated Global Solver for Bounded Continuous Nonlinear Programs via Linear Bound Propagation

cs.LG math.OCcs.MSmath.NA ·2026-11-07 ·Duo Zhou, Hesun Chen, Xiangru Zhong, Grani A. Hanasusanto, Huan Zhang
top venuecode/data similarity 0.63
Abstract · Accepted by NeurIPS 2026

We present a novel GPU-accelerated global solver for constrained nonlinear programming (NLP) inspired by the efficient linear bound propagation framework in neural network (NN) verification. Existing work on NN verification, a problem that can be cast as feasibility detection for a nonlinear objective, demonstrated orders-of-magnitude speedups with the linear bound propagation-based framework when compared to traditional solvers. Extending this paradigm to global nonlinear programming requires addressing many challenges: a global constrained NLP solver must effectively exploit all, possibly unstructured, nonlinear constraints to improve the objective, whereas NN verification typically handles simple input box constraints over a well-structured NN and does not directly optimize an objective function. We address these challenges by fully exploiting the linear bounds produced by bound propagation: these linear bounds can be viewed as relaxations of nonlinear constraints and used to provide lower bounds, check infeasibility, and guide the search for a primal solution. In addition, we propose tighter linear relaxations for bilinear, quotient, and other commonly used nonlinear functions in NLP problems, and a projected augmented Lagrangian method tightly coupled to our dual solving procedure to produce primal solutions. Our method solves 421 of 505 bounded and continuous NLP problems in the GAMS and MINLPLib benchmarks under a 180-second limit, more than each of the six global solvers we compare with, including Gurobi and BARON (commercial), and SCIP (open-source). Sixteen of these problems are certified by none of the six global solvers; all of them contain exponential, logarithmic, or trigonometric terms, which are often challenging for traditional approaches. Project webpage is at https://verified-intelligence.github.io/GEAR.

0.38

Constrained Graph Diffusion for Mixed Integer Optimization

cs.LG ·2026-08-13 ·Vincenzo Di Vito, Yusuf Guven, Babak Badnava, Deepjyoti Deka, Kaarthik Sundar +1 more
similarity 0.62
Abstract

This paper proposes a novel learning-based approach to approximately solve instances of mixed-integer optimization problems. These problems are computationally challenging, as they require jointly determining discrete and continuous decisions while satisfying complex combinatorial constraints. problem-agnostic and can accommodate a broad class of mixed-integer optimization problems through suitable projection operators. We introduce Constrained Graph Diffusion (CGD), a learning-based framework that approximately solves recurring instances of such problems by learning a conditional distribution over their discrete decisions. CGD uses a graph-based diffusion model and incorporates constraint information directly into the reverse diffusion process, steering intermediate predictions toward the feasible region throughout generation. By operating on continuous relaxations of the discrete variables, CGD defines a differentiable constrained generation pathway up to terminal discrete recovery. Once the discrete decision is recovered and fixed, a numerical optimizer solves the remaining continuous problem, avoiding online combinatorial search over the binary variables while retaining numerical optimization for continuous completion. We evaluate CGD on AC-OPF with branch switching and discrete portfolio optimization, demonstrating substantial improvements in feasibility and solution quality over learning-based baselines while achieving speedups of up to $543\times$ over state-of-the-art MIP solvers on large instances.

0.04

DCEmbed: Scalable Optimization over Neural Surrogates

cs.LG math.OC ·2026-09-27 ·Akshay Sreekumar, Nicolas Christianson, Priya L. Donti, Ellen Vitercik, Ram Rajagopal
similarity 0.62
Abstract

Neural surrogates can accelerate large-scale optimization by replacing expensive or intractable model components with efficient learned approximations, but solving the resulting embedded problems can remain prohibitively costly. For instance, standard exact encodings of neural networks with ReLU activations allow the problem to be solved by mixed-integer solvers, but add large numbers of binary variables to accommodate the nonlinearity of the activations, which can render the problem computationally prohibitive. To address this, we propose DCEmbed, a heuristic for optimization problems with embedded neural surrogates that leverages the difference-of-convex (DC) representation of the network and avoids adding activation binaries. Exploiting shared structure within the DC representation of a ReLU network, we derive a reduced-size, exact formulation for its convex components that can be embedded in optimization problems using just two linear inequalities and one continuous auxiliary variable per hidden neuron. Using this, the problem is solved via an iterative penalty convex-concave procedure, where only the concave portions of the neural terms are approximated at each stage. The original objective, constraints, and any discrete decisions are retained, allowing standard convex or mixed-integer optimization solvers to optimize the host and surrogate jointly at each iteration. In experiments on quadratic programs, mixed-integer resource allocation, and neural two-stage stochastic programming, our method demonstrates much faster progress toward high-quality feasible solutions than approaches using exact mixed-integer embeddings. In particular, DCEmbed achieves $4\times$ lower normalized primal integral than the best exact baseline on the resource allocation problem, while in two-stage stochastic programming it reaches the global surrogate optimum $\sim 5\times$ faster than Gurobi ML.

0.06