|
 
|
[ROU04] From Linear to Semidefinite Programming: an Algorithm to obtain Semidefinite Relaxations for Bivalent Quadratic Problems
Revue Internationale avec comité de lecture : Journal Journal of Combinatorial Optimization, vol. 8(4), pp. 469-493, 2004
motcle:
Résumé:
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.
Commentaires:
(Première version présentée à ROADEF'2002, ENST, Paris)
Collaboration:
LIPN
BibTeX
| @article { | |||
| ROU04, | |||
| title | = | "{From Linear to Semidefinite Programming: an Algorithm to obtain Semidefinite Relaxations for Bivalent Quadratic Problems}", | |
| author | = | "F. Roupin", | |
| journal | = | "Journal of Combinatorial Optimization", | |
| year | = | 2004, | |
| volume | = | 8, | |
| number | = | 4, | |
| pages | = | "469-493", | |
| note | = | "{(Première version présentée à ROADEF'2002, ENST, Paris)}", | |
| } | |||
