Model-based automatic neighborhood design by unsupervised learning

Gianpaolo Ghiani, Gilbert Laporte, Emanuele Manni

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

Abstract

The definition of a suitable neighborhood structure on the solution space is a key step when designing a heuristic for Mixed Integer Programming (MIP). In this paper, we move on from a MIP compact formulation and show how to take advantage of its features to automatically design efficient neighborhoods, without any human analysis. In particular, we use unsupervised learning to automatically identify "good" regions of the search space "around" a given feasible solution. Computational results on compact formulations of three well-known combinatorial optimization problems show that, on large instances, the neighborhoods constructed by our procedure outperform state-of-the-art domain-independent neighborhoods.

Original languageEnglish
Pages (from-to)108-116
Number of pages9
JournalComputers and Operations Research
Volume54
DOIs
Publication statusPublished - Feb 2015

Keywords

  • Mixed integer programming
  • Neighborhood search
  • Unsupervised learning

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Model-based automatic neighborhood design by unsupervised learning'. Together they form a unique fingerprint.

Cite this