An Interior Point Approximation Algorithm for a Class of Combinatorial Optimization Problems: Implementation and Enhancements

Non-convex quadratic minimization on a special projection of a hypercube models a large class of combinatorial optimization problems. It makes it possible to arrive at small neighbourhood of a binary local minimizer using a quadratic programming method and then employ a rounding heuristic to actually get such a minimizer. In this paper we describe an implementation of an approximation algorithm designed along the lines just mentioned. We report on its performance on real-life instances, such as Frequency Assignment Problems (FAP). For the latter, a number of preprocessing techniques is described. A new optimality result for a certain CELAR FAP is given. As well, we give performance indications for our implementation on a number of well-known benchmark problems, such as the n-queens problem and graph colouring problems. Roughly a 100-fold performance increase over the earlier implementations is observed. Directions for future development of our approach are discussed, as well. 1 Introdu..