You are here

Cost Impact Guided LNS

TitleCost Impact Guided LNS
Publication TypeConference Paper
Year of Publication2014
AuthorsLombardi, Michele, and Schaus Pierre
Conference NameCPAIOR: The Eleventh International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) techniques in Constraint Programming

InLargeNeighborhoodSearch(LNS)[14],aproblemissolved by repeatedly exploring (via tree search) a neighborhood of an incum- bent 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 pa- per, 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 il- lustrating the superiority of some of them over pure random relaxations.