Neighborhoods Shaped to the Model: Decomposition Overhead Inside Large Neighborhood Search

Constraint solvers often rewrite a high-level rule, such as "these variables must all take different values," into many small rules, such as a list of pairwise inequalities. The small rules are cheap and work in any solver. They are also weaker: they miss deductions that the whole rule would catch, and on some problems this costs a million-fold blow-up in search. Large Neighborhood Search (LNS) is a local search method that repeatedly frees a subset of variables in the current solution and asks a solver to re-optimize just that subset. It is one of the most effective ways to scale constraint solvers. Nobody has asked how the weakness of a decomposition changes inside such a repair. Our central claim is that it changes sharply and predictably. The deductions a decomposition loses depend on how many variables in a global constraint's scope the neighborhood leaves free, which we call the neighborhood's free-arity on that constraint. For some constraints the loss is exactly zero below a small threshold.

This turns a fixed modelling choice into a controllable variable. If decomposition overhead is a function of the neighborhood, then an LNS loop can do two things: build neighborhoods whose free-arity profile keeps the cheap decomposed model exact, and switch to the full global propagator only for repairs where free-arity is high. We propose to measure this relationship on standard scheduling and assignment benchmarks, to build a neighborhood generator and model-switching rule around it, and to test whether it beats both "always decompose" and "always use the global propagator" inside the same LNS.

Core Claim

A global constraint is a single rule over many variables, handled by a dedicated filtering routine called a propagator. The field treats the choice between a global propagator and a decomposition as static. Direction 1 of the literature documents a large, persistent pruning gap, meaning the deductions a decomposition fails to make. Bessiere et al. frame the loss of global context. On pigeonhole problems, binary inequalities need "29 seconds and nearly a million backtracks" at $n=11$ against 0.1 seconds and 10 backtracks for a Hall-interval decomposition (Decompositions of All Different, Global Cardinality and Related Constraints). A dedicated SOFTCUMULATIVE propagator is over 10× faster than decomposition on 60–68% of instances (The SoftCumulative Constraint with Quadratic Penalty). All of these measurements come from full tree search from an empty assignment.

Inside an LNS repair, most variables are already fixed. Take ALL-DIFFERENT as the clean case. If at most two variables in its scope are free, pairwise inequality with arc consistency (the standard local filtering check) prunes exactly what the global propagator prunes. The reason is that the fixed values are simply removed from the free domains, and the remaining two-variable constraint is a binary inequality. Loss first appears at three free variables: a pair of variables sharing a two-value domain (a Hall set) forces a third to avoid those values, and pairwise reasoning cannot see this. Past that point, the gap should grow with the number of free variables whose domains overlap. We conjecture an analogous, less crisp dependence for cumulative resource constraints, where the relevant quantity is the number of free tasks whose time windows overlap. The consequence is that the pruning gap is a property of the (model, neighborhood) pair rather than of the model alone. Its size can be estimated from the neighborhood before the repair is run.

Relation to Prior Work

Three hybrid lines supply the setting but not the question. Large Neighborhood Search and Adaptive Randomized Decompositions for Flexible Jobshop Scheduling uses a CP solver to repair random, temporal and machine-based neighborhoods and grows neighborhood size when search stalls. Its CP model is described as naive, and it never measures what that naivety costs per neighborhood. A Framework for Constraint Based Local Search using Essence derives structure-aware neighborhoods from high-level models and picks among them with a bandit algorithm. It does not ask what is lost when those models are flattened into primitives. Large Neighborhood Search with Decision Diagrams replaces hand-built neighborhoods with width-bounded decision diagrams, a compact graph encoding of the candidate solutions. All three treat the repair model as fixed. We make the model and the neighborhood jointly chosen.

