Variable neighbourhood search for binary integer programming problems. (12th December 2022)

• Record Type: Journal Article
• Authors: Bentsen, Håkon; Hvattum, Lars Magnus
• Is Part Of: International journal of metaheuristics. Volume 8:Number 1(2023)
• Page Start: 1
• Page End: 26
• Publication Date: 2022-12-12
• Subjects: black-box solver -- 0-1 integer programming -- variable neighbourhood descent -- VND -- mathematical programming; Heuristic algorithms -- Periodicals; 006.3105
• Languages: English
• ISSNs: 1755-2176

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.