Batched Dual Bounds on GPUs for Exact Cloud-RAN Network Adaptation

Many wireless resource allocation problems combine on/off choices with continuous settings. One example is deciding which radio heads (the distributed antennas of a cloud-controlled radio network) to switch on, and then how to shape each antenna's transmit signal so every user gets enough signal quality. These are mixed-integer non-linear programs: exact solutions require search over discrete configurations, and the space of configurations grows exponentially with network size. The standard exact method is branch-and-bound, which repeatedly splits the problem into sub-cases and discards a sub-case once a cheap lower bound shows it cannot beat the best solution found so far. In wireless work, this search runs one node at a time on a CPU. The main speedups so far come from learning to skip nodes, at the cost of losing the guarantee of optimality.

This note proposes a different kind of speedup that keeps the guarantee. The lower bound at each node can be computed by a simple dual iteration that stops at any point and still returns a valid bound, and that iteration is only matrix-vector arithmetic. The solver can therefore evaluate thousands of open nodes at once on a GPU. A related move turned neural-network verification from a minutes-long CPU task into a seconds-long GPU task. We want to know whether the same structural rewrite makes exact Cloud-RAN adaptation fast enough for routine use and for cheap generation of training data for learned solvers.

Core Claim

The benchmark problem is power minimization in a cloud radio access network (Cloud-RAN), taken from Scalable Network Adaptation for Cloud-Rans: An Imitation Learning Approach. Let $s_l \in \{0,1\}$ indicate whether radio head $l$ is active. Let $w_{lk}$ be the beamforming vector that head $l$ uses for user $k$. Let $P^c_l$ be head $l$'s static power cost and $P_l$ its transmit power cap. The problem is

$$ \min_{s, w} \sum_l \Big( P^c_l s_l + \sum_k \|w_{lk}\|^2 \Big) \quad \text{s.t.} \quad \mathrm{SINR}_k(w) \ge \gamma_k \;\; \forall k, \qquad \sum_k \|w_{lk}\|^2 \le s_l P_l \;\; \forall l, $$

where $\gamma_k$ is user $k$'s required signal-to-interference-plus-noise ratio.

Two facts make the bounding step suitable for a GPU. First, once a branch-and-bound node fixes some $s_l$ and relaxes the rest to $[0,1]$, the remaining problem becomes convex after the standard rotation of the beamforming phases. Second, its Lagrangian dual has one multiplier per user and one per radio head. Weak duality says any dual-feasible multiplier vector $\lambda$ certifies

$$ g(\lambda) \le \text{OPT}_{\text{node}}, $$

where $g$ is the dual function. This holds whether or not the iteration has converged. Evaluating $g$ needs only small per-user linear solves, which can be run in batches. We can therefore stack all open nodes of the search tree along a batch dimension and run a few hundred projected dual steps on all of them at once. Every node keeps a certified lower bound at every step, and the solver prunes, branches and re-batches as it goes.

The claim is that this yields order-of-magnitude wall-clock speedups over CPU branch-and-bound while still certifying optimality. It should also extend exact solving to network sizes where prior work could only use learned, approximate pruning.

Relation to Prior Work

The method comes from Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition. That paper splits ReLU network verification into layer-local subproblems and evaluates thousands of dual bounds in parallel on GPUs, reporting up to 50x speedups. It also screens candidate branching variables cheaply before checking the best ones with a full dual bound. We reuse the anytime-valid dual bound, the frontier batching and the cheap-screen-then-verify branching. The objects being bounded are different. They are second-order-cone constraints coupled through interference, not piecewise-linear activations, and the dual structure is per user and per radio head rather than per layer.

The need for this work comes from two wireless papers. The imitation-learning Cloud-RAN paper trains a classifier to mimic a branch-and-bound oracle when deciding which nodes to prune. It reports over 20x speedup with under 0.6% objective loss, and over 14x when transferring from small to larger networks. Its tree search is still sequential, and the learned policy depends on an expensive exact oracle to produce labels. Accelerating Generalized Benders Decomposition for Wireless Resource Allocation generates candidate cuts in parallel but filters them with an SVM before a single-threaded master solve. Its offline training also runs through slow sequential solvers.

Both papers speed up the search by doing less of it. We speed it up by doing each step cheaply and many at a time. The two approaches compose: a faster exact oracle makes the imitation learner cheaper to train.

Two other papers constrain the design. Solving Large-Scale Granular Resource Allocation Problems Efficiently with POP gets up to 100x speedups by randomly partitioning clients and resources into independent subproblems. It states that it breaks down when resources are non-fungible and when objectives, such as counting active servers, are not separable. Interference-coupled radio-head activation has both properties, so we parallelize across search-tree nodes rather than across pieces of the network. Optimizing AI Service Placement and Resource Allocation in Mobile Edge Intelligence Systems shows that per-user decomposition through the alternating direction method of multipliers works when channels are orthogonal. It leaves co-channel interference open, and our setting is exactly that open case.

Research Program

