Minimal Conditions for Beneficial Local Search
This work provides theoretical insights into local search algorithms for combinatorial optimization, but it is incremental as it builds on existing concepts without introducing a new paradigm.
The paper investigates why neighborhood search is beneficial over blind search by identifying problem and neighborhood properties that support two novel proofs: one showing higher likelihood of improvement in a single step, and another showing greater cumulative improvement over multiple steps. Experiments on generated problem sets and a classical combinatorial optimization problem reveal that these benefits vary dramatically in practice.
This paper investigates why it is beneficial, when solving a problem, to search in the neighbourhood of a current solution. The paper identifies properties of problems and neighbourhoods that support two novel proofs that neighbourhood search is beneficial over blind search. These are: firstly a proof that search within the neighbourhood is more likely to find an improving solution in a single search step than blind search; and secondly a proof that a local improvement, using a sequence of neighbourhood search steps, is likely to achieve a greater improvement than a sequence of blind search steps. To explore the practical impact of these properties, a range of problem sets and neighbourhoods are generated, where these properties are satisfied to different degrees. Experiments reveal that the benefits of neighbourhood search vary dramatically in consequence. Random problems of a classical combinatorial optimisation problem are analysed, in order to demonstrate that the underlying theory is reflected in practice.