B3-PWL: GPU-Batched Branch-and-Bound for Piecewise-Linear Optimization with SOS2 Constraints¶

会议: NeurIPS 2026
arXiv: 2608.28988
OpenReview: https://openreview.net/forum?id=l7awisNMWs
领域: 优化/理论
关键词: 分段线性优化, 分支定界, GPU批处理, SOS2约束, 一阶原始对偶算法

一句话总结¶

针对传统CPU分支定界求解器难以并行化求解大量子问题LP松弛的瓶颈，B3-PWL构建了首个以GPU批处理一阶原始对偶求解器为核心引擎的SOS2分段线性优化分支定界框架，配合B2-SpMV不规则稀疏矩阵分块内核与统一可行性搜索模块，在基准测试中实现了相比NVIDIA cuOpt达9.25倍的几何平均求解加速。

研究背景与动机¶

分段线性（Piecewise-Linear, PWL）优化广泛存在于投资组合优化、人员排班、带阀点效应的机组组合以及大规模资源分配等混合整数规划（MIP）实际应用中。在经典建模体系中，非线性函数通常通过特殊有序集（SOS2）的凸组合权重 $\lambda$ 公式化表示，以在保持数学规划兼容性的同时近似复杂非线性关系。然而，要将这类问题求解至全局最优解极其昂贵，因为整数与SOS2组合约束诱导了解空间呈指数级爆炸，迫使经典分支定界（Branch-and-Bound, B&B）在单实例中递归产生成千上万甚至数以百万计的线性规划（LP）松弛子问题。

长期以来，工业级MIP求解器（如Gurobi、SCIP、HiGHS）以及近期结合GPU加速的求解器（如NVIDIA cuOpt）在核心B&B主循环中高度依赖运行在CPU上的单纯形法（特别是对偶单纯形法）。单纯形法的基重构与序列化旋转机制（pivoting）天然具有极强的顺序依赖性，无法有效映射至现代GPU的大规模高并发硬件架构上。虽然近年诸如 $\alpha\beta$-CROWN 等工具在神经网络鲁棒性验证中成功应用了GPU分支定界，但其依赖于神经网络特定的逐层区间界传播（LiRPA）且仅需松弛的下界判定性质，无法直接推广到通用且必须精确定位全局最优目标值的PWL优化中；另一方面，cuOpt等工具仅将GPU一阶LP作为全强分支（FSB）或界收紧（OBBT）等辅助子程序的辅助加速器，节点LP松弛计算依然受制于CPU单纯形法。

因此，通用PWL优化面临的核心矛盾在于：GPU海量并发计算资源与经典单纯形法顺序旋转特性之间存在不可调和的架构失配，而子问题经预求解后约束矩阵维度各异的不规则性又阻碍了GPU批处理LP的高效实现。本文的核心 idea 是：将批处理一阶原始对偶求解器（cuPDLPx）确立为分支定界主循环的核心计算原语，设计面向异构不规则约束矩阵的B2-SpMV分块稀疏内核，并结合SOS2直接修复与批处理可行性泵构建统一可行性搜索模块，实现全流程端到端的高效GPU批处理分支定界。

方法详解¶

整体框架¶

B3-PWL通过CPU与GPU的高效协同机制组织计算：CPU端负责维护全局B&B搜索树拓扑结构、活跃节点优先队列管理、批处理任务打包以及界更新与分支判定；GPU端则作为高吞吐的批处理LP求解引擎，执行经PSLP预求解与Ruiz重缩放后的异构子问题批处理原始对偶混合梯度（PDHG）迭代。

