Variable Intensity Local Search

Snezana Mitrovic-Minic and Abraham P. Punnen

Department of Mathematics, Surrey, Simon Fraser University, BC, Canada,
apunnen@sfu.ca snezanam@sfu.ca

Abstract. This paper considers a local search based heuristic frame-
work for solving the Mixed-Integer Programming problem (MIP) where
a general purpose MIP solver is employed to search the associated neigh-
borhoods. The associated neighborhood search problems are MIPs of
smaller sizes. The neighborhoods are explored in varying the intensity
by changing time and size parameters. This local search can be viewed as
a combination of very large scale neighborhood (VLSN) search and vari-
able neighborhood search (VNS). The approach has been implemented
to solve three integer programming problems: the generalized assignment
problem, the multi-resource generalized assignment problem, and the fa-
cility location problem. Encouraging computational results for the first
two problems are provided, while the third study is in progress.