Fixing Variables in Semidefinite Relaxations
Author:
- Christoph HelmbergCHChristoph Helmberg
- 1 January 2000
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 21 (3) , 952-969
Abstract
The standard technique of reduced cost fixing from linear programming is not trivially extensible to semidefinite relaxations because the corresponding Lagrange multipliers are usually not available. We propose a general technique for computing reasonable Lagrange multipliers for constraints that are not part of the problem description. Its specialization to the semidefinite {-1,1} relaxation of quadratic 0-1 programming yields an efficient routine for fixing variables. The routine offers the possibility of exploiting problem structure. We extend the traditional bijective map between {0,1} and {-1,1} formulations to the constraints so that the dual variables remain the same and structural properties are preserved. Consequently, the fixing routine can be applied efficiently to optimal solutions of the semidefinite {0,1} relaxation of constrained quadratic 0-1 programming as well. We provide numerical results showing the efficacy of this approach.Keywords
This publication has 30 references indexed in Scilit:
- Fixing Variables in Semidefinite RelaxationsSIAM Journal on Matrix Analysis and Applications, 2000
- A Geometric Approach to BetweennessSIAM Journal on Discrete Mathematics, 1998
- Approximate graph coloring by semidefinite programmingJournal of the ACM, 1998
- Interior-Point Methods for the Monotone Semidefinite Linear Complementarity Problem in Symmetric MatricesSIAM Journal on Optimization, 1997
- An Interior-Point Method for Semidefinite ProgrammingSIAM Journal on Optimization, 1996
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- Nonpolyhedral Relaxations of Graph-Bisection ProblemsSIAM Journal on Optimization, 1995
- An Interior-Point Method for Minimizing the Maximum Eigenvalue of a Linear Combination of MatricesSIAM Journal on Control and Optimization, 1993
- The cut polytope and the Boolean quadric polytopeDiscrete Mathematics, 1990
- On the Shannon capacity of a graphIEEE Transactions on Information Theory, 1979