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.

A new MIP Heuristic based on Randomized Neighborhood Search

ANGHINOLFI, DAVIDE;PAOLUCCI, MASSIMO
2011-01-01

Abstract

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11567/282628
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact