acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
optimization
Keywords:
Large Neighborhood Search, Online Learning, Combinatorial Optimization, Mixed-Integer Programming

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_mNWrOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

Dyn-LNS is a general-purpose Large Neighborhood Search (LNS) algorithm for combinatorial optimization that adapts its LNS decisions online, based on the current state of the optimization and the search dynamics. It decides which destroy operator to use, how many variables to unassign in each destroy step, and the temperature that influences whether a worse solution is accepted over the current one. The authors show that Dyn-LNS is competitive with, and mostly superior to, other non-commercial LNS baselines on both synthetic and real-world datasets.

Critical strengths

Although the authors acknowledge that Dyn-LNS does not achieve the best results for every family-size combination and metric, the results are nonetheless strong. The experiments empirically show that Dyn-LNS is the most stable method and competes for the best result in most categories, unlike any other LNS method discussed in the paper. These results are promising, as they indicate a high-performing approach that yields a high-performing general-purpose solver.

Bandit-based LNS methods already use online learning to select destroy and repair operators, but they treat the payoffs of the different operators as stationary, when in reality these payoffs are non-stationary and can change over the course of an optimization run. The authors contribute an approach that is aware of both the search state and its dynamics. Besides the destroy operator and the size of the freed variables, the method also adjusts the acceptance temperature online.

Critical weaknesses

The novelty exists in combining existing methods within the online learning-based LNS realm. The hand-designed buckets for modelling the state and the search dynamics are the most novel parts. Even though this work contains contributions, I see them only as marginal, especially since I would have liked to see experiments demonstrating that the learnable parameters do, in fact, change over time and that the method switches between operators during a run. Such experiments would offer direct evidence that the proposed mechanisms produce the intended effect. Additionally, the proposed state design is rather basic and contains information that the search is stuck but not why. No direct information about the state of the incumbent solution (which drives the search) is modelled.

In places, the paper was somewhat difficult to follow. Figure 1 gives a complete overview of the method, but it refers to buckets, which are not clearly introduced until page 4. This makes it harder to understand how this part of the method works, including the associated tables.

Questions for authors

The Random destroy operator works pretty well in practice, as you also showed in your paper. Why did you not use it in your destroy operator set? And if the reason is comparability to other methods, did you consider trying it out in order to achieve better results?

Have you tried different severity levels for the RANDOM baseline?

How many LNS iterations could your method make within the time budget?

8 comments
AuthorsOpenReview ↗

Thanks for your comment!

We sincerely appreciate the constructive suggestions and comments on our work, which have definitely helped us to enhance the paper. The following are our detailed responses to each of the reviewer's comments.

Further explain Random destroy operator(Question 1)

We thank the reviewer for pointing this out. RANDOM is already included in the Dyn-LNS operator set. Following prior work [1], we refer to this operator as “Mutation” within the operator set, but as “RANDOM” when it is used alone as a baseline (to make it more understandable). We have revised the manuscript to avoid such misunderstandings.

Different severity levels for the RANDOM baseline(Question 2)

We also compared all three fixed RANDOM severity levels with Dyn-LNS. On the eight synthetic families, the PG/PI of Dyn-LNS, RANDOM-25%, RANDOM-50%, and RANDOM-75% were:

FamilyDyn-LNSRANDOM-25%RANDOM-50%RANDOM-75%
CA-S1.79 / 153.87.29 / 474.93.70 / 244.52.47 / 195.0
CA-L2.68 / 255.27.60 / 497.43.70 / 243.72.37 / 217.9
MIS-S0.08 / 24.62.46 / 163.90.70 / 49.60.38 / 28.4
MIS-L0.01 / 30.72.62 / 177.00.73 / 52.80.35 / 31.3
MVC-S0.21 / 17.70.48 / 32.70.24 / 17.20.22 / 17.5
MVC-L0.14 / 13.10.39 / 27.30.14 / 10.70.14 / 17.4
SC-S0.80 / 73.53.21 / 206.61.38 / 105.41.09 / 104.8
SC-L0.98 / 90.54.29 / 286.31.86 / 135.41.42 / 132.4

And on MIPLIB:

DatasetDyn-LNSRANDOM-25%RANDOM-50%RANDOM-75%
MIPLIB5.80 / 504.625.10 / 1520.323.85 / 1441.821.94 / 1347.1

