Title: Variable neighbourhood search for binary integer programming problems

Authors: Håkon Bentsen; Lars Magnus Hvattum

Addresses: Faculty of Logistics, Molde University College, Norway ' Faculty of Logistics, Molde University College, Norway

Abstract: General solvers exist for several types of optimisation problems, with the commercially available solvers for mixed integer programming (MIP) being a prime example. Although binary integer programming (BIP) can be used to model a wide variety of important combinatorial optimisation problems, relatively few contributions have been made to develop heuristic algorithms for BIP. This paper examines whether variable neighbourhood search can be successfully used to tackle BIP instances, when avoiding very large neighbourhoods explored by the means of external MIP solvers. The results indicate that methods based on variable neighbourhood search are more successful than exact and heuristic commercial solvers on certain types of instances, while the opposite holds true on others. A general variable neighbourhood search proves very effective on instances with up to 200 variables, in particular some instances that are tightly constrained.

Keywords: black-box solver; 0-1 integer programming; variable neighbourhood descent; VND; mathematical programming.

DOI: 10.1504/IJMHEUR.2022.127813

International Journal of Metaheuristics, 2022 Vol.8 No.1, pp.1 - 26

Received: 12 Oct 2020
Accepted: 02 Oct 2021
Published online: 19 Dec 2022 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article