Heuristics with a worst-case bound for unconstrained quadratic 0–1 programming

Article type: Research Article

Authors: Palubeckis, Gintaras

Affiliations: Department of Practical Informatics, Kaunas University of Technology, 3028 Kaunas, Studentų St. 50, Lithuania

Abstract: In this paper, we present two heuristics for solving the unconstrained quadratic 0–1 programming problem. First heuristic realizes the steepest ascent from the centre of the hypercube, while the second constructs a series of solutions and chooses the best of them. In order to evaluate their worst-case behaviour We define the performance ratio K which uses the objective function value at the reference point x=1/2. We show for both heuristics that K is bounded by 1 from above and this bound is sharp. Finally, we report on the results of a computational study with proposed and local improvement heuristics.

Keywords: quadratic 0–1 programming, heuristics, performance ratio, local improvement algorithms

DOI: 10.3233/INF-1992-3205

Journal: Informatica, vol. 3, no. 2, pp. 225-240, 1992