Higher severity generally strengthens RANDOM, but does not eliminate Dyn-LNS’s advantage. Dyn-LNS achieves lower PG and PI than all three RANDOM configurations on five synthetic families (CA-S, MIS-S, MIS-L, SC-S, and SC-L) and on MIPLIB. RANDOM-75% performs better on CA-L, while the MVC results are mixed. These results show that Dyn-LNS’s advantage, while also demonstrating that fixed random neighborhoods can remain competitive on some problem families. On MIPLIB however, while RANDOM with higher severity seems better, Dyn-LNS is significantly better than all of them.

How many LNS iterations(Question 3)

Within the allocated 3,600 s time budget, the average number of LNS iterations completed by Dyn-LNS varies across instance classes. According to our experiments, Dyn-LNS performs iterations of approximately 160 for MVC-S, 180 for MIS-S, 180 for CA-S, 150 for SC-S, 140 for MVC-L, 190 for MIS-L, 220 for CA-L, and 150 for SC-L.

Experiments showing that the learned credits change over time and the method switches operators during a run(Weakness 1)

We agree that there should be experiments showing that whether the learned credits actually evolve during a run and whether this evolution changes the actions. To answer this directly, we instrumented the five-operator Dyn-LNS controller and recorded every selection and credit update in 36 complete runs. The results show clear within-run adaptation:

FamilyCredit rangeMaximum selection probabilityOperator switches after cold start
CA-L0.4800.590153
MIS-L0.3970.603112
MVC-L0.1200.27979
SC-L0.0950.27783

The credit range is the largest within-run change observed for any fixed destroy-credit cell after the cold-start period. We observe that the learned credits do change over time and the method switches operators frequently instead of relying on a single operator. We additionally include an individual-run visualization for CA_L in Appendix H, providing a direct view of how the reward signal changes over time.

Reference

[1]Cai, Jun-Yang et al. “Balans: Multi-Armed Bandits-based Adaptive Large Neighborhood Search for Mixed-Integer Programming Problem.” International Joint Conference on Artificial Intelligence (2024).

State design is basic: it shows that the search is stuck but not why, and does not model the incumbent(Weakness 1)

We agree that our design for the state is simple, but it is a deliberate design choice to preserve sample efficiency in the online, training-free setting. Because Dyn-LNS learns from scratch within a single solve (typically hundreds of LNS iterations), adding incumbent features or more signals would multiply the credit table rows and severely reduce the updates per entry.

Empirically, our ablations confirm that this minimal state design hits an effective sweet spot: removing it (Dyn-LNS-S) degrades the performance (see in Table 3 and Table 7) whereas expanding the state granularity (Dyn-LNS-P and Dyn-LNS-C) yields no consistent improvement due to sparser updates per state (see in Table 9).

Clarify state buckets and associated credit tables in Figure 1(Weakness 2)

We thank the reviewer for pointing out this presentation gap. We agree that introducing the bucket notation (bt,bˉtb_t, \bar{b}_t) and credit tables in Figure 1 before their formal definition creates an unnecessary forward reference.

In the revised manuscript, we have improved the readability in two ways: first, when introducing the LNS loop on page 3, we now explicitly explain how the continuous search trajectory is discretized into state buckets (bt,bˉtb_t, \bar{b}_t), with explicit pointers to Sections 3.2 and 3.3; then, we expand the caption of Figure 1 to explicitly define the state buckets right away.

Reviewer_mNWrOpenReview ↗

Follow up

Thank you for the detailed answers and for the effort you put into clarifying the paper.

Q1) Thank you, this is clear to me now.

Q2) The values appear to be consistently higher than those in the main table for all methods. Could you explain where this difference comes from?

Q3) Thank you, this answers my question.

W1) I find this analysis valuable, and I would suggest moving it into the main part of the paper, since it provides direct evidence for your claims. I would also be interested in seeing how the other learned components, severity and temperature, behave over time.

Regarding the state design: do you see incorporating this as future work, or do you think it has little potential given the limitations you listed?

W2) I appreciate the effort to make this easier to understand.

