Interior-point methods (IPMs), originally conceived in the context of linear programming have found a variety of applications in integer programming, and combinatorial optimization. This survey presents an up to date account of IPMs in solving NP-hard combinatorial optimization problems to optimality, and also in developing approximation algorithms for some of them. The surveyed approaches include non-convex potential reduction methods, interior point cutting plane methods, the generic interior point method for the semidefinite programming (SDP) problem, branch and cut approaches based on SDP relaxations, approximation algorithms based on SDP formulations, and finally methods employing successive convex approximations of the underlying combinatorial optimization problem.
Citation
AdvOL-Report No. 2004/2, Dept. of Computing & Software, McMaster University, Hamilton, Canada January 2004, revised April 2004; to appear in the GERAD 25th anniversary volume on Graph Theory and Combinatorial Optimization, edited by D. Avis, A. Hertz, and O. Marcotte, Kluwer Academic Publishers, 2005.