The closest method-level precedent is Local Search with Constraint Propagation and Conflict-Based Heuristics. Its path-repair builds neighborhoods from nogoods, which are sets of decisions that filtering proved inconsistent. It worked only over binary constraints, and it named non-minimal nogoods and filtering cost as limitations. Our proposal differs in its target. It controls when filtering is exact and cheap, rather than using conflicts to pick which variables to move. Reducing Search Space in Local Search for Constraint Satisfaction motivates us from the other side. Its island confinement keeps a hand-chosen subset of constraints hard during local search, yielding 0.88 s against 154.18 s on 100-Queens. That shows that deciding which constraint structure local moves respect matters enormously, but the subset was chosen by hand.

Two further lines constrain the design. Parallel Batch Scheduling With Incompatible Job Families Via Constraint Programming shows that decoupling assignment from scheduling makes solvers rediscover the same contradictions. This warns that neighborhoods which cut across coupled constraints may be paying a hidden gap. BTBS-LNS shows that learned LNS gets trapped by badly fixed variables and needs a second network to un-fix them. Our free-arity statistic is a structural, non-learned signal of which fixings sever a global constraint.

The parameterized hardness of finding improving paths (A Parameterized-Complexity Framework for Finding Local Optima) tells us not to expect guarantees about reaching local optima. Our claims are about per-repair propagation strength and wall-clock quality, not convergence.

Research Program

The first component is a measurement instrument. For a given benchmark we run a reference LNS, log every neighborhood it generates, and replay each repair subproblem twice under an identical search strategy and node limit. One replay uses a decomposition, either binary inequalities for ALL-DIFFERENT or a time-table decomposition for cumulative. The other uses the global propagator. For each constraint touched by the neighborhood we record its free-arity and domain-overlap statistics. We also record the node-count ratio, the ratio of time per node, and whether the repair found an improvement. This gives the empirical gap curve, meaning pruning loss as a function of free-arity, per constraint type. It also tests the exactness prediction for ALL-DIFFERENT at free-arity ≤ 2, which is a sanity check the instrument must pass.

The second component is a neighborhood generator that is aware of the decomposition. Given a target neighborhood size $k$, it samples relaxed variable sets as the existing random, temporal and machine operators do. It then rejects or reshapes samples so that the maximum free-arity on each global constraint stays below that constraint's measured "safe" threshold. It spreads freed variables across many constraints rather than concentrating them in one.

The third component is a switching rule for repairs that must have high free-arity, because diversification sometimes needs concentrated neighborhoods. For those repairs, the rule turns on the global propagator for the constraints above threshold and keeps the decomposition elsewhere. The rule is a simple threshold read off the measured curve. We deliberately do not learn it, so the effect is attributable.

Each component can be tested on its own. The instrument alone is a publishable characterization. The generator and the switching rule each correspond to one ablation arm.

Baselines

The naive reference point is LNS with the repair model always decomposed and the neighborhood operators of Large Neighborhood Search and Adaptive Randomized Decompositions for Flexible Jobshop Scheduling: random, temporal, machine-based, with adaptive size growth. This is the configuration most practitioners actually run. On the eData la21–la40 instances that paper reports reaching within 0.5% of best-known solutions in 5 minutes and improving 60% of best-known values in 60 minutes; no per-instance makespans are reported in the file. We will reimplement it in one CP solver. Our method must beat it on the same instances with the same seeds, time limits and hardware.

The strongest single competitor is the same LNS with the global propagator always on. If propagator overhead per node is small relative to the gap it closes, this simply wins, and our claim reduces to "use global propagators." It gets the same neighborhoods, time budget and tuning budget, meaning an equal number of configurations for the size-growth schedule. Beating it means a better primal integral (area under the gap-to-best-known curve over time) or final gap at equal wall-clock, not just fewer nodes.

The published result closest to our question is the SOFTCUMULATIVE comparison on KSD15_D: over 10× faster than decomposition on 68% (linear penalty) and 60% (quadratic) of instances (The SoftCumulative Constraint with Quadratic Penalty). That was measured in complete search. We will test whether the advantage shrinks inside LNS repairs as free-arity falls, which our claim predicts.

