Interior Point and Semidefinite Approaches in Combinatorial Optimization

Kartik Krishnan (kartikcaam.rice.edu)
Tamas Terlaky (terlakymcmaster.ca)

Abstract: 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.

Keywords: Interior Point Methods, Semidefinite Programming, Combinatorial Optimization, Approximation Algorithms, Branch and cut approaches, Successive Convex Approximations

Category 1: Combinatorial Optimization

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Integer Programming (0-1 Programming )

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.

Download: [Postscript][PDF]

Entry Submitted: 01/26/2004
Entry Accepted: 01/26/2004
Entry Last Modified: 03/09/2005

Modify/Update this entry