From Linear to Semidefinite Programming: An Algorithm to Obtain Semidefinite Relaxations for Bivalent Quadratic Problems

Frédéric Roupin ()
Additional contact information
Frédéric Roupin: CEDRIC—Institut d’Informatique d’Entreprise

Journal of Combinatorial Optimization, 2004, vol. 8, issue 4, No 5, 469-493

Abstract: Abstract In this paper, we present a simple algorithm to obtain mechanically SDP relaxations for any quadratic or linear program with bivalent variables, starting from an existing linear relaxation of the considered combinatorial problem. A significant advantage of our approach is that we obtain an improvement on the linear relaxation we start from. Moreover, we can take into account all the existing theoretical and practical experience accumulated in the linear approach. After presenting the rules to treat each type of constraint, we describe our algorithm, and then apply it to obtain semidefinite relaxations for three classical combinatorial problems: the K-CLUSTER problem, the Quadratic Assignment Problem, and the Constrained-Memory Allocation Problem. We show that we obtain better SDP relaxations than the previous ones, and we report computational experiments for the three problems.

Keywords: semidefinite programming; quadratic assignment problem; K-CLUSTER problem; constrained-memory allocation problem (search for similar items in EconPapers)
Date: 2004
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-004-4838-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:jcomop:v:8:y:2004:i:4:d:10.1007_s10878-004-4838-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-004-4838-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().