Eliminating Auxiliary Variables to Remove Saddles in Relaxed Constraint Decompositions

Constraint solvers handle rules like "these variables must all take different values" or "exactly $N$ distinct values may be used" in one of two ways. A specialised algorithm can reason about the rule as a whole. Alternatively, the rule can be broken into many small arithmetic pieces that a general-purpose solver understands. The best decompositions avoid losing reasoning power by adding helper ("auxiliary") variables that pass information between the pieces, such as counters for how many variables land in each value interval. The same decompositions are increasingly relaxed into continuous objectives and optimised by gradient methods. This happens when they serve as search heuristics, as differentiable constraint layers, or as soft penalties. In that continuous setting, every helper variable adds dimensions to the space the optimiser must explore.

We propose that the helper variables which make discrete decompositions strong are the same ones that create flat regions and saddle points (places where the gradient vanishes but the point is not a minimum) once the model is relaxed. We further propose that minimising them out exactly, as an inner problem, keeps the tight relaxation while removing those traps. The proposal builds on A Saddle Point Remedy: Power of Variable Elimination in Non-convex Optimization. That paper shows that eliminating a block of variables of guaranteed positive curvature turns saddles into points that gradient descent leaves immediately. It establishes this only for separable models such as matrix factorisation and small networks. Our test case is the pyramid of counting variables from Decomposition of the NVALUE constraint, which is a natural, combinatorially structured instance of such a block.

Core Claim

Relax a global constraint into a continuous objective over soft assignments $P$. Row $i$ of $P$ is a probability vector over the values of variable $i$. Collect the decomposition's auxiliary variables in $z$: "value $v$ is used" indicators $y_v$ and interval counts $M_{lu}$. The rules linking $z$ to $P$ and to each other are imposed by convex penalties with weight $\rho$, giving an objective $F(P,z)$. Our claim concerns the reduced objective $$\Phi(P)=\min_{z} F(P,z).$$

