One-sentence Summary

Researchers at Rice University introduce Neural Certificate Pricing (NCP), an unsupervised learning framework that predicts certificate-level dual prices and uses a structured recovery layer to amortize separation for combinatorial optimization, achieving global feasibility under a certificate-consistency condition and first-order error robustness, either outperforming state-of-the-art neural baselines by large margins or matching them at a fraction of the computation time across three problem classes, and showing stronger out-of-distribution generalization.

Key Contributions

• Neural Certificate Pricing (NCP) trains a neural network to predict certificate-level dual prices and uses a structured recovery layer to produce a feasible primal marginal in an unsupervised manner; the process is an amortized separation that learns residual prices whose aggregate effect enters recovery without enumerating violated inequalities.
• A local stability result proves that, under a certificate-consistency condition, the recovery is smooth and first-order errors in the predicted prices lead to only second-order degradation in the primal objective value near a primal-realizing point.
• Across three combinatorial optimization problem classes, NCP outperforms state-of-the-art neural baselines by large margins or matches them at a fraction of the computation time, and demonstrates stronger out-of-distribution generalization.

Introduction

Combinatorial optimization on graphs underpins decision-making in networked systems, where local choices must satisfy global coupling constraints, creating an exponential search space. Classical solvers rely on structured search, while recent learning-based methods predict solution components such as scores, policies, or relaxed marginals, leaving the certification of global validity to a separate downstream decoding or repair step. This separation overlooks the inherent asymmetry that a candidate solution can be verified efficiently even when finding it is hard. The authors introduce neural certificate pricing (NCP), an unsupervised framework that learns to generate pricing signals for a certificate-conditioned recovery layer. By representing discrete objects in a marginal space that isolates local consistency, certificate-induced structure, and retained coupling constraints, NCP uses the pricing signal to directly recover a certificate-consistent primal marginal, allowing training to optimize the original objective without requiring labeled solutions and transforming certification from a post-hoc check into an integral solution mechanism.

Method

The authors propose Neural Certificate Pricing (NCP), a framework that solves combinatorial optimization problems over graph-based structures by learning a cost perturbation that tightens a tractable certificate-conditioned recovery. The starting point is the free-energy formulation $p^{\star}(G) = \min_{\mu \in \mathcal{M}_G} F_G(\mu)$p⋆(G)=minμ∈MG​​FG​(μ) over the exact marginal polytope $\mathcal{M}_G$MG​, where $F_G(\mu) = \langle c, \mu \rangle - \tau H_{\mathcal{M}}(\mu)$FG​(μ)=⟨c,μ⟩−τHM​(μ). Direct optimization over $\mathcal{M}_G$MG​ is intractable, and typical relaxations $\mathcal{P}_G$PG​ (local constraints plus a set of explicit global coupling constraints $A_G\mu \le b_G$AG​μ≤bG​) are often loose. The key insight is that while characterizing the full polytope is hard, certifying that a particular marginal vector $\mu$μ belongs to $\mathcal{M}_G$MG​ can be much easier if one has a structural certificate $y \in \mathcal{Y}_G$y∈YG​ that induces a tractable recovery set $\mathcal{S}_G(y) \subseteq \mathcal{P}_{\text{loc}}(G)$SG​(y)⊆Ploc​(G). For many combinatorial problems, such certificates are naturally available: node potentials induce an acyclic order for routing, reduced-cost structures restrict assignments to local subproblems, and conflict or clique covers simplify packing constraints. When explicit coupling constraints are absent, $\mathcal{S}_G(y) \subseteq \mathcal{M}_G$SG​(y)⊆MG​ holds directly; otherwise, dual prices $\lambda \ge 0$λ≥0 for $A_G\mu \le b_G$AG​μ≤bG​ are used together with $y$y to maintain feasibility.

NCP augments this certificate mechanism with a learned cost perturbation $\Gamma \in \mathbb{R}^{|E|}$Γ∈R∣E∣, which plays the role of a residual pricing signal that can tighten the recovery beyond what is achievable by Lagrange multipliers alone. For a fixed certificate $y$y, dual variables $\lambda$λ, and perturbation $\Gamma$Γ, the primal recovery map is defined as

When $\mathcal{S}_G(y)$SG​(y) is contained in $\mathcal{M}_G$MG​, every recovered $\hat{\mu}$μ^​ yields a valid primal bound $F_G(\hat{\mu})$FG​(μ^​) for the original problem. The perturbation $\Gamma$Γ acts as a substitute for the prices of valid inequalities that are omitted from the tractable recovery set. Proposition 3.2 formalizes this: if a certificate $y$y covers an optimizer $\mu^*$μ∗ and the omitted inequalities are $B_G\mu \le d_G$BG​μ≤dG​, then setting $\Gamma^* = B_G^{\top}z^*$Γ∗=BG⊤​z∗ (where $z^*$z∗ are the KKT multipliers for those constraints) guarantees $\mu^* \in Q_G(\Gamma^*, y, \lambda^*)$μ∗∈QG​(Γ∗,y,λ∗). Thus, learning a suitable $\Gamma$Γ can in principle recover the exact optimum.

