IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v60y2015i1p171-198.html
   My bibliography  Save this article

Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting

Author

Listed:
  • Jiming Peng
  • Tao Zhu
  • Hezhi Luo
  • Kim-Chuan Toh

Abstract

Quadratic assignment problems (QAPs) are known to be among the most challenging discrete optimization problems. Recently, a new class of semi-definite relaxation models for QAPs based on matrix splitting has been proposed (Mittelmann and Peng, SIAM J Optim 20:3408–3426, 2010 ; Peng et al., Math Program Comput 2:59–77, 2010 ). In this paper, we consider the issue of how to choose an appropriate matrix splitting scheme so that the resulting relaxation model is easy to solve and able to provide a strong bound. For this, we first introduce a new notion of the so-called redundant and non-redundant matrix splitting and show that the relaxation based on a non-redundant matrix splitting can provide a stronger bound than a redundant one. Then we propose to follow the minimal trace principle to find a non-redundant matrix splitting via solving an auxiliary semi-definite programming problem. We show that applying the minimal trace principle directly leads to the so-called orthogonal matrix splitting introduced in (Peng et al., Math Program Comput 2:59–77, 2010 ). To find other non-redundant matrix splitting schemes whose resulting relaxation models are relatively easy to solve, we elaborate on two splitting schemes based on the so-called one-matrix and the sum-matrix. We analyze the solutions from the auxiliary problems for these two cases and characterize when they can provide a non-redundant matrix splitting. The lower bounds from these two splitting schemes are compared theoretically. Promising numerical results on some large QAP instances are reported, which further validate our theoretical conclusions. Copyright Springer Science+Business Media New York 2015

