Back to Search
Start Over
On improving convex quadratic programming relaxation for the quadratic assignment problem
- Source :
- Journal of Combinatorial Optimization. 30:647-667
- Publication Year :
- 2013
- Publisher :
- Springer Science and Business Media LLC, 2013.
-
Abstract
- Relaxation techniques play a great role in solving the quadratic assignment problem, among which the convex quadratic programming bound (QPB) is competitive with existing bounds in the trade-off between cost and quality. In this article, we propose two new lower bounds based on QPB. The first dominates QPB at a high computational cost, which is shown equivalent to the recent second-order cone programming bound. The second is strictly tighter than QPB in most cases, while it is solved as easily as QPB.
- Subjects :
- Mathematical optimization
Control and Optimization
Quadratic assignment problem
Applied Mathematics
Upper and lower bounds
Computer Science Applications
Computational Theory and Mathematics
Theory of computation
Discrete Mathematics and Combinatorics
Relaxation (approximation)
Quadratic programming
Convex quadratic programming
Cone programming
Mathematics
Subjects
Details
- ISSN :
- 15732886 and 13826905
- Volume :
- 30
- Database :
- OpenAIRE
- Journal :
- Journal of Combinatorial Optimization
- Accession number :
- edsair.doi...........c8c8d8287832ede45e79f283557f07fe