Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Fixing Variables in Semidefinite Relaxations

Please always quote using this URN: urn:nbn:de:0297-zib-2530
  • The standard technique of reduced cost fixing from linear programming is not trivially extensible to semidefinite relaxations as the corresponding Lagrange multipliers are usually not available. We propose a general technique for computing reasonable Lagrange multipliers to constraints which are not part of the problem description. Its specialization to the semidefinite $\left\{-1,1\right\}$ relaxation of quadratic 0-1 programming yields an efficient routine for fixing variables. The routine offers the possibility to exploit problem structure. We extend the traditional bijective map between $\left\{0,1\right\}$ and $\left\{-1,1\right\}$ formulations to the constraints such that the dual variables remain the same and structural properties are preserved. In consequence the fixing routine can efficiently be applied to optimal solutions of the semidefinite $\left\{0,1\right\}$ relaxation of constrained quadratic 0-1 programming, as well. We provide numerical results showing the efficacy of the approach.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Author:Christoph Helmberg
Document Type:ZIB-Report
Date of first Publication:1996/11/27
Series (Serial Number):ZIB-Report (SC-96-43)
Published in:Appeared in: SIAM J. Matrix Anal. Appl. 21 (2000), Nr. 3, 952-969
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.