整个求解流程在每一轮次中包含四个紧密衔接的阶段： 1. 任务汇聚与组装：CPU根据搜索策略从活跃节点队列中提取 $B$ 个子问题，解除SOS2约束并将节点限定的分段区间编码为变量上下界固定条件，组成批处理任务； 2. GPU批处理求解：将任务批次分发给基于cuPDLPx定制的一阶求解内核，利用B2-SpMV稀疏分块乘法并发执行数千次PDHG迭代，直至满足停机条件； 3. 统一可行性搜索与解回传：在GPU输出原始解后，立即执行SOS2直接修复启发式；若修复点未能满足线性约束，则无缝注入批处理目标可行性泵（Feasibility Pump）生成软目标任务，与后续搜索任务同批并发求解，快速推挤出高质量可行解并收紧全局上界； 4. 状态更新与分支定界：CPU接收解向量，更新全局上下界，剪枝劣解与不可行节点，对未定节点执行SOS2断点范围二叉分支，生成新子问题重新入队。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：SOS2分段线性优化问题<br/>根节点松弛模型初始化"] --> B["1. 异构子问题批处理组装<br/>提取活跃节点并固定分段边界"]
    B --> C["2. B2-SpMV异构稀疏矩阵分块与GPU批求解<br/>cuPDLPx一阶PDHG并发迭代"]
    C --> D{"3. 统一可行性搜索：<br/>SOS2直接修复是否满足约束？"}
    D -->|否：线性约束违反| E["批处理可行性泵<br/>构建软目标代理任务并注入下批次"]
    D -->|是：满足原约束| F["更新全局最佳可行解与全局上界"]
    E --> F
    F --> G["4. 剪枝判定与二叉分支扩展<br/>生成新子问题并入队活跃集合"]
    G -->|活跃队列非空且Gap大于容限| B
    G -->|队列耗尽或收敛至目标Gap| H["输出：全局最优解及最优目标值"]

关键设计¶

1. 基于cuPDLPx的异构子问题批处理一阶LP引擎：打破单纯形法对GPU并行化的阻碍

传统B&B在各节点求解LP松弛时普遍采用对偶单纯形法，其序列化旋转基操作无法在GPU上展开大规模并行。针对PWL优化各子问题均继承自根问题且仅在变量分界区间上存在差异的结构特性，B3-PWL将一阶原始对偶混合梯度法（cuPDLPx）深度拓展为批处理执行模式。在批次 $\mathcal{T}=\{1,\dots,B\}$ 中，每个任务 $t$ 对应一个移除了SOS2约束并锁定不可行断点权重 $\lambda_{j,i}^{(t)}=0$ 的盒约束LP： $$\min_{x^{(t)}} c^{(t)\top}x^{(t)} \quad \text{s.t.} \quad \ell_A^{(t)} \leq A^{(t)}x^{(t)} \leq u_A^{(t)}, \quad \ell_x^{(t)} \leq x^{(t)} \leq u_x^{(t)}$$ 通过在GPU上同时调度所有任务的内部PDHG算子，更新步显式写为： $$x_{k+1}^{(t)} = \Pi_{\mathcal{X}^{(t)}}\!\left(x_k^{(t)} - \tau_k^{(t)}\bigl(c^{(t)} - A^{(t)\top}y_k^{(t)}\bigr)\right)$$ $$\bar{x}_{k+1}^{(t)} = 2x_{k+1}^{(t)} - x_k^{(t)}$$ $$y_{k+1}^{(t)} = y_k^{(t)} - \sigma_k^{(t)}A^{(t)}\bar{x}_{k+1}^{(t)} - \sigma_k^{(t)}\Pi_{-\mathcal{S}^{(t)}}\!\left((\sigma_k^{(t)})^{-1}y_k^{(t)} - A^{(t)}\bar{x}_{k+1}^{(t)}\right)$$ 其中 $\tau_k^{(t)}=\eta_k^{(t)}/\omega_k^{(t)}$ 与 $\sigma_k^{(t)}=\eta_k^{(t)}\omega_k^{(t)}$ 分别为根据对偶距离由PID控制器独立动态调节的任务级原始/对偶步长。配合反射Halpern加速迭代与自适应重启机制，各子任务独立维护终止条件与步长，在单次GPU核函数分发中吞吐海量子问题求解。

