DROPS

Document

Short Paper

DOI: 10.4230/LIPIcs.CP.2024.39

An Investigation of Generic Approaches to Large Neighbourhood Search (Short Paper)

Authors: Filipe Souza, Diarmuid Grimes, and Barry O'Sullivan

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract

A bottleneck in the more wide-spread use of approaches such as Large Neighborhood Search is the need for domain-specific knowledge. To this end, a number of generic LNS methods have previously been proposed that automate the selection of variables in the neighborhood with the aim of reducing the expertise requirement. Recently a new generic approach, Improved Variable-Relationship Guided LNS (iVRG), was proposed that showed promising initial results. This method combines static information regarding problem structure and dynamic information from search performance in its neighborhood selection. In this work, we first show the generalisability of the approach by comparing it on two widely studied problems, car sequencing and steel mill slab, where it outperformed existing generic approaches. We then provide a detailed examination of iVRG, investigating its key components (static/dynamic information, the use of a Tournament Selection operator) to assess their individual impact and provide insight into iVRGs overall behavior.

Cite as

Filipe Souza, Diarmuid Grimes, and Barry O'Sullivan. An Investigation of Generic Approaches to Large Neighbourhood Search (Short Paper). In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 39:1-39:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{souza_et_al:LIPIcs.CP.2024.39,
  author =	{Souza, Filipe and Grimes, Diarmuid and O'Sullivan, Barry},
  title =	{{An Investigation of Generic Approaches to Large Neighbourhood Search}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{39:1--39:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.39},
  URN =		{urn:nbn:de:0030-drops-207248},
  doi =		{10.4230/LIPIcs.CP.2024.39},
  annote =	{Keywords: Combinatorial Optimization, Metaheuristics, Large Neighborhood Search (LNS), Machine Reassignment Problem, Car Sequencing Problem, Steel Mill Slab Problem}
}

Search Results

Documents authored by Souza, Filipe

An Investigation of Generic Approaches to Large Neighbourhood Search (Short Paper)

Abstract

Cite as

Thanks for your feedback!

Could not send message