Reviewer_8wH5OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Dyn-LNS is a purely online controller for large neighborhood search in mixed-integer optimization. It conditions credits on coarse progress and stagnation states, separately selects the destroy operator, destruction severity, and acceptance temperature, and updates small credit tables with recency weighting. Experiments on four synthetic families and a filtered 35-instance MIPLIB subset show improvements over several SCIP-based adaptive LNS methods, with benchmark-dependent trade-offs in final primal gap and primal integral.

Critical strengths
  • The lightweight controller adapts multiple search decisions within each solve, without offline data collection or model pretraining.
  • Experiments across synthetic families and a MIPLIB subset show useful gains over relevant adaptive LNS baselines, with supporting component ablations.
Critical weaknesses
  • Limited methodological novelty and unclear differentiation from existing online adaptive search. The method combines coarse state buckets, EWMA credit updates, Boltzmann sampling, and factorized control—largely established mechanisms. Its specific increment lies in the state-dependent, separate-table design for the three decisions, but the methodological insight beyond existing adaptive or state-aware selection remains unclear.
  • Insufficient evidence of stochastic robustness. Dyn-LNS randomly samples several control decisions, yet each instance is evaluated with only one fixed seed. The reported means and standard deviations describe variation across instances rather than repeated-run variability. The substantial gains on some tasks are encouraging, but modest average improvements, such as those over BALANS on MIPLIB, are harder to assess without repeated runs and paired uncertainty analysis.
Questions for authors
  • What is the key methodological distinction from existing online ALNS selectors?
  • How is severity defined for different neighborhoods, and under what conditions does the implementation generate and accept worsening candidates?
  • Could you provide the MIPLIB filtering counts and clarify whether any existing paired analyses or repeated-run results support the robustness of the reported gains?
  • Do PG/PI track the best-so-far or current solution? Are the units and normalization consistent between the sensitivity tables and main experiments?
8 comments
AuthorsOpenReview ↗

Thanks for your comment!

We sincerely appreciate the constructive suggestions and comments on our work, which have definitely helped us to enhance the paper. The following are our detailed responses to each of the reviewer's comments.

Key methodological distinction from existing online ALNS selectors (Weakness 1 & Question 1)

Dyn-LNS differs from existing online LNS selectors in two fundamental ways. (1) What they condition on: it conditions operator credits on real-time search progress and stagnation buckets, updating them via EWMA to track shifting operator utility (Hypothesis 1); and (2) What they learn: it decouples destroy type, destruction severity, and acceptance temperature into three independently learned credit tables at tailored state resolutions, rather than learning joint arms or following a fixed schedule (Hypothesis 2).

How is severity defined for different neighborhoods (Question 2)

We thank the reviewer for catching this important detail. Severity ρ\rho is operator-specific in how it is converted into a neighborhood. In our implementation, Mutation frees a uniformly random ρ\rho-fraction of all discrete variables; RINS frees a random ρ\rho-fraction of the discrete variables on which the incumbent and the LP-relaxation solution disagree; RENS draws a ρ\rho-fraction of the discrete variables that are fractional in the LP relaxation; Local branching uses a Hamming-ball radius kk drawn uniformly between 5% and ρ\rho of the number of binary variables; and Proximity search uses δ\delta as the required relative objective improvement (cutoff=obj−δ⋅∣obj∣\text{cutoff} = \text{obj} - \delta \cdot |\text{obj}|), with δ=ρ/10\delta=\rho / 10 (2.5%, 5% and 7.5%). In every case a larger level means a larger or more aggressive neighborhood, which is the only property the severity table relies on. In the revised manuscript, we have generalized the neighborhood formulation in Section 3 and Algorithm 1 (which previously used the mutation-style notation kt=⌈ρt∣I∣⌉k^t = \lceil \rho_t \vert{}\mathcal{I}\vert{} \rceil as a shorthand) and added these detailed descriptions to Appendix B.5.

Under what conditions does the implementation generate and accept worsening candidates (Question 2)

In the sub-MIP for Mutation, RINS and RENS, every variable outside the destroyed set is fixed to its incumbent value, so the incumbent is always feasible in the sub-MIP, but we do not pass the other variables as a warm start (and Proximity search adds a cutoff, with a slack variable). A worsening candidate therefore arises when the solver hits its time cap before it recovers a solution as good as the incumbent, or when Proximity search returns a solution through its slack variable. Such a candidate is then accepted with probability ptp_t according to Eq. 6–7; candidates that do not worsen the incumbent are always accepted.