2. B2-SpMV不规则稀疏矩阵分块内核：攻克预求解导致的维度不一致瓶颈

为消除冗余变量并加速收敛，各节点LP在求解前必须经过独立的任务级预求解（PSLP）和Ruiz对角缩放。然而预求解会导致不同子问题被精简出的稀疏约束矩阵 $A^{(t)}$ 在行数、列数及非零元分布上高度异构（ragged collection）。现有的cuSPARSE库既不支持批处理SpMV调用，若强行将整个批次展平成单一的大对角稀疏矩阵又会引发极端严重的负载不均衡与间接寻址开销。

B3-PWL专门设计了面向异构稀疏矩阵的批处理分块SpMV内核（B2-SpMV）。该内核将各任务的稀疏矩阵 $A^{(t)}$ 划分为固定尺寸的二维微块（tiles），剔除所有全零瓦块，将全批次剩余的非零瓦块紧凑压入单一的GPU连续显存张量中。同时，内核为每个子问题构建瓦块索引映射表（Tile Index Map），指示矩阵网格坐标对应的显存物理瓦块地址或空标记。在执行正向 $A^{(t)}x^{(t)}$ 或转置 $A^{(t)\top}y^{(t)}$ 运算时，单个GPU线程块（Thread Block）分配负责单个子问题的一行或一列瓦块计算，遇到空标记直接跳过，既避免了零块的无效浮点开销，又彻底实现了跨任务的显存合并访问（coalesced access），在批尺寸增大时相比循环调用cuSPARSE取得了超50倍的核函数加速。

3. 统一可行性搜索模块：直面一阶内点残差并快速收紧全局上界

分支定界算法的高效剪枝极度依赖高质量可行解（Incumbent）所建立的紧致全局上界。然而，单纯形法天然输出具有基可行性的多面体极点解，而一阶PDHG算法是从LP多面体内部向边界收敛，其后求解出的原始解即便在宏观容限内满足约束，在理论上应严格为0的SOS2断点权重上通常仍残留微小的非零数值，直接导致叶子节点频繁被误判为违背SOS2约束。

为攻破该固有缺陷，B3-PWL提出了两阶段统一可行性搜索架构： - SOS2直接修复启发式：提取LP连续解 $\hat{x}_j$，直接截断至有效区间并定位其所落入的唯一分段单元 $[d_j^{k_j}, d_j^{k_j+1}]$，将两端权重解析赋值为 $\tilde{\lambda}_j^{k_j} = \frac{d_j^{k_j+1}-\hat{x}_j}{d_j^{k_j+1}-d_j^{k_j}}$ 及 $\tilde{\lambda}_j^{k_j+1} = \frac{\hat{x}_j-d_j^{k_j}}{d_j^{k_j+1}-d_j^{k_j}}$，其余分量强制置零。此时重构点 $(\tilde{x}, \tilde{z}, \tilde{\lambda})$ 天然严格满足SOS2约束，随后只需快速代入检验原线性约束 $A\tilde{x}+G\tilde{z} \leq b$，若通过即刻更新全局上界。 - 批处理目标可行性泵（Feasibility Pump）：若直接修复因违反线性约束失败，则将直接修复得到的断点离散投影 $\bar{\lambda}^{(r)}$ 作为软引导目标，构造复合可行性引导目标函数： $$c_{\mathrm{FP}}^{(r)} = \alpha_r c_{\mathrm{prox}}^{(r)} + (1-\alpha_r)\gamma_r c_{\mathrm{orig}}$$ 其中临近项 $(c_{\mathrm{prox}}^{(r)})_{j,k} = -\bar{\lambda}_{j,k}^{(r)}$ 在选定断点上赋予负成本，以极小化目标惩罚诱导LP解贴近目标分段，$\gamma_r = \|c_{\mathrm{prox}}^{(r)}\|_2 / (\|c_{\mathrm{orig}}\|_2 + \varepsilon)$ 用于对齐两项梯度的 $L_2$ 量级，衰减因子 $\alpha_r$ 随迭代轮次动态缩减。最关键的是，可行性泵子问题与常规B&B搜索子问题在矩阵约束上完全同构，仅目标向量不同，因此B3-PWL将其直接混合打包进同一个GPU求解批次中并发分发，实现零额外调度开销的快速可行解搜寻。

