Data center networks that use free-space optical links send beams of light through open air between racks. Operators bundle many small traffic flows onto shared beams, a practice called traffic grooming, to save on expensive switching hardware. Deciding which flows share which beam is NP-complete even on a simple chain of nodes. In dense deployments a second problem appears: beams that are active at the same time leak light into each other's receivers. A beam's usable capacity then depends on which other beams are switched on. Today's grooming methods cannot measure how far their answers are from the best possible, and this second effect makes the problem harder still. We propose to write interference-coupled grooming as a quadratic program over binary choices and relax it to a convex semidefinite program. The relaxation yields a provable lower bound on the hardware cost. We then train a graph neural network to produce, in milliseconds, both a feasible grooming plan and a dual solution, which a cheap eigenvalue correction turns into a valid lower bound. Every plan the system outputs therefore comes with a certified optimality gap. The guarantee holds even on networks far larger than any seen in training, and even when the network makes mistakes.
In two sentences: learned solvers for network resource problems are fast but cannot say how good their answers are, and exact solvers cannot say anything at large scale. We make the learned solver output a mathematically valid bound alongside its plan, so that speed and certified quality come together, and we test this on a grooming problem whose hardness is well understood.
Core Claim
The claim is that a message-passing network can output dual variables for a semidefinite relaxation that are good enough to certify near-optimality of large instances. A semidefinite relaxation replaces a vector of unknowns $z$ by the matrix $Z = zz^\top$, keeps only the convex condition that $Z$ is positive semidefinite, and drops the requirement that $Z$ has rank one. The resulting bounds should be tighter than those from linear relaxations, because the problem's hard part, beam-to-beam interference, is quadratic. A second claim is that the eigenvalue correction which makes the bound valid also accounts exactly for coupling between communities of the network. This gives a principled answer to the cross-community leakage that divide-and-conquer influence methods ignore.
The problem is defined as follows. Let $x_{d,w}\in\{0,1\}$ indicate that demand $d$ (with rate $r_d$) is groomed onto beam or wavelength $w$. Let $y_{v,w}\in\{0,1\}$ indicate an add-drop multiplexer at node $v$ on $w$, and $a_w\in\{0,1\}$ indicate that beam $w$ is active. Let $G_{uw}\ge 0$ be the cross-talk gain from beam $u$ into the receiver of beam $w$, and let $\beta_w$ be the interference beam $w$ can tolerate while still meeting its target signal-to-interference ratio. Let $g$ be the grooming factor, the number of unit flows a beam carries. The problem is
$$\min \sum_{v,w} y_{v,w}\quad \text{s.t.}\quad \sum_w x_{d,w}=1,\;\; y_{v,w}\ge x_{d,w}\ (d \text{ ends at } v),\;\; \sum_d r_d x_{d,w}\le g\,a_w,\;\; a_w\Big(\sum_{u\ne w}G_{uw}a_u-\beta_w\Big)\le 0 .$$
Setting $G=0$ recovers classical grooming. That problem is NP-complete on chains with $g=2$, as shown in The Traffic Grooming Problem in Optical Networks with Respect to ADMs and OADMs, so our problem is NP-hard by restriction.
The certificate works like this. Lift $z=(x,y,a,1)$ to $Z$, add the redundant constraint $\mathrm{tr}(Z)\le N$ (valid because $z$ is binary of length $N-1$ plus a constant), and write the dual. For nonnegative multipliers $\lambda$ on the constraints, let $S(\lambda)$ be the dual slack matrix and $b$ the vector of constraint right-hand sides. Then
$$\mathrm{OPT}\;\ge\; b^\top\lambda + N\cdot\min\big(0,\ \lambda_{\min}(S(\lambda))\big)$$
holds for any $\lambda\ge 0$, by weak duality. The network only needs to propose $\lambda$. The smallest eigenvalue of the sparse matrix $S(\lambda)$ is computed by a Lanczos iteration in time linear in its number of nonzeros. A poorly trained network yields a loose bound, never a wrong one.
Where This Sits in Prior Work
Four bodies of work supply the method, motivate the gap, or constrain the design.
The learning machinery comes from graph-based interference modeling. Unfolding WMMSE Using Graph Neural Networks turns the iterations of a classical power-control algorithm into four neural layers. It matches its sum rate (83.21 against 82.94) at one eighth the runtime, but it offers no bound on optimality. Graph Neural Networks for Scalable Radio Resource Management shows that message passing is equivalent to a class of distributed local algorithms. It transfers from 50 to 1,000 transceiver pairs with a loss of about 1–2%. Random Edge Graph Neural Networks trains such policies with a primal-dual method over random fading graphs. All three handle continuous power control and report objective values without certificates. We reuse their architectures and their primal-dual training style, but we point the dual head at a convex relaxation so that its output becomes a proof.
The relaxation side comes from wireless beamforming. Fan, Liu and Liu prove that the relaxation is exact for cooperative beamforming. They replace slow interior-point solvers with a dual fixed-point iteration, and that iteration is the kind we propose to unfold. The RIS cognitive sensing work shows the more common case, where the relaxation is not exact and needs Gaussian randomization inside a block coordinate loop of about 11 iterations, each solving two SDPs. Our problem has binary variables, so we expect it to resemble the second case: a nonzero gap that has to be measured rather than proved away.
The grooming literature motivates the work and supplies ground truth. Shalom et al. give the MERGE algorithm, whose worst-case ratio is $2\sqrt{g}\lceil\log n\rceil$ on chains. The star-network paper shows the problem is polynomial for capacity $C\le 2$ and NP-complete above it. That threshold gives us an exactly solvable regime for checking bounds. The metaheuristics survey, TG-FSO, and LightFDG produce practical plans but provide no bounds. They also treat free-space optical beams as interference-free. TG-FSO reports 3.4 times the throughput of equal-cost multipath routing.
The decomposition comes from scalable influence optimization. Community-IM splits a network into disjoint communities, solves each one locally, and divides the budget progressively. Its stated weakness is that it ignores spread across community boundaries. We borrow the partition and the progressive split of the beam budget. The global eigenvalue check in the bound above then charges any cross-community interference that the local solutions missed, so leakage lowers the certified bound instead of silently corrupting it. The influence-blocking work is a reminder that well-engineered combinatorial methods can be three orders of magnitude faster than naive greedy. Any learned method has to beat strong classical heuristics, not straw men.
Research Program
The work has three parts. The first is a benchmark generator for interference-coupled grooming. It takes chain, ring, and star topologies from the complexity literature. It adds data center instances that follow the TG-FSO emulation: MapReduce shuffle traffic of 80% mice flows and 20% elephant flows, at 5 Gbps per wavelength. Cross-talk gains $G_{uw}$ are drawn from the random-geometric Rayleigh model with path-loss exponent 2.2 used by the unfolded-WMMSE study. Gains are thresholded to fix the sparsity of the interference graph. Instance sizes run from tens of beams, where an exact integer program finishes, to over a thousand.
The second part is the solver. A permutation-equivariant message-passing network runs over a heterogeneous graph of demands, nodes, and beams. Its primal head outputs fractional assignments, which a greedy repair step rounds into a feasible plan. Its dual head outputs $\lambda$. Its layers are initialized as an unrolled projected-gradient ascent on the SDP dual, in the spirit of the dual fixed-point method of Fan et al. Training maximizes the certified bound and minimizes the repaired primal cost on small instances, and needs no labels. For the largest graphs the dual is solved block by block over Louvain communities. The global Lanczos correction is then applied once to the full sparse slack matrix.
The third part is analysis. We will characterize when the relaxation gap stays small as interference density grows. We will also test whether certified gaps on instances with $C\le 2$ stars reach zero, as they should if the relaxation captures the polynomial structure there.
Baselines
The naive reference is interference-oblivious grooming followed by switching off beams that violate their interference budget. Its plans are cheap but often infeasible or wasteful. Its bound is the trivial one, given by the number of demand endpoints divided by $g$. It is run on identical instances.
The strongest primal competitors are the TG-FSO multi-level heuristic and simulated annealing tuned per the metaheuristics survey. Both get the same wall-clock budget as our method, with tuning hyperparameters searched on the same training instance distribution. Because our bound certifies any feasible plan, we will also certify their plans. Our primal head beats them only if it reaches equal or lower cost at equal time. No reported result was found on Lacuna for either method on interference-coupled grooming, so these numbers will be produced here. On the interference side alone, the reported anchor is WCGCN at roughly 97–103% of WMMSE sum rate (Shen et al.). That serves as a sanity target for our message-passing backbone on pure power-feasibility subproblems.
The strongest bounding competitor is a generic branch-and-bound integer programming solver. It reports both an incumbent and a proven lower bound at any time. We give it the same CPU budget and compare certified gaps against wall-clock time. On small instances we also run an interior-point SDP solver to measure how close the learned dual gets to the true relaxation value. Beating the integer solver means a smaller certified gap at equal time on instances above a few hundred beams. Below that size we expect to lose and will say so. No reported result was found on Lacuna for any certified bound on this problem.
Three ablations isolate the key ingredients. The first is a linear (McCormick) relaxation with the same learned dual approach, to test whether the semidefinite lifting matters. The second removes the eigenvalue correction, giving a fast but uncertified estimate, which shows how often an uncorrected learned dual overstates the bound. The third replaces community decomposition with disjoint Community-IM-style local solves without the global correction, to quantify leakage.
Why not just…?
Why not just run an exact integer programming solver? It is the real threat at small and moderate sizes. It provides both plans and bounds, and on chain instances it will be optimal. The grooming hardness results imply that its worst-case time grows exponentially. The open question is where the crossover with our method lies on realistic instances. The equal-time gap-versus-size curves settle this directly. If the solver's anytime bound matches ours at 1,000 beams, the learned certificate is not worth building.
Why not just use a linear relaxation, which is far cheaper than an SDP? It may be enough. The interference constraint is a sum of products of activation variables, and McCormick linearization of such products is typically loose when many beams interact. The semidefinite lift captures their joint structure. This is a hypothesis, not a known fact. The linear-relaxation ablation on instances with known optima decides it. If the linear bound is within a few percent of the semidefinite bound, we will adopt the linear dual, since the certificate mechanism carries over unchanged.
Why not just train a graph network to output grooming plans directly, as in WCGCN or unfolded WMMSE? Those methods report objective values only relative to a classical algorithm. That comparison breaks down at scale, where no reference is computable. A direct-prediction network may well produce good plans, and our primal head is essentially one. What it cannot provide is evidence of quality on a 1,000-beam instance. The no-certificate ablation shows how much that uncertainty matters in practice.
Why not just partition the network into communities and solve each independently? Community-IM shows this is fast. It also admits that boundary effects are ignored, and cross-talk from neighboring clusters is exactly such an effect. The disjoint-solve ablation measures the infeasibility and cost increase this causes. Our global correction converts that leakage into a looser but valid bound.
Proposed Experiments
The first decisive check is on chains, rings, and stars small enough for exact solution. We compare the semidefinite bound, the linear bound, and the learned certified bound against the true optimum, and compare MERGE's a priori ratio against the gaps we observe. On $C\le 2$ stars, the relaxation should be exact or nearly so. A large gap there would indicate a formulation error.
The second check measures transfer. We train on instances of 20–50 beams, then evaluate certified gap and runtime on 100 to 1,000+ beams at several interference densities. The learned dual must stay within a stated fraction of the interior-point SDP value wherever that value is computable.
The third check is the head-to-head against the integer solver and the tuned heuristics at equal time on TG-FSO-style data center instances. The outcome to report is certified gap (primal cost minus best bound, divided by primal cost) against wall-clock time.
The project's premise fails, and we would say so, under either of two outcomes. One is that the semidefinite bound is not meaningfully tighter than the linear bound on interference-heavy instances. The other is that learned certified gaps at large scale are no smaller than the integer solver's anytime gap at the same time.
References
- The Traffic Grooming Problem in Optical Networks with Respect to ADMs and OADMs: Complexity and Approximation
- Unfolding WMMSE Using Graph Neural Networks for Efficient Power Allocation
- Graph Neural Networks for Scalable Radio Resource Management: Architecture Design and Theoretical Analysis
- Optimal Wireless Resource Allocation With Random Edge Graph Neural Networks
- Efficiently and Globally Solving Joint Beamforming and Compression Problem in the Cooperative Cellular Network Via Lagrangian Duality
- RIS-Enhanced Cognitive Integrated Sensing and Communication: Joint Beamforming and Spectrum Sensing
- Approximating the traffic grooming problem in tree and star networks
- Metaheuristic Approaches to Traffic Grooming in Wdm Optical Networks
- Design and Provision of Traffic Grooming for Optical Wireless Data Center Networks
- LightFDG: An Integrated Approach to Flow Detection and Grooming in Optical Wireless DCNs
- A Community-Aware Framework for Social Influence Maximization
- Influence Minimization via Blocking Strategies