Interior Point and Semidefinite Approaches in Combinatorial Optimization

Kartik Krishnan and Tamás Terlaky

Chapter Chapter 5 in Graph Theory and Combinatorial Optimization, 2005, pp 101-157 from Springer

Abstract: Abstract Conic programming, especially semidefinite programming (SDP), has been regarded as linear programming for the 21st century. This tremendous excitement was spurred in part by a variety of applications of SDP in integer programming (IP) and combinatorial optinmization, and the development of efficient primal-dual interior-point rnethods (IPMs) and various first order approaches for the solution of large scale SDPs. This survey presents an up to date account of semidefinite and interior point approaches in solving NP-hard combinatorial optimnization problenis to optimality, and also in developing approximation algorithms for some of them. The interior point approaches discussed in the survey have been applied directly to non-convex formulations of IPs; they appear in a cutting plane framework to solving IPs, and finally as a subroutine to solving SDP relaxations of IPs. The surveyed approaches include non-convex potential reduction methods, interior point cutting plane methods, primal-dual IPMs and first-order algorithms for solving SDPs, branch and out approaches based on SDP relaxations of IPs, approximation algorithms based on SDP formulations, and finally methods employing successive convex approximations of the underlying combinatorial optimization problem.

Keywords: Semidefinite Programming; Second Order Cone Programming; Convex Feasibility Problem; Volumetric Center; Copositive Programming (search for similar items in EconPapers)
Date: 2005
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-0-387-25592-7_5

Ordering information: This item can be ordered from
http://www.springer.com/9780387255927

DOI: 10.1007/0-387-25592-3_5

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().