训练策略 / 算法配置¶

求解器容限：底层cuPDLPx原始与对偶可行性及最优性残差容限设置为 $10^{-4}$；全局B&B停止判定相对MIP Gap目标设置为 $1.0\%$；
批处理规模与超时：单批次最大包含活跃子问题数依据GPU显存动态调整，全局求解硬性墙上时间预算设为 300 秒；
可行性泵衰减参数：初始权重参数设为 $\alpha_0=1.0$，每次修复尝试未通过线性约束检验时按衰减率 $\alpha_{r+1} = 0.9\,\alpha_r$ 衰退，平衡可行性引导与原目标最优性。

实验关键数据¶

主实验¶

评估在配置NVIDIA RTX PRO 6000 Blackwell Server Edition GPU（96GB显存）与双路192核CPU的服务器节点上进行。在包含43个典型PWL-MIP实例（涵盖投资组合Portfolio 18项、人员排班Workforce 9项、资源分配Resource Allocation 16项，规模在100~1,200个PWL函数与15~25个断点）的基准测试中，以Gurobi（$10^{-6}$ Gap）作为最优解Oracle基准，对比NVIDIA工业级求解器 cuOpt（v26.02.00）：

评估类别	实例数 $n$	Eff-Opt (≤1% Gap) (B3-PWL / cuOpt)	Exact Match (B3-PWL / cuOpt)	算术平均用时 (s) (B3-PWL / cuOpt)	位移几何平均用时 (s) (B3-PWL / cuOpt)	几何平均加速比 Geo-Spd	胜出率 (B3-PWL Wins)
投资组合 (Portfolio)	18	18 / 10	15 / 0	2.5 / 142.2	2.1 / 57.0	29.35×	18 / 18
人员排班 (Workforce)	9	9 / 8	9 / 1	2.6 / 68.9	2.2 / 35.7	17.69×	9 / 9
资源分配 (Resource Alloc.)	16	16 / 12	13 / 8	82.3 / 107.9	39.0 / 67.3	1.75×	11 / 16
全基准总计 (Total)	43	43 / 30	37 / 9	32.2 / 114.1	7.0 / 55.0	9.25×	38 / 43

在进一步纳入经典CPU开源MIP求解器的横向基准对比中： - Gurobi 13.0.2：Eff-Opt 43/43，几何平均用时 1.0 秒； - B3-PWL（本文）：Eff-Opt 43/43，几何平均用时 7.0 秒； - HiGHS 1.15.1：Eff-Opt 40/43，几何平均用时 25.2 秒； - SCIP 10.0.1：Eff-Opt 37/43，几何平均用时 27.1 秒； - cuOpt 26.02：Eff-Opt 30/43，几何平均用时 55.0 秒。

在带阀点效应机组组合（Valve-Point UC）实际电网基准测试中，随时间跨度扩展至 $T=24$ 时，SCIP与cuOpt均在300秒内发生超时（>300s），而B3-PWL在不同断点设置下均在 5.7~9.0 秒内迅速完成 1% MIP Gap收敛认证。

消融实验¶

针对统一可行性搜索模块的核心组件（SOS2直接修复与批处理可行性泵FP），在43个PWL-MIP实例上进行消融验证：

