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 research line, we move on from a MIP compact formulation and try to take advantage of its features to automatically design efficient neighborhoods, without any human analysis.
A first contribution in this sense is given by:
G. Ghiani, G. Laporte, E. Manni (2015) “Model-based automatic neighborhood design by unsupervised learning”. Computers and Operations Research 54, 108–116.
In my PhD activities I’ve been co-author of these other contributions:

  • G. Ghiani, T. Adamo, A. Grieco, E. Guerriero, E. Manni (2017) “MIP neighborhood synthesis through semantic feature extraction and automatic algorithm configuration”, Computers & Operations Research 
    We deal with the definition of a “good” neighborhood structure on the solution space, a key step when designing several types of heuristics for Mixed Integer Programming (MIP). Typically, in order to achieve efficiency in the search, the neighborhood structures need to be tailored not only to the specific problem but also to the peculiar distribution of the instances to be solved (reference instance population). Nowadays, this is done by human experts through a time-consuming process comprising: (a) problem analysis, (b) literature scouting and (c) experimentation. In this paper, we illustrate an Automatic Neighborhood Design algorithm that mimics steps (a) and (c). In particular, it extract some semantic features from a MIP compact model. These features are then used to derive automatically some neighborhood design mechanisms. Finally, the “proper mix” of such mechanisms is defined through an automatic configuration phase perfomed on a training set representative of the reference instance population. When assessed on four well-known combinatorial optimization problems, our automatically-generated neighborhoods outperforms state-of-the-art domain-independent neighborhoods with respect to both scalability and solution quality.
  • G. Ghiani, T. Adamo, T. Calogiuri, A. Grieco, E. Guerriero, E. Manni (2016) “Neighborhood synthesis from an ensemble of MIP and CP models”, Lecture Notes in Computer Science, DOI: 10.1007/978-3-319-50349-3_15 In book: Learning and Intelligent Optimization, pp.221-226
    We describe a procedure that automatically synthetises a neighborhood from an ensemble of Mixed Integer Programming (MIP) and/or Constraint Programming (CP) models. Here, we extend the previous work in order to generate a suitable neighborhood from an ensemble of MIP and/or CP models of a given combinatorial optimization problem. Computational results show relevant improvements over the previous approach.
  • G. Ghiani, T. Adamo, E. Guerriero, E. Manni (2017) “Automatic instantiation of a Variable Neighborhood Descent from a Mixed Integer Programming model”, Operations Research Perspectives
    We describe the automatic synthesis of a Variable Neighborhood Descent (VND) procedure from a Mixed Integer Programming (MIP) model. We move on from a recent paper of ours in which a neighborhood structure is automatically designed from a MIP model. Here, we extend the previous work in order to synthesize automatically an entire VND algorithm from a MIP model. Computational results show relevant improvements over previous model-derived VND procedures.
  • G. Ghiani, T. Adamo, E. Guerriero, E. Manni (2018) “A learn-and-construct heuristic for general mixed-integer programming problems”, International Transactions in Operational Research DOI:10.1111/itor.12578
    In this paper we propose a new method for finding an initial feasible solution from a mixed-integer programming model. We call it learn-and-construct since it first exploits the structure of the model and its linear relaxation solution and then uses this knowledge to try to produce a feasible solution. In the learning phase, we use an unsupervised learning algorithm to cluster entities originating the MIP model. Such clusters are then used to decompose the original MIP in a number of easier sub-MIPs that are solved by using a black-box solver. Computational results on three well-known problems show that our procedure is characterized by a success rate larger that the Feasibility Pump heuristic embedded into CPLEX. Furthermore, our approach is more scalable and uses less time on average.
  • Ejection chain moves for automatic neighborhood synthesis in constrained cardinality-minimization problems,10.1111/itor.12643. – In this paper, we deal with the problem of automatically synthesizing “good” neighborhoods for a specific class
    of problems, namely constrained cardinality-minimization problems.

We are about to submit for publication some more papers on this subject. Stay tuned !