A conflict-guided baseline adapts path-repair (Local Search with Constraint Propagation and Conflict-Based Heuristics) to LNS: it relaxes the variables in the most recent failure explanation. The file reports only qualitative results for it on Taillard open shop, and no reported numbers were found on Lacuna for it on eData.

A monolithic-solver baseline is Gurobi or CP-SAT run on the full model for the same wall-clock. For context, BTBS-LNS reports a 10% better average primal gap than Gurobi 9.5.0 at 300 s on MIPLIB 2017, which shows that monolithic solvers are beatable in this regime.

Two ablations isolate the ingredients: the generator without switching, and switching with unshaped neighborhoods.

Why not just…?

Why not just always use the global propagator? This is the real threat. The complete-search evidence (SoftCumulative, Explaining Propagators for String Edit Distance Constraints, where CP with the propagator found 227 of 250 median-string optima against 180 for standard CP) all favors global propagators. The case for our method rests on two facts about repairs. Per-node propagator cost does not shrink as quickly as the pruning gap does when most of the scope is fixed. And LNS runs thousands of short repairs, where fixed overhead dominates. The replay instrument measures both quantities directly. If the time-per-node ratio is near one at all free-arities, we will report that "always global" is the right answer for LNS and drop the switching rule. The measurement itself remains the contribution.

Why not just let adaptive neighborhood sizing absorb it? Adaptive randomized decomposition already grows and shrinks neighborhoods (Pacino and Van Hentenryck). Size is not free-arity, though. A neighborhood of 20 tasks can free 2 per machine or 20 on one machine, and our claim predicts these behave differently under decomposition. The ablation holding $k$ fixed while varying the free-arity profile settles whether size is a sufficient proxy.

Why not just use a power-preserving decomposition everywhere? Hall-interval decompositions recover bound consistency for ALL-DIFFERENT and GCC (Bessiere et al.), and these are the decompositions that produced the 0.1 s pigeonhole result. They cost $O(nd^2)$ to $O(nd^3)$ per branch and add many auxiliary variables. They also do not exist for every constraint: no polynomial decomposition achieving full domain consistency for ALL-DIFFERENT is known, and cumulative lacks an equivalent. We include the Hall-interval decomposition as a third repair model on the ALL-DIFFERENT benchmarks, so it competes directly.

Why not just use conflict-guided neighborhoods instead? Explanations tell the search where the trouble is but not how expensive the repair will be. Relaxing a conflict set concentrated on one global constraint may push free-arity into the high-gap regime. The two signals can be combined, and the conflict-guided arm with and without free-arity capping tests whether they are complementary.

Proposed Experiments

We will use the flexible jobshop eData set (la21–la40, disjunctive and cumulative structure), KSD15_D resource-constrained project scheduling with soft overloads, and Taillard open shop. For ALL-DIFFERENT-heavy structure we will use pigeonhole, double-wheel graceful graphs and Latin square instances (magic-25, magic-30). For generality we will add MiniZinc Challenge models containing alldifferent or cumulative (The MiniZinc Challenge 2008-2013). The pigeonhole and graceful-graph instances will be posed as optimization or partial-completion variants so that LNS applies. Metrics are primal integral, final gap to best known at 5 and 60 minutes, repairs per second, and from the replay instrument, the node ratio and time-per-node ratio against free-arity.

The first decisive check is the exactness prediction. On ALL-DIFFERENT, the node ratio must be exactly one at free-arity ≤ 2 and rise after that. If it does not, the instrument or the theory is wrong. The second is whether the gap curve for cumulative has a usable threshold at all; if the gap is large even at low free-arity, switching loses its rationale for scheduling. The third is the head-to-head against "always global" at equal wall-clock on eData and KSD15_D. We count the method a success only if it beats that baseline in primal integral on a clear majority of instances across seeds. Matching it while also matching "always decompose" on the easy instances counts as partial success. The fourth is the fixed-$k$ ablation, which determines whether free-arity carries information beyond neighborhood size.