Interior Point Approximation Algorithm for a Class of Combinatorial Optimization Problems: Implementations and Enhancements.

摘要

A large class of combinatorial optimization problems can be formulated as a non-convex quadratic minimization on a special projection of a hypercube. Using a quadratic programming method on such a model, it is possible to arrive at a small neighborhood of a binary local minimizer and then employ a rounding heuristic to try to find it. In this paper we describe an implementation of an approximation algorithm designed along these lines. We report on its performance on real-life instances, such a 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 coloring problems. Roughly a 100-fold performance increase over the earlier implementations is observed. Directions for future development of our approach are discussed, as well.