Advanced Search
Article Contents
Article Contents

Convex hull of the orthogonal similarity set with applications in quadratic assignment problems

Abstract Related Papers Cited by
  • In this paper, we study thoroughly the convex hull of the orthogonal similarity set and give a new representation. When applied in quadratic assignment problems, it motivates two new lower bounds. The first is equivalent to the projected eigenvalue bound, while the second highly outperforms several well-known lower bounds in literature.
    Mathematics Subject Classification: Primary: 90C27; Secondary: 90C22.


    \begin{equation} \\ \end{equation}
  • [1]

    K. M. Anstreicher and H. Wolkowicz, On lagrangian relaxation of quadratic matrix constraints, SIAM J. Matrix Anal. Appl., 22 (2000), 41-55.doi: 10.1137/S0895479898340299.


    K. M. Anstreicher, Eigenvalue bounds versus semidefinite relaxations for the quadratic assignment problem, SIAM Journal on Optimization, 11 (2001), 254-265.doi: 10.1137/S1052623499354904.


    K. M. Anstreicher and N. W. Brixius, A new bound for the quadratic assignment problem based on convex quadratic programming, Mathematical Programming Ser. A, 89 (2001), 341-357.doi: 10.1007/PL00011402.


    K. M. Anstreicher, Recent advances in the solution of quadratic assignment Problems, Mathematical Programming Ser. B, 97 (2003), 24-42.


    R. E. Burkard, Locations with spatial interactions: The quadratic assignment problem, in "Discrete Location Theory" (eds. P. B.Mirchandani and R. L.Francis), Wiley, New York, (1991), 387-437.


    R. E. Burkard, E. Çela, P. M. Pardalos and L. S. Pitsoulis, The quadratic assignment Problem, in "Handbook of Combinatorial Optimization" (eds. D.-Z. Du and P. M. Pardalos), 3, Kluwer, (1998), 241-337.


    E. Çela, "The Quadratic Assignment Problem: Theory and Algorithms," Kluwer Academic Publishers, Dordrecht, 1998.


    Y. Ding and H. Wolkowicz, A low-dimensional semidefinite relaxation for the quadratic assignment problem, Mathematics of Operations Research, 34 (2009), 1008-1022.doi: 10.1287/moor.1090.0419.


    C. S. Edwards, The derivation of a greedy approximator for the Koopmans-Beckmann quadratic assignment problem, Proceedings of the 77-th Combinatorial Programming Conference (CP77) (1977), 55-86.


    C. S. Edwards, A branch and bound algorithm for the Koopmans-Beckmann quadratic assignment problem, Mathematical Programming Study, 13 (1980), 35-52.


    P. A. Fillmore and J. P. Williams, Some convexity theorems for matrices, Glasgow Math. J., 12 (1971), 110-117.doi: 10.1017/S0017089500001221.


    G. Finke, R. E. Burkard and F. Rendl, Quadratic assignment problems, Ann. Discrete Math., 31 (1987), 61-82.doi: 10.1016/S0304-0208(08)73232-8.


    M. Grant and S. Boyd, "{CVX}: {Matlab} Software for Disciplined Convex Programming," http://cvxr.com/cvx. version 1. 21 (2010)


    S. W. Hadley, F. Rendl and H. Wolkowicz, A new lower bound via projection for the quadratic assignment problem, Math. Oper. Res., 17 (1992), 727-739.doi: 10.1287/moor.17.3.727.


    G. G. Hardy, J. E. Littlewood and G. Pólya, "Inequalities," Cambridge University Press, London and New York, 1952.


    E. M. Loiola, N. M. M. Abreu, P. O. Boaventura-Netto, P. Hahn and T. Querido, A survey for the quadratic assignment problem, European Journal of Operational Research, 176 (2007), 657-690.doi: 10.1016/j.ejor.2005.09.032.


    A. W. Marshall and I. Olkin, "Inequalities: Theory of Majorization and its Application," Academic Press, New York, NY, 1979.


    M. L. Overton and R. S. Womersley, On the sum of the largest eigenvalues of a symmetric matrix, SIAM J. Matrix Anal. Appl., 13 (1992), 41-45.doi: 10.1137/0613006.


    P. M. Pardalos, F. Rendl and H. Wolkowicz, The Quadratic Assignment Problem: A Survey and Recent Developments, in "Quadratic Assignment and Related Problems" (eds. P. M. Pardalos and H. Wolkowicz), 16 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science,AMS. 16 (1994), 1-42.


    S. Sahni and T. Gonzalez, P-complete approximation problems, Journal of the Association of Computing Machinery, 23 (1976), 555-565.doi: 10.1145/321958.321975.


    Y. Xia, Second order cone programming relaxation for quadratic assignment problems, Optimization Methods $&$ Software, 23 (2008), 441-449.doi: 10.1080/10556780701843405.


    Y. Xia, New sufficient global optimality conditions for linearly constrained bivalent quadratic optimization problem, Journal of Industrial and Management Optimization, 5 (2009), 881-892.doi: 10.3934/jimo.2009.5.881.


    Y. Xia, Convex hull presentation of a quadratically constrained set and its application in solving quadratic programming problems, Asia-Pacific Journal of Operational Research, 26 (2009), 769-778.doi: 10.1142/S0217595909002468.

  • 加载中

Article Metrics

HTML views() PDF downloads(171) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint