On convergence of scatter search and star paths with directional rounding for 0–1 mixed integer programs

Scatter Search is an evolutionary metaheuristic introduced by Glover (1977) as a heuristic for integer programming and was joined with a directional rounding strategy for 0–1 Mixed Integer Programming (MIP) problems based on Star Paths in Glover (1995). In this paper, we address directional rounding both independently and together with these other algorithmic components, studying its properties as a mapping from continuous to discrete (binary) space. We establish several useful properties of directional rounding and show that it provides an extension of classical rounding and complementing operators. Moreover, we observe that directional rounding of a line, as embodied in a Star Path, contains a finite number of distinct 0–1 points. This property, together with those of the solution space of 0–1 MIP, enables us to organize the search for an optimal solution of 0–1 MIP problems using Scatter Search in association with both cutting plane and extreme point solution approaches. Building on this, we provide a Convergent Scatter Search algorithm for 0–1 Mixed Integer Programs with proof of its finite convergence, along with two variants of its implementation and examples that illustrate the running of the approach.