Cost impact guided LNS

Lombardi, Michèle [University of Bologna] Schaus, Pierre [UCL]

In Large Neighborhood Search (LNS) [14], a problem is solved by repeatedly exploring (via tree search) a neighborhood of an incumbent solution. Whenever an improving solution is found, this replaces the current incumbent. LNS can improve dramatically the scalability of CP on large real world problems, provided a good neighborhood selection heuristic is available. Unfortunately, designing a neighborhood heuristic for LNS is still largely an art and on many problems beating a random selection requires a considerable amount of both cleverness and domain knowledge. Recently, some authors have advocated the idea to include in the neighborhood the variables that are most directly affecting the cost of the current solution. The proposed approaches, however, are either domain dependent or require non-trivial solver modifications. In this paper, we rely on constraint propagation and basic solver support to design a set of simple, cost based, domain independent neighborhood selection heuristics. Those techniques are applied on Steel Mill Slab problems illustrating the superiority of some of them over pure random relaxations.