The MIPLIB filtering counts (Question 3)

The filtering counts is as follows. We start from the 101 instances of the MIPLIB2017 collection labelled “hard”; 51 of them admit an initial incumbent within 20 s; 41 remain after removing instances on which SCIP, BALANS or another third-party package fails for reasons unrelated to the method; and 35 instances remain after the final filter, which removes those that SCIP or Gurobi can solve to optimality within one hour. These 35 instances are listed in Table 5.

Paired analyses or repeated-run results that support the robustness of the reported gains (Weakness 2 & Question 3)

We added four additional runs for each of the 35 MIPLIB instances and report five seed-indexed runs per method, yielding 350 runs for Dyn-LNS and BALANS in total.

The repeated-run results are consistent in direction across both metrics. Dyn-LNS has a lower five-seed mean PG than BALANS (5.04 ± 0.46% vs. 5.92 ± 1.19%) and a lower five-seed mean PI (548.68 ± 60.46 vs. 566.74 ± 52.37).

For the paired analysis, we first averaged the five runs within each instance and then compared the 35 matched instance-level differences. Dyn-LNS wins, ties, and loses on 23/4/8 instances for PG and 19/1/15 instances for PI. These additional runs support a favorable average trend and show that the reported gains are not based on a single lucky seed.

Do PG/PI track the best-so-far or current solution (Question 4)

We thank the reviewer for catching this important detail. PG and PI track the best-so-far (running-best) solution across all methods in our implementation, following the definition in [1]. The ambiguity stems from a notational overload in the manuscript: in Section 3, xtx^t denotes the current working solution while x∗x^* tracks the best-so-far solution; however, in Section 4.1 (Eqs. 8–9), we inadvertently reused xtx^t to denote the running-best solution at time tt. We have revised our manuscript to eliminate this ambiguity.

Consistency between the sensitivity tables and main experiments (Question 4)

We thank the reviewer for pointing this out. All tables in our paper follow a consistent within-table normalization rule where the reference f∗f^* is the best objective found among the methods compared within that table. However, upon checking our evaluation scripts, there's a scaling inconsistency in Tables 8–9: PG was reported as a raw fraction rather than a percentage (×100%\times 100\%), and PI was addtionally normalized by the time budget T=3,600sT = 3,600\text{s}. We have corrected Tables 7–8 in the revised manuscript to match the exact units of Tables 1–3 (reporting PG in %\% and unnormalized cumulative PI). The relative PI spreads and all sensitivity conclusions are completely unaffected.

Reference

[1]Berthold, Timo. "Measuring the impact of primal heuristics." Operations research letters 41.6 (2013).

Reviewer_mNWrOpenReview ↗

Follow ups

Regarding the repeated runs and paired analyses. Have you included them in the paper now?

Reviewer_pV1kOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Dyn-LNS, an online learning-based framework for Large Neighborhood Search (LNS) that adapts to evolving search dynamics without requiring offline training. The method introduces three key components: (1) a state characterization mechanism based on search progress and stagnation, (2) heterogeneous credit tables that independently control destroy operators, destruction severity, and acceptance temperature, and (3) a recency-weighted credit update strategy to adapt to changes in operator effectiveness. The authors evaluate Dyn-LNS on four combinatorial optimization problem families and 35 MIPLIB2017 instances, using Primal Gap (PG) and Primal Integral (PI) as evaluation metrics. Experimental results show that Dyn-LNS generally matches or outperforms existing SCIP-based LNS methods, including ALNS and BALANS. Ablation studies further demonstrate the contributions of state conditioning, recency-weighted updates, and heterogeneous control to the overall performance.

Critical strengths
  1. The paper addresses the limitations of state-agnostic online LNS methods by introducing a lightweight, state-aware control framework that adapts to evolving search dynamics without requiring offline training. This provides a well-motivated and practically useful solution with a relatively simple design.
  2. The paper evaluates Dyn-LNS on four synthetic problem families and 35 MIPLIB2017 instances, demonstrating competitive performance against existing SCIP-based LNS methods. The ablation studies and hyperparameter sensitivity analyses further support the effectiveness of the proposed framework, providing broad empirical validation across diverse optimization problems.
