Model-based automatic neighborhood design by unsupervised learning

Gianpaolo Ghiani, Gilbert Laporte, Emanuele Manni

Research output: Contribution to journalArticlepeer-review

8 Citations (SciVal)


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
Publication statusPublished - Feb 2015


  • Mixed integer programming
  • Neighborhood search
  • Unsupervised learning

ASJC Scopus subject areas

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


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

Cite this