Back to Search
Start Over
[Untitled]
- Source :
- Journal of Combinatorial Optimization. 2:71-109
- Publication Year :
- 1998
- Publisher :
- Springer Science and Business Media LLC, 1998.
-
Abstract
- Semidefinite programming (SDP) relaxations for the quadratic assignment problem (QAP) are derived using the dual of the (homogenized) Lagrangian dual of appropriate equivalent representations of QAP. These relaxations result in the interesting, special, case where only the dual problem of the SDP relaxation has strict interior, i.e., the Slater constraint qualification always fails for the primal problem. Although there is no duality gap in theory, this indicates that the relaxation cannot be solved in a numerically stable way. By exploring the geometrical structure of the relaxation, we are able to find projected SDP relaxations. These new relaxations, and their duals, satisfy the Slater constraint qualification, and so can be solved numerically using primal-dual interior-point methods.
- Subjects :
- Discrete mathematics
Semidefinite programming
Quadratically constrained quadratic program
Control and Optimization
Duality gap
Quadratic assignment problem
Applied Mathematics
Mathematics::Optimization and Control
Computer Science Applications
Computational Theory and Mathematics
Theory of computation
Discrete Mathematics and Combinatorics
Dual polyhedron
Relaxation (approximation)
Interior point method
Mathematics
Subjects
Details
- ISSN :
- 13826905
- Volume :
- 2
- Database :
- OpenAIRE
- Journal :
- Journal of Combinatorial Optimization
- Accession number :
- edsair.doi...........352c7bab04ff4c2c5c79bff5e113fcef