Fixing Variables in Semidefinite Relaxations
Christoph Helmberg
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.
Preprint SC-96-43, December 1996,
Konrad Zuse Zentrum fer Informationstechnik Berlin,
Takustrasse 7, D-14195 Berlin-Dahlem, Germany.
Contact: [email protected]
![[PS]](../../InteriorPoint/gif/PS.gif)
![[IP PAGE]](../../InteriorPoint/gif/HOME.gif)
![[SEARCH AGAIN]](../../InteriorPoint/gif/SEARCH.gif)