To ensure that the output of the recovery map is a feasible marginal, the framework requires a certificate consistency condition. Let $C_G$CG​ be a certificate readout map that extracts a certificate from a marginal vector. A pair $(y,\lambda)$(y,λ) is called a consistent certificate at perturbation $\Gamma$Γ if

where $\hat{\mu} = Q_G(\Gamma, y, \lambda)$μ^​=QG​(Γ,y,λ). Proposition 3.3 shows that under consistency, $\hat{\mu} \in \mathcal{M}_G$μ^​∈MG​ and the recovered point satisfies a shifted optimality condition $F_G(\hat{\mu}) - F_G(\nu) \le \langle \Gamma, \nu - \hat{\mu} \rangle$FG​(μ^​)−FG​(ν)≤⟨Γ,ν−μ^​⟩ for any $\nu \in \mathcal{S}_G(y) \cap \mathcal{P}_G$ν∈SG​(y)∩PG​. This turns the search for a good perturbation into an equilibrium-constrained problem: find $\Gamma, y, \lambda$Γ,y,λ that minimize $F_G(\mu)$FG​(μ) subject to $y = C_G(\mu)$y=CG​(μ), $\mu \in Q_G(\Gamma, y, \lambda)$μ∈QG​(Γ,y,λ), and the KKT complementarity $0 \le \lambda \perp b_G - A_G\mu \ge 0$0≤λ⊥bG​−AG​μ≥0. This oracle characterization (OC) is a bi-level program; any feasible solution provides a primal bound because $\mu$μ is a valid marginal.

NCP amortizes this search across instances by training a neural network $\Gamma_\theta(G)$Γθ​(G) to predict the perturbation directly from the instance $G$G. For a given $\theta$θ, the forward pass solves the consistency system via a damped projected fixed-point iteration. Starting from an initial certificate guess $z^0 = (y^0, \lambda^0)$z0=(y0,λ0), the update is

where $D_\rho(\lambda, \mu) = \Pi_{\mathbb{R}_+^{m_G}}[\lambda + \rho (A_G\mu - b_G)]$Dρ​(λ,μ)=ΠR+mG​​​[λ+ρ(AG​μ−bG​)] is a projected dual ascent step, $\rho>0$ρ>0 is a step size, and $\alpha \in (0,1]$α∈(0,1] is a damping factor that stabilizes convergence without changing fixed points. At convergence, the recovered marginal is $\mu_\theta(G) = Q_G(\Gamma_\theta(G), y^\star, \lambda^\star)$μθ​(G)=QG​(Γθ​(G),y⋆,λ⋆), and the unsupervised training loss is simply

evaluated under the unperturbed objective $F_G$FG​ (the perturbation is used only within recovery and consistency). Gradients are computed by implicit differentiation through the certificate-consistency fixed point, circumventing the need to backpropagate through many iterations.

The theoretical analysis justifies this learning scheme by revealing a favorable local structure. At a regular OC solution where strict complementarity holds for the explicit coupling constraints and the implicit function theorem applies, the bi-level problem locally reduces to an unconstrained smooth minimization of $\Phi_G(\Gamma) = F_G(\hat{\mu}_G(z_\Gamma, \Gamma))$ΦG​(Γ)=FG​(μ^​G​(zΓ​,Γ)), where $z_\Gamma$zΓ​ is the implicit solution of the consistency equalities. Theorem 4.1 shows that stationary points of $\Phi_G$ΦG​ coincide with KKT stationary points of the local equality-constrained OC. Moreover, Theorem 4.2 establishes second-order value stability: around a stationary perturbation, a mismatch of order $\varepsilon$ε in $\Gamma$Γ causes only an $O(\varepsilon^2)$O(ε2) change in the objective. Corollary 4.3 decomposes the suboptimality gap relative to the true optimum $p^\star(G)$p⋆(G) into a structural certificate gap $\Delta_{\text{cert}}$Δcert​ and a local optimization residual. If the certificate family is compatible with the underlying discrete structure and the network learns a $\Gamma$Γ within a neighborhood of a stationary point, the residual term is $O(\varepsilon^2)$O(ε2), and when the conditions of Proposition 3.2 are met, the certificate gap vanishes as well. This analysis explains why NCP can recover near-optimal primal bounds: the training objective concentrates on a smooth landscape where approximate consistency translates into small value errors.

Experiment

Across three combinatorial optimization problems (maximum independent set, generalized assignment, and elementary shortest path) evaluated under out-of-distribution conditions, NCP demonstrates robustness to changing objectives and scaling to larger instances while maintaining efficiency comparable to single-pass methods. Ablation studies confirm that the structure certificate and learned perturbation are essential, and learning shifts the primal gap below the canonical Lagrangian bound. The reduced objective exhibits second-order stability near stationary perturbations, aligning with theoretical predictions and supporting stable optimization.

