Finding the Maximum Multi Improvement on neighborhood exploration

Neighborhood search techniques are often employed to deal with combinatorial optimization problems. Previous works got good results in applying a novel neighborhood search methodology called Multi Improvement (MI). First and best improvement are classical approaches for neighborhood exploration, while the MI has emerged due to the advance of new parallel computing technologies. The MI formalizes the concept of heuristic and exact exploration of independent moves for a given neighborhood structure, however, the advantages of an application of MI face the difficulty to select a great set of independent moves (which can be performed simultaneously). Most of the existing implementations of MI select these moves through heuristic methods, while others have succeeded in implementing exact dynamic programming approaches. In this paper, we propose a formal description for the Maximum Multi Improvement Problem (MMIP), as a theoretical background for the MI. Moreover, we develop three dynamic programming algorithms for solving the MMIP, given a solution tour for a Traveling Salesman Problem and neighborhood operators 2-Opt, 3-Opt, and OrOpt-k. The analysis suggests the rise of a new open topic focused on developing novel efficient neighborhood searches.