Suggested Citation

  • Jiming Peng & Tao Zhu & Hezhi Luo & Kim-Chuan Toh, 2015. "Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting," Computational Optimization and Applications, Springer, vol. 60(1), pages 171-198, January.
  • Handle: RePEc:spr:coopap:v:60:y:2015:i:1:p:171-198
    DOI: 10.1007/s10589-014-9663-y
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10589-014-9663-y
    Download Restriction: Access to full text is restricted to subscribers.

    File URL: https://libkey.io/10.1007/s10589-014-9663-y?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Adams, Warren P. & Guignard, Monique & Hahn, Peter M. & Hightower, William L., 2007. "A level-2 reformulation-linearization technique bound for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 180(3), pages 983-996, August.
    2. Loiola, Eliane Maria & de Abreu, Nair Maria Maia & Boaventura-Netto, Paulo Oswaldo & Hahn, Peter & Querido, Tania, 2007. "A survey for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 176(2), pages 657-690, January.
    3. Lopamudra Mukherjee & Vikas Singh & Jiming Peng & Jinhui Xu & Michael J. Zeitz & Ronald Berezney, 2009. "Generalized median graphs and applications," Journal of Combinatorial Optimization, Springer, vol. 17(1), pages 21-44, January.
    4. Peter Hahn & Thomas Grant, 1998. "Lower Bounds for the Quadratic Assignment Problem Based upon a Dual Formulation," Operations Research, INFORMS, vol. 46(6), pages 912-922, December.
    5. de Klerk, E. & Sotirov, R., 2007. "Exploiting Group Symmetry in Semidefinite Programming Relaxations of the Quadratic Assignment Problem," Discussion Paper 2007-44, Tilburg University, Center for Economic Research.
    6. Eugene L. Lawler, 1963. "The Quadratic Assignment Problem," Management Science, INFORMS, vol. 9(4), pages 586-599, July.
    7. Qing Zhao & Stefan E. Karisch & Franz Rendl & Henry Wolkowicz, 1998. "Semidefinite Programming Relaxations for the Quadratic Assignment Problem," Journal of Combinatorial Optimization, Springer, vol. 2(1), pages 71-109, March.
    8. Rendl, F. & Sotirov, R., 2007. "Bounds for the quadratic assignment problem using the bundle method," Other publications TiSEM b6d298bc-77c9-4a6d-a043-5, Tilburg University, School of Economics and Management.
    9. Yichuan Ding & Henry Wolkowicz, 2009. "A Low-Dimensional Semidefinite Relaxation for the Quadratic Assignment Problem," Mathematics of Operations Research, INFORMS, vol. 34(4), pages 1008-1022, November.
    10. S. W. Hadley & F. Rendl & H. Wolkowicz, 1992. "A New Lower Bound Via Projection for the Quadratic Assignment Problem," Mathematics of Operations Research, INFORMS, vol. 17(3), pages 727-739, August.
    11. Peter M. Hahn & Yi-Rong Zhu & Monique Guignard & William L. Hightower & Matthew J. Saltzman, 2012. "A Level-3 Reformulation-Linearization Technique-Based Bound for the Quadratic Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 24(2), pages 202-209, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. José F. S. Bravo Ferreira & Yuehaw Khoo & Amit Singer, 2018. "Semidefinite programming approach for the quadratic assignment problem with a sparse graph," Computational Optimization and Applications, Springer, vol. 69(3), pages 677-712, April.
    2. Feizollahi, Mohammad Javad & Feyzollahi, Hadi, 2015. "Robust quadratic assignment problem with budgeted uncertain flows," Operations Research Perspectives, Elsevier, vol. 2(C), pages 114-123.
    3. E. de Klerk & R. Sotirov & U. Truetsch, 2015. "A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 378-391, May.
    4. Huixian Wu & Hezhi Luo & Xianye Zhang & Haiqiang Qi, 2023. "An effective global algorithm for worst-case linear optimization under polyhedral uncertainty," Journal of Global Optimization, Springer, vol. 87(1), pages 191-219, September.
    5. Hezhi Luo & Xiaodong Ding & Jiming Peng & Rujun Jiang & Duan Li, 2021. "Complexity Results and Effective Algorithms for Worst-Case Linear Optimization Under Uncertainties," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 180-197, January.
    6. Ketan Date & Rakesh Nagi, 2019. "Level 2 Reformulation Linearization Technique–Based Parallel Algorithms for Solving Large Quadratic Assignment Problems on Graphics Processing Unit Clusters," INFORMS Journal on Computing, INFORMS, vol. 31(4), pages 771-789, October.
    7. Xiaodong Ding & Hezhi Luo & Huixian Wu & Jianzhen Liu, 2021. "An efficient global algorithm for worst-case linear optimization under uncertainties based on nonlinear semidefinite relaxation," Computational Optimization and Applications, Springer, vol. 80(1), pages 89-120, September.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Yichuan Ding & Henry Wolkowicz, 2009. "A Low-Dimensional Semidefinite Relaxation for the Quadratic Assignment Problem," Mathematics of Operations Research, INFORMS, vol. 34(4), pages 1008-1022, November.
    2. Ketan Date & Rakesh Nagi, 2019. "Level 2 Reformulation Linearization Technique–Based Parallel Algorithms for Solving Large Quadratic Assignment Problems on Graphics Processing Unit Clusters," INFORMS Journal on Computing, INFORMS, vol. 31(4), pages 771-789, October.
    3. Loiola, Eliane Maria & de Abreu, Nair Maria Maia & Boaventura-Netto, Paulo Oswaldo & Hahn, Peter & Querido, Tania, 2007. "A survey for the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 176(2), pages 657-690, January.
    4. Pessoa, Artur Alves & Hahn, Peter M. & Guignard, Monique & Zhu, Yi-Rong, 2010. "Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization Technique," European Journal of Operational Research, Elsevier, vol. 206(1), pages 54-63, October.
    5. Huizhen Zhang & Cesar Beltran-Royo & Liang Ma, 2013. "Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers," Annals of Operations Research, Springer, vol. 207(1), pages 261-278, August.
    6. Peter M. Hahn & Yi-Rong Zhu & Monique Guignard & William L. Hightower & Matthew J. Saltzman, 2012. "A Level-3 Reformulation-Linearization Technique-Based Bound for the Quadratic Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 24(2), pages 202-209, May.
    7. E. de Klerk & R. Sotirov & U. Truetsch, 2015. "A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 378-391, May.
    8. de Klerk, Etienne & -Nagy, Marianna E. & Sotirov, Renata & Truetsch, Uwe, 2014. "Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems," European Journal of Operational Research, Elsevier, vol. 233(3), pages 488-499.
    9. Feizollahi, Mohammad Javad & Feyzollahi, Hadi, 2015. "Robust quadratic assignment problem with budgeted uncertain flows," Operations Research Perspectives, Elsevier, vol. 2(C), pages 114-123.
    10. Silva, Allyson & Coelho, Leandro C. & Darvish, Maryam, 2021. "Quadratic assignment problem variants: A survey and an effective parallel memetic iterated tabu search," European Journal of Operational Research, Elsevier, vol. 292(3), pages 1066-1084.
    11. Richárd Molnár-Szipai & Anita Varga, 2019. "Integrating combinatorial algorithms into a linear programming solver," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 27(2), pages 475-482, June.
    12. Hahn, Peter M. & Kim, Bum-Jin & Stutzle, Thomas & Kanthak, Sebastian & Hightower, William L. & Samra, Harvind & Ding, Zhi & Guignard, Monique, 2008. "The quadratic three-dimensional assignment problem: Exact and approximate solution methods," European Journal of Operational Research, Elsevier, vol. 184(2), pages 416-428, January.
    13. Yichuan Ding & Dongdong Ge & Henry Wolkowicz, 2011. "On Equivalence of Semidefinite Relaxations for Quadratic Matrix Programming," Mathematics of Operations Research, INFORMS, vol. 36(1), pages 88-104, February.
    14. Yong Xia & Wajeb Gharibi, 2015. "On improving convex quadratic programming relaxation for the quadratic assignment problem," Journal of Combinatorial Optimization, Springer, vol. 30(3), pages 647-667, October.
    15. Nyberg, Axel & Westerlund, Tapio, 2012. "A new exact discrete linear reformulation of the quadratic assignment problem," European Journal of Operational Research, Elsevier, vol. 220(2), pages 314-319.
    16. Alexandre Domingues Gonçalves & Artur Alves Pessoa & Cristiana Bentes & Ricardo Farias & Lúcia Maria de A. Drummond, 2017. "A Graphics Processing Unit Algorithm to Solve the Quadratic Assignment Problem Using Level-2 Reformulation-Linearization Technique," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 676-687, November.
    17. Nihal Berktaş & Hande Yaman, 2021. "A Branch-and-Bound Algorithm for Team Formation on Social Networks," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1162-1176, July.
    18. Palubeckis, Gintaras, 2015. "Fast simulated annealing for single-row equidistant facility layout," Applied Mathematics and Computation, Elsevier, vol. 263(C), pages 287-301.
    19. Monique Guignard, 2020. "Strong RLT1 bounds from decomposable Lagrangean relaxation for some quadratic 0–1 optimization problems with linear constraints," Annals of Operations Research, Springer, vol. 286(1), pages 173-200, March.
    20. E. R. van Dam & R. Sotirov, 2015. "On Bounding the Bandwidth of Graphs with Symmetry," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 75-88, February.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:coopap:v:60:y:2015:i:1:p:171-198. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.