View article

The definition of a “good” neighborhood structure on the solution space is 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). Firstly, the procedure extracts some semantic features from a MIP compact model. Secondly, these features are used to derive automatically some neighborhood design mechanisms. Finally, the “proper mix” of such mechanisms is sought through an automatic …