Dyn-LNS: Online Learning-Based Adaptive Control for Large Neighborhood Search with Evolving Search Dynamics

The performance of Large Neighborhood Search (LNS) depends critically on a series of interdependent control decisions, including the configuration of destroy or repair operators, and the solution acceptance rule. However, the effectiveness of these decisions may change substantially as the search progresses, whereas existing online selection methods typically rely on globally stationary performance estimates and remain state-agnostic. Another class of methods that account for such dynamic evolution generally depends on policies pretrained offline, which incurs substantial training costs and often leads to poor generalization ability. To address this gap, we propose Dyn-LNS, a general online learning-based control framework that dynamically adapts LNS decisions to the evolving search dynamics. The proposed method comprises three key techniques: 1) a state characterization mechanism based on bucket partitioning, capable of capturing search progress and stagnation without offline pre-training; 2) heterogeneous credit tables that enable independent adaptive adjustment of destroy operators, destruction severity, and acceptance temperature at a state-specific decision resolution; and 3) a recency-weighted credit update strategy that allows operator credit values to dynamically increase or decay over the course of the search process. We evaluate Dyn-LNS on representative combinatorial optimization (CO) and mixed integer programming (MIP) problems, using primal gap (PG) and primal integral (PI) as metrics. Experiments demonstrate that Dyn-LNS generally matches or outperforms existing adaptive LNS strategies across the tested benchmarks. Ablation studies further analyze the individual contributions of state conditioning, non-stationary credit estimation, and heterogeneous control.