Critical weaknesses
  1. All experiments use a single random seed (Appendix B.4), making it difficult to assess the stability and statistical reliability of the reported improvements.
  2. The paper lacks comparisons with offline RL-based LNS methods and established non-stationary bandits, making it difficult to fully evaluate the advantages of the proposed online learning framework.
  3. The Dyn-LNS-H ablation changes both the factorization of control decisions and the state granularity of severity, making it difficult to isolate the contribution of independent learning.
Questions for authors
  1. Can the authors provide multi-seed results and paired statistical tests against the strongest baselines to support the reliability of the reported improvements?
  2. How does Dyn-LNS compare with established non-stationary bandit methods, such as Discounted UCB or Sliding-Window UCB? Can the authors also clarify the feasibility of comparisons with offline RL-based LNS methods?
  3. Can the authors provide an additional ablation with matched state granularity to better isolate the contribution of independent learning?
  4. How does the proposed EWMA credit update (Eq. 3) differ from the reaction-factor update in classical ALNS (Ropke & Pisinger, 2006)?
  5. Can the authors provide direct empirical evidence that operator effectiveness changes across different search stages or stagnation states (e.g., state-wise operator reward trends) to further support Hypothesis 1?
3 comments
AuthorsOpenReview ↗

Thanks for your comment!

We sincerely appreciate the constructive suggestions and comments on our work, which have definitely helped us to enhance the paper. The following are our detailed responses to each of the reviewer's comments.

Multi-seed results and paired statistical tests against the strongest baselines (Weakness 1 & Question 1)

We have evaluated Dyn-LNS and the strongest baseline, BALANS, on all 35 MIPLIB instances using five seed-indexed runs per instance and method (175 runs per method in total). Seed 1 is the original run, while seeds 2–5 are newly rerun experiments.

Across the five seeds, Dyn-LNS obtains a lower mean terminal primal gap (PG) than BALANS (5.04 ± 0.46% vs. 5.92 ± 1.19%) and a lower primal-integral score (PI) (548.68 ± 60.46 vs. 566.74 ± 52.37). The reported standard deviations are computed across the five seed-level MIPLIB averages.

For the paired analysis, we first averaged the five runs within each instance and then compared the 35 matched instance-level differences. Dyn-LNS wins, ties, and loses on 23/4/8 instances for PG and 19/1/15 instances for PI. The mean paired differences (Dyn-LNS − BALANS) are −0.884 % for PG and −18.060 for PI. Two-sided exact paired sign-flip tests yield p=0.224p = 0.224 for PG and p=0.494p = 0.494 for PI.

Thus, although the two-sided test results are not significant under p=0.05p=0.05, the multi-seed MIPLIB results show a favorable overall trend for Dyn-LNS against the baseline BALANS.

Comparisons with established non-stationary bandit methods, such as Discounted UCB or Sliding-Window UCB, and comparisons with offline RL-based LNS methods (Weakness 2 & Question 2)

We thank the reviewer for suggesting these additional comparisons. [1] reports that IL-LNS outperforms RL-LNS on several benchmarks, while CL-LNS achieves stronger overall anytime performance, so we implemented and evaluated IL-LNS and CL-LNS as representative offline-trained LNS baselines rather than RL-based LNS to measure the distance between our method with the offline methods.

We also implemented Discounted UCB and Sliding-Window UCB[2], using γ=0.99,T=100\gamma=0.99, T=100 and ξ=0.6\xi=0.6. The following table reports the PG/PI results:

DatasetDyn-LNSD-UCBSW-UCBIL-LNSCL-LNS
CA_S1.524 / 138.052.389 / 218.712.386 / 211.280.751 / 66.040.172 / 21.11
CA_L2.585 / 249.773.473 / 365.182.594 / 338.240.747 / 90.160.091 / 20.41
MIS_S0.009 / 20.310.937 / 116.180.451 / 89.420.032 / 13.100.005 / 4.29
MIS_L0.008 / 30.460.880 / 125.270.412 / 98.550.173 / 41.200.002 / 8.22
MVC_S0.154 / 14.210.252 / 23.240.227 / 21.330.099 / 6.980.117 / 7.55
MVC_L0.097 / 10.480.270 / 24.190.237 / 23.450.073 / 6.700.007 / 1.35
SC_S0.764 / 71.410.593 / 61.580.521 / 57.372.722 / 229.870.433 / 118.15
SC_L0.951 / 88.621.220 / 91.531.100 / 94.361.847 / 143.920.946 / 86.87

