Interior Point and Semidefinite Approaches in Combinatorial Optimization
Kartik Krishnan (kartikcaam.rice.edu)
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.
Entry Submitted: 01/26/2004
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|