Local-search based algorithm for combinatorial optimization problems

What is it about?

Crafting efficient local search algorithms requires tailored consideration of problem characteristics. We introduce the Extended Reach approach, a simple yet potent strategy for overcoming local optima encountered in best improvement local search. Applied to the linear ordering problem (LOP), traveling salesperson problem (TSP), and quadratic assignment problem (QAP), this tactic leverages two key landscape properties identified in literature.Firstly, it recognizes that local optima often reside on the fringes of their own attraction basins, suggesting that exploring second-order neighbors may lead to superior solutions within a better local optimum's attraction basin. Secondly, it acknowledges that for LOP and certain neighborhoods, solutions can be discarded without evaluation, a principle extended to TSP's 2-opt neighborhood to preemptively eliminate unnecessary evaluations. Additionally, we present efficient methods for evaluating second-order neighbors based on cost differences, substantially reducing computational overhead. Experimental validation on random and benchmark instances corroborates the efficacy of our strategy in escaping local optima, despite its simplicity.

Featured Image

Why is it important?

The proposed algorithm for overcoming local optima encountered in best improvement local search. Applied to the linear ordering problem (LOP), traveling salesperson problem (TSP), and quadratic assignment problem (QAP), this tactic leverages two key landscape properties identified in literature.