- 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
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 () 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 (), 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.
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.
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:
And on MIPLIB:
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:
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).