A new MIP Heuristic based on Randomized Neighborhood Search

A new simple MIP heuristic, called Randomized Neighborhood Search (RANS) is proposed, whose purpose is to produce within short time bounds high quality solutions especially for large size MIP problems as the ones characterizing real industrial applications. Starting from starts from a feasible incumbent solution RANS iterates solutions' neighborhood exploration randomly defined by calling a MIP solver as a black box tool. RANS rationale is similar to the one of other MIP heuristics recently appeared in literature but, differently, it exploits only a randomization mechanism to guide the MIP solver. RANS has some self-tuning rules so that it needs as single input parameter the maximum computation time. RANS also includes a procedure for generating the first incumbent solution based on the same randomization concepts, that can be used as an initialization alternative for particularly hard instances. RANS effectiveness is shown by an experimental comparison with other MIP heuristics.