Three properties should hold for the NVALUE pyramid. First, $F$ is convex in $z$ for fixed $P$. The inner problem then has a tree structure that a bottom-up pass over the interval pyramid can solve exactly, so $\Phi$ and its gradient (by Danskin's theorem) cost about as much as one sweep of the pyramid. Second, wherever $\Phi$ is twice differentiable, its Hessian is the Schur complement of the $zz$ block of the joint Hessian of $F$. By the Haynsworth inertia additivity argument used by Gan et al., every negative curvature direction of the joint landscape survives, while the many positive or flat auxiliary directions disappear. Third, the reduced landscape keeps the same interval inequalities that give the discrete decomposition bound consistency, a level of reasoning that checks only the smallest and largest values each variable can take. As a result, it should be as tight as the joint relaxation while making gradient methods stall less often.

There is an important control case. For the Hall-interval decomposition of all-different in Decompositions of All Different, Global Cardinality and Related Constraints, the auxiliary variable $A_{ilu}$ is a linear function of $P$, namely the sum of $P_{iv}$ over $v\in[l,u]$. Eliminating it is plain substitution. We therefore predict no benefit from elimination over substitution there, and we use this as a negative control. The claim has real content only where the link between helper and primary variables is nonlinear, as with the max-type "value used" indicators and the hierarchical counts of NVALUE and the global cardinality constraint (GCC).

Research Program

The first part is an analysis. We will write out the penalty relaxation of the NVALUE pyramid, characterise the inner problem as a projection onto a tree-structured polytope, and give the exact dynamic-programming solver and its gradient. We will then state conditions under which $\Phi$ is smooth almost everywhere. Following Gan et al., we will prove that any strict saddle of $F$ maps to a point of $\Phi$ whose negative curvature is at least as large, while the number of near-zero curvature directions drops by the auxiliary dimension. One honest caveat is that $\Phi$ is only piecewise smooth where the max inside "value used" switches. This kink is exactly where a smoothed or entropic variant may be needed, and we will compare the hard and log-sum-exp versions.

The second part is a measurement study. For each instance we will run gradient descent, perturbed gradient descent from How to Escape Saddle Points Efficiently, and YOGI from Adaptive Methods for Nonconvex Optimization on both the joint objective $F$ and the reduced objective $\Phi$. At every stall point (gradient norm below a threshold), we will estimate the smallest Hessian eigenvalue using Lanczos iterations on Hessian-vector products, the same primitive used in Finding Approximate Local Minima for Nonconvex Optimization in Linear Time. This tells us directly whether failures are saddle stagnation, spurious minima, or slow progress on plateaus. The diagnostic is what turns the hypothesis "decomposition creates saddles" from a guess into a measured fact.

The third part is downstream use. Following Constraint Satisfaction as Global Optimization, which used gradient ascent on a continuous relaxation to order values during backtracking, we will feed the relaxed solution into a discrete solver as a value-ordering heuristic. This tests whether faster and more reliable continuous convergence buys anything that matters to combinatorial search.

Baselines

The do-nothing reference is the relaxation of the naive binary-inequality decomposition, with pairwise penalties forbidding $P_i$ and $P_j$ from placing mass on the same value, optimised by plain gradient descent. This relaxation is weak by construction. On pigeonhole instances it admits fractional "solutions" that hide the infeasibility, so it calibrates how much the stronger decompositions help at all.

The main ablation isolates our key ingredient. It uses the identical pyramid penalty $F$, data, initialisations and iteration budget, optimised jointly over $(P,z)$. The only difference from our method is whether $z$ is minimised out. Each optimiser gets the same per-run hyperparameter search (step size, perturbation radius, $\rho$), sized to equal wall-clock time rather than equal iterations, because one evaluation of $\Phi$ costs a pyramid sweep. Beating this ablation means a higher fraction of runs reaching a rounded feasible or optimal assignment at equal wall-clock time, together with stall points showing more negative curvature. Equal success at higher cost would count as a loss.

The strongest continuous competitor is a primal-dual treatment of the same linking constraints, in the style of the gradient primal-dual algorithm and gradient ADMM. Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solution for Nonconvex Distributed Optimization Over Networks proves these methods reach second-order stationary points almost surely, though without a rate and only for linear equality constraints. We will apply it to the linear pyramid sum constraints, keep the "value used" inequalities as penalties, and give it the same tuning budget. Beating it means fewer iterations and fewer failures at matched time. No reported result was found on Lacuna for any continuous method on these benchmarks.

The strongest discrete reference is the Hall-interval and pyramid decompositions inside a pseudo-Boolean or CP solver. Bessiere et al. report the double-wheel graceful graph $DW_{10}$ solved in 2.1 seconds with the $HI_5$ decomposition, versus over 118 seconds for binary inequalities, and pigeonhole $n=11$ in 0.1 seconds with 10 backtracks. Narodytska et al. report PyramidBC needing 256,582 backtracks on the $n=8$ queen's-graph dominating set, versus 390,717 for naive decompositions, and 58 seconds where the GCC method took 8,568. We do not expect a continuous method to beat these solvers outright. Our target is to reduce the backtracks of the pyramid-based solver when our relaxation supplies value ordering, at equal total time including relaxation cost.

Why not just…?

Why not just substitute the auxiliary variables away instead of solving an inner problem? For the Hall-interval decomposition this is correct, and our control experiment is designed to show that elimination and substitution coincide there. For NVALUE, the "value used" variable is a maximum over assignments, and the interval counts are chained sums of these maxima. Substitution then yields a deeply nested nonsmooth expression whose gradient is nonzero only along the currently maximal entries. Substitution is in fact one possible way to compute $\Phi$, so it is not a rival method; the question is whether to evaluate it by naive autodiff through nested maxima or by the exact tree solve. We will run both, and if naive substitution with smoothing matches the tree solve, we will report that the contribution reduces to the curvature analysis.

Why not just run perturbed gradient descent or YOGI on the joint objective? This is the most serious threat, because escape time for perturbed gradient descent grows only polylogarithmically with dimension. Adding auxiliary dimensions might therefore cost little. The counterargument is that the bound depends on the curvature gap and on flatness, not on dimension alone, and Gan et al. found that elimination beat joint optimisation by many orders of magnitude in residual error on separable networks. The stall-point eigenvalue measurements under matched wall-clock time settle this directly. If perturbed descent on $F$ matches $\Phi$, the claim fails.

Why not just use the monolithic propagator or a discrete solver and skip relaxation? For pure satisfiability this is the right tool, and the reported numbers above show that decomposed discrete models are already fast. Relaxations earn their place only as heuristics, as soft or penalised variants, or as differentiable layers. Our downstream evaluation is accordingly framed as improving the discrete solver's search, not replacing it. If the heuristic does not reduce backtracks net of its cost, the practical case collapses even if the landscape result holds.

Proposed Experiments

The benchmarks are those with reported discrete results. We will use queen's-graph dominating sets for $n$ from 5 to 10 and random binary CSPs at the phase transition with an NVALUE side constraint (500 instances, 600-second timeout, as in Narodytska et al.) as the main NVALUE testbed. Pigeonhole and double-wheel graceful graphs serve as the all-different control where elimination equals substitution. A GCC variant of the random CSPs extends the nonlinear case.

The metrics are fraction of runs reaching a feasible rounded assignment, wall-clock time to that point, and smallest Hessian eigenvalue and count of near-zero eigenvalues at stalls. For the downstream use, the metrics are backtracks and runtime of the pyramid-based discrete solver with and without our value ordering. On unsatisfiable pigeonhole instances, the residual penalty at convergence is an additional metric, since a strong relaxation should leave a strictly positive residual that certifies overload.

Three outcomes are decisive. First, on NVALUE, the joint objective should show stalls with many near-zero eigenvalues that disappear under elimination, accompanied by higher success at equal time against perturbed descent, YOGI and the primal-dual method. Second, on all-different, elimination and substitution should give indistinguishable results, confirming that the effect comes from nonlinear helper variables and not from implementation differences. Third, the elimination-based heuristic should reduce backtracks on the queen's graph relative to the 256,582 reported for PyramidBC at $n=8$, counting relaxation time.

If the first outcome appears without the third, we have a landscape result without practical value, and we will report it as such. If perturbed descent on the joint objective already succeeds, the hypothesis that decomposition creates harmful saddles is refuted for this class of constraints.