The first component is a batched node solver in PyTorch or JAX. It holds a tensor of node states: fixed-on, fixed-off and relaxed radio heads, plus warm-started dual multipliers inherited from the parent node. It runs projected dual ascent on that tensor and returns, for each node, a certified lower bound and a primal candidate. The primal candidate is obtained by rounding the relaxed activations and solving the fixed-set beamforming problem, again batched. That solve gives a valid upper bound whenever it is feasible.

The second component is a frontier manager. Each round it selects the $B$ nodes with the lowest bounds, branches on radio heads using a screen-then-verify rule, and keeps the GPU busy whenever the frontier shrinks. We will measure how bound tightness trades against the number of dual steps per round. That trade-off decides whether many loose bounds or fewer tight ones finish the search faster.

The third component addresses an open problem the file names directly, the oracle bottleneck. We will regenerate the imitation-learning training data with the GPU oracle and measure how much the labeling cost falls. We will also test whether the learned pruner, when trained on networks too large for the CPU oracle to label, recovers cross-scale accuracy.

A secondary generality check applies the same batched dual bounding to the joint subcarrier-and-power problem studied with Benders decomposition. This tests whether the mechanism depends on Cloud-RAN structure. It is a check, not a second headline.

Baselines

The naive reference point is the standard CPU branch-and-bound that serves as the oracle in the imitation-learning Cloud-RAN paper. Each node's relaxation is solved by an interior-point cone solver, one node at a time. Every method is reported as a speedup over this baseline on identical instances, together with its final optimality gap.

The strongest existing exact competitor is a commercial mixed-integer second-order-cone solver applied to the same formulation with all CPU cores enabled. Commercial solvers include presolve, cutting planes and parallel tree search, so this is the competitor a practitioner would actually reach for. It will be run with default and tuned settings on the same machine class as the GPU host. The tuning budget will match the time we spend tuning the dual step size and batch width.

The strongest existing fast method is the learned DAgger pruning policy, retrained on the same instance generator. Its reported numbers are over 20x speedup over standard branch-and-bound with less than 0.6% objective loss on 10 radio heads and 15 users, and over 14x when trained at 6 heads and 8 users and tested at 10 and 15. No absolute runtimes or results beyond these sizes were found on Lacuna. Because this method gives up optimality, we will compare it with our solver both at matched wall-clock time, by objective loss, and at matched objective loss, by time.

The key ablation keeps our search tree, branching rule and dual relaxation unchanged but evaluates nodes on a multithreaded CPU pool. In a second variant, batch width is set to 1 on the GPU. These variants separate the gain from batching from the gain from the dual reformulation itself.

Beating the field means the following, on the existing 10-head/15-user instances and on generated instances up to about 30 heads and 60 users. We must reach a certified gap of 0.1% faster than both the commercial solver and the CPU-pool ablation. We must match or exceed the learned pruner's speedup without its objective loss. And we must solve to certification instances where the CPU oracle times out.

Why not just…?

Why not just use learned pruning, which already gives 20x? It is a real competitor on speed, and at small sizes it may tie or win. However, it gives up the guarantee, its labels come from the oracle we are accelerating, and its reported cross-scale speedup falls from over 20x to over 14x. The matched-time and matched-loss comparisons, together with the large-network experiment, will settle whether exact batched search dominates at scale or only helps produce training data. In the second outcome, the contribution narrows honestly to faster oracle generation.

Why not just run the commercial solver multithreaded? Commercial solvers are strong. Still, the file reports that monolithic solvers time out on comparable networking MINLPs: the slicing study of Optimal QoS-Aware Network Slicing for Service-Oriented Networks with Flexible Routing hit an 1,800-second limit before reformulation. It also reports that structure-aware solvers beat commercial ones by tenfold on block structure, as in Design and implementation of a modular interior-point solver for linear optimization. The CPU-pool ablation is the decisive test. If spreading the same dual bounds across CPU cores matches GPU throughput, the GPU adds nothing, and we would report that the dual reformulation alone is the contribution.

Why not just partition the network geographically and solve the pieces in parallel? That is the POP strategy. POP itself reports failure under non-fungible resources and non-separable activation-count objectives, and interference between neighboring heads is exactly that kind of coupling. We will include a POP-style geographic partition as a heuristic upper-bound comparison to show the quality loss directly.

Why not just do greedy activation followed by beamforming? Joint Subcarrier and CPU Time Allocation for Mobile Edge Computing and User Association for Load Balancing in Heterogeneous Cellular Networks show that decoupled allocation loses heavily in energy and creates harmful interference. We will report greedy results anyway, as the floor of quality-versus-time.

Decisive Checks

Three results would confirm or kill the idea. First, the speedup over the CPU-pool ablation must grow with frontier size. If it stays flat, batching is not the cause. Second, early-stopped dual bounds must stay tight enough that the node count grows by less than the per-node speedup. Otherwise loose bounds cancel the gain. Third, at sizes beyond the original 10-head benchmark, the GPU solver must certify instances the CPU oracle cannot, and a DAgger pruner trained on those labels must recover the cross-scale accuracy lost at 14x.