ABSTRACT
A combinatorial optimization problem (COP) P consists of a collection of its instances. An instance of P can be represented as an ordered pair (F, f), where F is the family of feasible solutions and f is the objective function, which is used to compare two feasible solutions. Very largescale neighborhood (VLSN) search algorithmsearch algorithms have been successfully applied to solve various optimization problems of practical interest. Researchers have used various techniques for developing good neighborhood functions that lead to effective VLSN search algorithms. This includes multi-exchange ejection chains, variable depth methods, integer programming, weighted matching set partitioning and so on. One of the most important theoretical questions in VLSN search (and local search in general) is to find a good bound on the number of improvement steps required to reach termination. In addressing this important theoretical question, Johnson et al. introduced the complexity class PLS.
