Quadratic Knapsack Relaxations Using Cutting Planes and Semidefinite Programming: extended abstract
Please always quote using this URN: urn:nbn:de:0297-zib-2031
- We investigate dominance relations between basic semidefinite relaxations and classes of cuts. We show that simple semidefinite relaxations are tighter than corresponding linear relaxations even in case of linear cost functions. Numerical results are presented illustrating the quality of these relaxations.
Author: | Christoph Helmberg, Franz Rendl, Robert Weismantel |
---|---|
Document Type: | ZIB-Report |
Date of first Publication: | 1995/12/06 |
Series (Serial Number): | ZIB-Report (SC-95-37) |
ZIB-Reportnumber: | SC-95-37 |
Published in: | Appeared in: Integer Programming and Combinatorial Optimization. 5th Int. IPCO Conference, Vancouver, British Columbia, Canada, June, 1996. W. H. Cunningham et al. (eds.) Springer 1996. Lecture Notes in Computer Science, 1084. Pp. 175-189 |