(1) Comparison with non-stationary bandits: Dyn-LNS outperforms both D-UCB and SW-UCB on 7 out of 8 datasets in both PG and PI, confirming that explicit state conditioning adapts to search more effectively than passive discounting or sliding windows alone.

(2) Trade-off against offline-trained methods: Remarkably, without any offline training, Dyn-LNS outperforms IL-LNS on half of the benchmarks (MIS-S/L, SC-S/L), while CL-LNS achieves the best overall performance on these homogeneous synthetic families. However, both IL-LNS and CL-LNS require collecting expert demonstrations over 1,024 instances (taking ~30 wall-clock hours on a parallel cluster to collect labels across 1,024 training instances per family) and training separate family-specific networks. Dyn-LNS eliminates this massive offline procedure, offering a competitive, training-free alternative.

References

[1]Huang, Taoan, et al. "Searching large neighborhoods for integer linear programs with contrastive learning." International conference on machine learning (2023).

[2]Garivier, Aurélien, and Eric Moulines. "On upper-confidence bound policies for switching bandit problems." International conference on algorithmic learning theory (2011).

An additional ablation with matched state granularity (Weakness 3 & Question 3)

To isolate the effect of independent learning, we implement Dyn-LNS-MG (matched granularity). Dyn-LNS-MG uses the same six severity states and update rate as Dyn-LNS-H, while maintaining separate learning tables for destroy operators and severity levels. The results are:

DatasetDyn-LNSDyn-LNS-HDyn-LNS-MG
CA_L0.546 / 77.571.271 / 103.400.679 / 80.39
MIS_L0.143 / 23.130.131 / 23.920.148 / 23.00
MVC_L0.081 / 5.690.092 / 6.550.083 / 6.38
SC_L0.503 / 36.950.761 / 46.620.717 / 45.59
MIPLIB1.292 / 353.494.046 / 512.711.873 / 641.23

The numerical values differ slightly from those in the paper because these results use a common Best-Known-Solution computed from Dyn-LNS and all four ablation variants. It shows that independent learning contributes to Dyn-LNS. We also note that the original Dyn-LNS remains the strongest method in the ablation study.

How EWMA credit update (Eq. 3) differ from the reaction-factor update in classical ALNS (Question 4)

Mathematically, Eq. (3) shares the same exponential-smoothing form as the reaction-factor update in classical ALNS[1], and we do not claim the EWMA formula itself as a standalone novelty. Instead, Eq. (3) is introduced in modern bandit-based MIP LNS selectors.

Compared to the classical ALNS reaction-factor update, our credit update differs in: (i) State-local selectivity: Eq. (3) updates only the visited state-bucket entry across three tables; (ii) Per-iteration responsiveness: updates are applied immediately after each step rather than at 100-iteration segment boundaries; (iii) Heterogeneous rates: we assign table-specific recency weights (λd=0.15,λρ=λτ=0.05\lambda_d=0.15, \lambda_\rho=\lambda_\tau=0.05) matched to each decision's bucket resolution.

Direct empirical evidence that operator effectiveness changes across different search stages or stagnation states (Question 5)

We agree that there should be direct evidence that operator effectiveness is non-stationary. We reevaluated 12 large instances with three random seeds each, resulting in 36 complete runs, to analyze the observed reward received by each destroy operator across the whole run.

The following table reports the mean observed reward in each phase:

FamilyMutationRINSRENSLocal BranchingProximity
CA-L0.715 → 0.535 → 0.2440.511 → 0.341 → 0.1650.457 → 0.306 → 0.1260.388 → 0.253 → 0.1430.323 → 0.222 → 0.105
MIS-L0.538 → 0.383 → 0.2180.465 → 0.214 → 0.1310.427 → 0.228 → 0.1330.354 → 0.157 → 0.1250.248 → 0.142 → 0.112
MVC-L0.208 → 0.125 → 0.1090.227 → 0.109 → 0.1060.208 → 0.119 → 0.1000.145 → 0.100 → 0.1040.120 → 0.100 → 0.100
SC-L0.150 → 0.113 → 0.1160.152 → 0.100 → 0.1000.132 → 0.100 → 0.1000.126 → 0.104 → 0.1000.308 → 0.100 → 0.103

