-
Previous Article
Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming
- JIMO Home
- This Issue
-
Next Article
Stable strong and total parametrized dualities for DC optimization problems in locally convex spaces
Convex hull of the orthogonal similarity set with applications in quadratic assignment problems
1. | State Key Laboratory of Software Development Environment, LMIB of the Ministry of Education, School of Mathematics and System Sciences, Beihang University, Beijing, 100191, China |
References:
[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. |
[2] |
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. |
[3] |
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. |
[4] |
K. M. Anstreicher, Recent advances in the solution of quadratic assignment Problems, Mathematical Programming Ser. B, 97 (2003), 24-42. |
[5] |
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. |
[6] |
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. |
[7] |
E. Çela, "The Quadratic Assignment Problem: Theory and Algorithms," Kluwer Academic Publishers, Dordrecht, 1998. |
[8] |
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. |
[9] |
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. |
[10] |
C. S. Edwards, A branch and bound algorithm for the Koopmans-Beckmann quadratic assignment problem, Mathematical Programming Study, 13 (1980), 35-52. |
[11] |
P. A. Fillmore and J. P. Williams, Some convexity theorems for matrices, Glasgow Math. J., 12 (1971), 110-117.
doi: 10.1017/S0017089500001221. |
[12] |
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. |
[13] |
M. Grant and S. Boyd, "{CVX}: {Matlab} Software for Disciplined Convex Programming," http://cvxr.com/cvx. version 1. 21 (2010) |
[14] |
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. |
[15] |
G. G. Hardy, J. E. Littlewood and G. Pólya, "Inequalities," Cambridge University Press, London and New York, 1952. |
[16] |
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. |
[17] |
A. W. Marshall and I. Olkin, "Inequalities: Theory of Majorization and its Application," Academic Press, New York, NY, 1979. |
[18] |
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. |
[19] |
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. |
[20] |
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. |
[21] |
Y. Xia, Second order cone programming relaxation for quadratic assignment problems, Optimization Methods & Software, 23 (2008), 441-449.
doi: 10.1080/10556780701843405. |
[22] |
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. |
[23] |
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. |
show all references
References:
[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. |
[2] |
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. |
[3] |
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. |
[4] |
K. M. Anstreicher, Recent advances in the solution of quadratic assignment Problems, Mathematical Programming Ser. B, 97 (2003), 24-42. |
[5] |
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. |
[6] |
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. |
[7] |
E. Çela, "The Quadratic Assignment Problem: Theory and Algorithms," Kluwer Academic Publishers, Dordrecht, 1998. |
[8] |
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. |
[9] |
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. |
[10] |
C. S. Edwards, A branch and bound algorithm for the Koopmans-Beckmann quadratic assignment problem, Mathematical Programming Study, 13 (1980), 35-52. |
[11] |
P. A. Fillmore and J. P. Williams, Some convexity theorems for matrices, Glasgow Math. J., 12 (1971), 110-117.
doi: 10.1017/S0017089500001221. |
[12] |
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. |
[13] |
M. Grant and S. Boyd, "{CVX}: {Matlab} Software for Disciplined Convex Programming," http://cvxr.com/cvx. version 1. 21 (2010) |
[14] |
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. |
[15] |
G. G. Hardy, J. E. Littlewood and G. Pólya, "Inequalities," Cambridge University Press, London and New York, 1952. |
[16] |
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. |
[17] |
A. W. Marshall and I. Olkin, "Inequalities: Theory of Majorization and its Application," Academic Press, New York, NY, 1979. |
[18] |
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. |
[19] |
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. |
[20] |
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. |
[21] |
Y. Xia, Second order cone programming relaxation for quadratic assignment problems, Optimization Methods & Software, 23 (2008), 441-449.
doi: 10.1080/10556780701843405. |
[22] |
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. |
[23] |
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. |
[1] |
Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial and Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177 |
[2] |
Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems and Imaging, 2021, 15 (2) : 315-338. doi: 10.3934/ipi.2020070 |
[3] |
Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial and Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881 |
[4] |
Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial and Management Optimization, 2019, 15 (1) : 235-259. doi: 10.3934/jimo.2018041 |
[5] |
R. N. Gasimov, O. Ustun. Solving the quadratic assignment problem using F-MSG algorithm. Journal of Industrial and Management Optimization, 2007, 3 (2) : 173-191. doi: 10.3934/jimo.2007.3.173 |
[6] |
Xiaojin Zheng, Zhongyi Jiang. Tighter quadratically constrained convex reformulations for semi-continuous quadratic programming. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2331-2343. doi: 10.3934/jimo.2020071 |
[7] |
Alessandro Ferriero, Nicola Fusco. A note on the convex hull of sets of finite perimeter in the plane. Discrete and Continuous Dynamical Systems - B, 2009, 11 (1) : 103-108. doi: 10.3934/dcdsb.2009.11.103 |
[8] |
Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial and Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117 |
[9] |
Gisella Croce. An elliptic problem with degenerate coercivity and a singular quadratic gradient lower order term. Discrete and Continuous Dynamical Systems - S, 2012, 5 (3) : 507-530. doi: 10.3934/dcdss.2012.5.507 |
[10] |
Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1527-1538. doi: 10.3934/jimo.2019015 |
[11] |
Daniel Heinlein, Ferdinand Ihringer. New and updated semidefinite programming bounds for subspace codes. Advances in Mathematics of Communications, 2020, 14 (4) : 613-630. doi: 10.3934/amc.2020034 |
[12] |
Shouhong Yang. Semidefinite programming via image space analysis. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1187-1197. doi: 10.3934/jimo.2016.12.1187 |
[13] |
Christine Bachoc, Alberto Passuello, Frank Vallentin. Bounds for projective codes from semidefinite programming. Advances in Mathematics of Communications, 2013, 7 (2) : 127-145. doi: 10.3934/amc.2013.7.127 |
[14] |
Zhi-Bin Deng, Ye Tian, Cheng Lu, Wen-Xun Xing. Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming. Journal of Industrial and Management Optimization, 2018, 14 (2) : 625-636. doi: 10.3934/jimo.2017064 |
[15] |
Ling Zhang, Xiaoqi Sun. Stability analysis of time-varying delay neural network for convex quadratic programming with equality constraints and inequality constraints. Discrete and Continuous Dynamical Systems - B, 2022 doi: 10.3934/dcdsb.2022035 |
[16] |
Bettina Klaus, Frédéric Payot. Paths to stability in the assignment problem. Journal of Dynamics and Games, 2015, 2 (3&4) : 257-287. doi: 10.3934/jdg.2015004 |
[17] |
Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193 |
[18] |
Xiaoni Chi, Zhongping Wan, Zijun Hao. Second order sufficient conditions for a class of bilevel programs with lower level second-order cone programming problem. Journal of Industrial and Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111 |
[19] |
Wan Nor Ashikin Wan Ahmad Fatthi, Adibah Shuib, Rosma Mohd Dom. A mixed integer programming model for solving real-time truck-to-door assignment and scheduling problem at cross docking warehouse. Journal of Industrial and Management Optimization, 2016, 12 (2) : 431-447. doi: 10.3934/jimo.2016.12.431 |
[20] |
Srimanta Bhattacharya, Sushmita Ruj, Bimal Roy. Combinatorial batch codes: A lower bound and optimal constructions. Advances in Mathematics of Communications, 2012, 6 (2) : 165-174. doi: 10.3934/amc.2012.6.165 |
2021 Impact Factor: 1.411
Tools
Metrics
Other articles
by authors
[Back to Top]