TY - GEN
A1 - Helmberg, Christoph
T1 - Fixing Variables in Semidefinite Relaxations
N2 - 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.
T3 - ZIB-Report - SC-96-43
Y1 - 1996
UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/253
UR - https://nbn-resolving.org/urn:nbn:de:0297-zib-2530
ER -