The three values in each cell correspond to early, middle, and late search phases, supporting that operator effectiveness changes across all phases. We additionally include an individual-run visualization for CA_L in Appendix H, providing a direct view of how the reward signal changes over time.

Reference

[1] Ropke, Stefan, and David Pisinger. "An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows." Transportation science (2006).

Dear Reviewer,

Thank you again for your thoughtful review. We have provided detailed responses to your comments and added experiments to address your concerns. As the discussion deadline is approaching, we would greatly appreciate any further feedback you may have, particularly on whether our responses and new results address your main concerns. We would be happy to clarify any remaining questions.

Thank you for your time and consideration.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Revision Summary

We thank the reviewers for their time and constructive suggestions. We have revised the manuscript to incorporate the clarifications and additional evidence discussed in our rebuttal. The main revisions are summarized below.

On readability:

  • We clarified the relationship between state buckets and their associated credit tables in Figure 1, adding explanations and references to the relevant subsections in the caption.
  • We resolved the notational ambiguity between the current search solution xtx^t in Section 3 and the best-so-far solution x∗,tx^{*,t} used for evaluation in Section 4. We also revised the numerical scaling of PG and PI in Tables 8–9.
  • We added Appendix B.5 to explain how severity maps to an operator-specific neighborhood size or perturbation strength for each of the five destroy operators.

On solidity:

  • We added Appendix F, reporting repeated runs and paired analyses of Dyn-LNS and BALANS across five seeds on 35 MIPLIB instances. Dyn-LNS achieves lower mean PG and PI when averaged across seeds, extending the favorable trend beyond the original single-seed evaluation.
  • We added empirical evidence supporting Hypothesis 1 in Figure 3 (Section 4.4) and Appendix H (Figures 7). These analyses show how observed destroy-operator rewards vary across search stages and how the corresponding credit estimates evolve during search. We also extended the mechanism analysis to severity and temperature in Appendix H (Figures 8–10).
  • We added Dyn-LNS-MG to the ablation studies in Section 4.3 and Appendix D. This variant retains separate learning while matching the severity state granularity and update rate of Dyn-LNS-H, enabling a more controlled comparison of separate and joint learning. We updated the ablation results and discussion to address the contributions of state conditioning, recency weighting, and separate learning.
  • We added an extended comparison of twelve methods across all eight synthetic datasets in Appendix B.6 (Table 6), including IL-LNS, CL-LNS, D-UCB, and SW-UCB alongside the original eight methods. We also added descriptions of the additional baselines in Appendix B.4.
AuthorsOpenReview ↗

Clarifying the Research Contribution

We thank the reviewers for their thoughtful comments and would like to clarify the research contribution connecting our framework, mechanism analyses, and performance experiments. Our paper studies how to adapt multiple LNS control decisions to the evolving dynamics of an individual search, using feedback collected during that search. The decisions include the destroy operator, destruction severity, and acceptance temperature. Their effectiveness depends on the current search context, while the limited number of observations within a solve constrains how much the controller can learn.

The central contribution is a unified online control framework that combines state conditioning, heterogeneous decision resolution, and recency-weighted learning. Search progress and stagnation provide a compact description of the search context. Separate credit tables allow destroy operators, severity, and temperature to adapt at different state resolutions. Recency-weighted updates allow these estimates to respond to changing rewards. Together, these choices balance context specificity with the amount of feedback available for each estimate.

The mechanism analyses examine the empirical motivation for this design. Figure 3 and Appendix H show that observed rewards vary across search stages and that credit estimates evolve during search. These observations document adaptation under the joint search policy and support investigating state-dependent, non-stationary control.

The ablation experiments address that complementary question. Removing state conditioning or recency weighting tests their contributions to solution quality. The additional Dyn-LNS-MG variant retains separate learning while matching the severity state granularity and update rate of the joint-learning variant Dyn-LNS-H. This comparison helps distinguish the contribution of separate learning from differences in those two design choices.

Finally, the synthetic and MIPLIB comparisons assess the practical value of the combined framework. The extended twelve-method comparison includes offline-trained and non-stationary bandit baselines, while the repeated MIPLIB evaluation examines performance across five seeds. These experiments support the usefulness of the proposed design within the tested settings.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.