On unweighted maximum independent set benchmarks, NCP achieves near-optimal ratios and solves most instances exactly while keeping inference time close to the fastest single-pass methods. In contrast to other neural baselines, NCP remains robust across all three graphs, most notably on IMDB where it matches the exact solver KaMIS with perfect score and far lower latency than diffusion or iterative approaches. NCP recovered the exact solution on all 200 IMDB instances, equaling KaMIS, whereas Erdos-Neural solved only 30 and Fast-T2T solved 198. On TWITTER, NCP obtained a ratio of 0.9881 and exact count of 120/196 in 1.93 ms, outperforming Erdos-Neural, DIFUSCO, and Fast-T2T while being over 150× faster than DIFUSCO.

On the weighted maximum independent set task, NCP maintains an approximation ratio above 0.97 across all three benchmarks and recovers the exact solution in the majority of instances. Neural baselines Erdos-Neural, DIFUSCO, and Fast-T2T experience sharp performance drops on the larger graphs COLLAB and IMDB, while NCP remains robust and delivers inference in sub-millisecond to low-millisecond times. NCP achieves ratios of 0.9795 (TWITTER), 0.9768 (COLLAB), and 0.9887 (IMDB) and exactly solves 39/196, 941/1000, and 196/200 instances, respectively. On COLLAB and IMDB, Erdos-Neural drops to a ratio of 0.67 and 0.27, DIFUSCO to 0.66 and 0.59, and Fast-T2T to 0.74 and 0.67, showing the vulnerability of these methods to weighted objectives. NCP's inference time stays under 2 ms on TWITTER, under 1 ms on COLLAB, and 0.14 ms on IMDB, combining high solution quality with single-pass-like speed.

NCP achieves the lowest mean optimality gap for top-1 and top-2 masks on the GAP benchmark, outperforming the LP-round baseline. For top-3 masks, its gap is nearly equal to the best competitor while cutting runtime by more than two orders of magnitude. The method also solves more instances exactly at k=2 than other neural approaches, indicating that its learned certificate produces a compact candidate set with near-optimal LP solutions. NCP attains the best mean gap for k=1 and k=2, and for k=3 its gap is almost identical to Fast-T2T while running over 200 times faster. At k=2, NCP exactly solves 32 of 60 instances, compared to 17 for Fast-T2T and 13 for DIFUSCO. NCP consistently improves over LP-round for all k, demonstrating the value of its learned certificate.

On ER and BA graphs, NCP reaches path costs close to the intensive labeling method at small sizes and consistently outperforms LP+Dec. and beam search baselines as graph size grows. Its runtime stays within a few seconds, making it far faster than labeling and beam search, both of which require tens of seconds per instance. The performance gap widens with larger graphs, reflecting the scalability of the learned certificate structure. At n=50, NCP's cost is only slightly behind Label-1M (e.g., -31.22 vs. -32.59 on ER) while cutting inference time from tens of seconds to under 0.13 seconds. On larger graphs where labeling is unavailable, NCP consistently achieves the best path costs among all scalable methods, substantially beating LP+Dec. and beam search. The advantage over LP+Dec. becomes much more pronounced as graph size increases: at n=500 on ER, NCP attains a cost of -395.11 while LP+Dec. reaches only -259.30.

Ablation of the NCP components on weighted maximum independent set shows that the structure certificate is essential: removing it results in the largest performance drop on IMDB and COLLAB, with ratio decreases up to 0.724 and nearly all exact solutions lost. Recovering the primal directly from the perturbation (Decoder by perturb) causes the highest ratio degradation on Twitter and competitive with certificate removal on COLLAB, confirming that the primal signal is reconstructed through the learned mapping, not from Γ alone. Learned certificate perturbations outperform random perturbations, and removing the consistency loss significantly degrades exact solve counts, highlighting the importance of certificate consistency. Removing the structure certificate slashes the ratio by 0.724 on IMDB and 0.308 on COLLAB, with exact solves dropping from 196 to 2 and from 941 to 10, respectively. Decoding directly from Γ degrades the ratio by 0.249 on Twitter and 0.409 on IMDB, causing the largest ratio loss on Twitter and reducing exact solves from 196 to 6 on IMDB. Randomizing the perturbation reduces exact solves by 912 on COLLAB and 183 on IMDB, underperforming the learned certificate perturbation and demonstrating that structured perturbations are crucial. Removing the perturbation entirely (w/o perturb) causes milder degradation (exact drop of 248 on COLLAB) than random perturbation, but still hurts performance, underscoring the need for a learned adaptation. Ablating certificate consistency leads to exact solve drops of 656 on COLLAB and 70 on IMDB, far worse than removing the perturbation, indicating that consistency guides effective primal recovery.

The evaluation spans maximum independent set (unweighted and weighted), the GAP benchmark, and path planning on synthetic graphs, validating NCP's solution quality and speed against exact solvers and neural baselines. NCP consistently achieves near-optimal results, often matching exact solvers while maintaining single-pass-like inference, and it remains robust on larger and weighted instances where other learning-based methods degrade sharply. The learned structure certificate is essential for performance, with ablations confirming that removing it or bypassing the primal recovery drastically reduces accuracy, while consistency loss further stabilizes learning. Overall, NCP delivers a compelling combination of accuracy, speed, and scalability across diverse combinatorial optimization tasks.