Potential reduction algorithms for structured combinatorial optimization problems

J.P. Warners, T. Terlaky, C. Roos, B. Jansen

Recently Karmarkar proposed a potential reduction algorithm for binary feasibility problems. In this paper we point out a practical drawback of his potential function and we propose a modified potential function that is computationally more attractive. As the main result of the paper, we will consider a special class of binary feasibility problems, and show how problems of this class can be reformulated as nonconvex quadratic optimization problems. The reformulation is very compact and a further interesting property is, that (instead of just one) multiple solutions may be found by optimizing it. We introduce a potential function to optimize the new model. Finally, we report on computational results on several instances of the graph coloring problem, comparing the three potential functions.

Report 95-88, Faculty of Technical Mathematics and Informatics, Delft University of Technology, Delft, 1995.

Contact: [email protected]