Semidefinite Relaxations for Integer Programming

Franz Rendl ()
Additional contact information
Franz Rendl: Department of Mathematics, Alpen-Adria Universität

Chapter Chapter 18 in 50 Years of Integer Programming 1958-2008, 2010, pp 687-726 from Springer

Abstract: Abstract We survey some recent developments in the area of semidefinite optimization applied to integer programming. After recalling some generic modeling techniques to obtain semidefinite relaxations for NP-hard problems, we look at the theoretical power of semidefinite optimization in the context of the Max-Cut and the Coloring Problem. In the second part, we consider algorithmic questions related to semidefinite optimization, and point to some recent ideas to handle large scale problems. The survey is concluded with some more advanced modeling techniques, based on matrix relaxations leading to copositive matrices.

Keywords: Travel Salesman Problem; Chromatic Number; SIAM Journal; Quadratic Assignment Problem; Bundle Method (search for similar items in EconPapers)
Date: 2010
References: Add references at CitEc
Citations:

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-3-540-68279-0_18

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

DOI: 10.1007/978-3-540-68279-0_18

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 ().