实验配置	可行解获取数 (Feas)	位移几何平均用时 (s)	算术平均用时 (s)	相对无FP加速比 (ii)/(iii)	说明
(i) 无可行性启发式	0 / 43	142.1 (全部未获可行解)	300.0	—	因一阶法内点数值浮点扰动，43个实例全部无法记录可行解
(ii) 仅SOS2直接修复	43 / 43	11.56	53.6	1.00× (基准)	恢复全部实例可行解，消除内点微小残差影响
(iii) 直接修复 + 可行性泵 (完整)	43 / 43	7.05	32.2	1.69×	混合目标协同驱动，在Portfolio/Workforce上提速2.18×/2.61×

同时，系统运行耗时剖析显示： - GPU侧LP求解（PDHG主循环与GPU准备）：平均占分支定界总耗时的 74.0%； - PSLP预求解与重缩放：占 11.3%； - CPU侧树管理（SOS2检查、分支选择、批次构造、后处理）：合计仅占 14.7%。这明确证实了算法的吞吐瓶颈落在GPU一阶LP运算能力上，而非CPU端树管理。

关键发现¶

直接修复是消除一阶法内点残差的生命线：由于PDHG算法不具备单纯形法顶点的离散投影属性，缺失SOS2直接修复时系统在所有实例上均无法捕获可行解；而直接修复能以极低代价（仅占约5.9%耗时）挽救可行性；
极速发现上界引领全局性能跃升：在寻找最佳可行解用时（Time to Best Incumbent, TTB）指标上，B3-PWL相比cuOpt达成了 12.28倍 的几何平均加速（4.22秒 vs. 45.77秒），优质可行解几乎在前几个批次中便被锁定，大幅提前触发深层子树剪枝；
B2-SpMV在大批次下彻底释放GPU显存吞吐：当子问题维度在8,000~25,000浮动时，分块瓦块索引技术使SpMV有效吞吐随着批尺寸扩展而急剧上升，相比循环调用cuSPARSE取得了超 50倍 的加速比。

亮点与洞察¶

将一阶LP确立为主循环引擎而非辅助工具：颠覆了以往“GPU仅作为全强分支/边界收紧等旁路辅助”的思维惯性，首次成功证明一阶原始对偶算法具备承载整个分支定界主节点LP吞吐的实用可行性；
异构不规则张量的高性能分块抽象（B2-SpMV）：通过“规则瓦块划分 + 紧凑显存张量打平 + 稀疏索引映射”解耦了预求解导致的矩阵维度离散化问题，为GPU处理异构优化问题批次提供了通用底层范式；
同批复用矩阵的低开销可行性泵：巧妙利用可行性泵与原问题仅目标向量不同的代数特性，避免新开GPU核函数调用，将原/对偶可行性探索完美折叠在同一计算批次内。

局限与展望¶

对偶界认证收敛较慢（尾部效应）：一阶优化算法在极高精度区间内具有次线性收敛特征，导致算法虽然极快找到最优可行解（上界），但在最后关闭1%以内的对偶间隙以完成数学可证明认证时耗费了大部分时间；
缺乏子问题间的热启动（Warm Start）机制：单纯形法可直接沿用父节点的对偶基以极少步数完成子节点求解，而当前PDHG各子节点几乎从头冷启动迭代，如何跨子问题继承缩放权重与重启历史仍是开放性难题；
分支割平面与高级策略尚未整合：系统尚未引入现代MIP求解器完备的割平面（Cutting Planes）生成模块，未来若能将GPU兼容的有效割平面融入一阶松弛模型，有望大幅收紧对偶边界。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次将批处理一阶原始对偶LP引擎作为SOS2分支定界主循环的核心算子，架构极具开拓性。
实验充分度: ⭐⭐⭐⭐⭐ 涵盖合成PWL与真实电网阀点机组组合基准，对比覆盖cuOpt、Gurobi、SCIP与HiGHS，消融深入详实。
写作质量: ⭐⭐⭐⭐⭐ 逻辑缜密，软硬件协同设计的系统瓶颈与代数推导剖析透彻。
价值: ⭐⭐⭐⭐⭐ 为推动现代运筹优化与混合整数规划求解器全面迈入GPU高并发计算时代树立了标志性里程碑。