IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v233y2014i3p488-499.html
   My bibliography  Save this article

Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems

Author

Listed:
  • de Klerk, Etienne
  • -Nagy, Marianna E.
  • Sotirov, Renata
  • Truetsch, Uwe

Abstract

The reformulation–linearization technique (RLT), introduced in [Sherali, H. D., Adams. W. P. (1990). A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics 3(3), 411–430], provides a way to compute a hierarchy of linear programming bounds on the optimal values of NP-hard combinatorial optimization problems. In this paper we show that, in the presence of suitable algebraic symmetry in the original problem data, it is sometimes possible to compute level two RLT bounds with additional linear matrix inequality constraints. As an illustration of our methodology, we compute the best-known bounds for certain graph partitioning problems on strongly regular graphs.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:233:y:2014:i:3:p:488-499
    DOI: 10.1016/j.ejor.2013.10.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221713008308
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2013.10.007?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. 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.
    3. Warren P. Adams & Hanif D. Sherali, 1990. "Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems," Operations Research, INFORMS, vol. 38(2), pages 217-226, April.
    4. Warren P. Adams & Hanif D. Sherali, 1986. "A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems," Management Science, INFORMS, vol. 32(10), pages 1274-1290, October.
    5. 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.
    6. Renata Sotirov, 2012. "SDP Relaxations for Some Combinatorial Optimization Problems," International Series in Operations Research & Management Science, in: Miguel F. Anjos & Jean B. Lasserre (ed.), Handbook on Semidefinite, Conic and Polynomial Optimization, chapter 0, pages 795-819, Springer.
    7. Haemers, W.H. & Touchev, V.D., 1996. "Spreads in strongly regular graphs," Other publications TiSEM baf73ad8-e852-4528-b0b5-c, Tilburg University, School of Economics and Management.
    8. Dobre, C., 2011. "Semidefinite programming approaches for structured combinatorial optimization problems," Other publications TiSEM e1ec09bd-b024-4dec-acad-7, Tilburg University, School of Economics and Management.
    9. 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.
    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. Feizollahi, Mohammad Javad & Feyzollahi, Hadi, 2015. "Robust quadratic assignment problem with budgeted uncertain flows," Operations Research Perspectives, Elsevier, vol. 2(C), pages 114-123.

    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. 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.
    2. Rostami, Borzou & Malucelli, Federico & Belotti, Pietro & Gualandi, Stefano, 2016. "Lower bounding procedure for the asymmetric quadratic traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 253(3), pages 584-592.
    3. 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.
    4. Peter Hahn & J. MacGregor Smith & Yi-Rong Zhu, 2010. "The Multi-Story Space Assignment Problem," Annals of Operations Research, Springer, vol. 179(1), pages 77-103, September.
    5. 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.
    6. Lucas A. Waddell & Jerry L. Phillips & Tianzhu Liu & Swarup Dhar, 2023. "An LP-based characterization of solvable QAP instances with chess-board and graded structures," Journal of Combinatorial Optimization, Springer, vol. 45(5), pages 1-23, July.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. de Meijer, Frank, 2023. "Integrality and cutting planes in semidefinite programming approaches for combinatorial optimization," Other publications TiSEM b1f1088c-95fe-4b8a-9e15-c, Tilburg University, School of Economics and Management.
    12. Guanglei Wang & Hassan Hijazi, 2018. "Mathematical programming methods for microgrid design and operations: a survey on deterministic and stochastic approaches," Computational Optimization and Applications, Springer, vol. 71(2), pages 553-608, November.
    13. de Klerk, E. & Pasechnik, D.V. & Sotirov, R., 2007. "On Semidefinite Programming Relaxations of the Travelling Salesman Problem (Replaced by DP 2008-96)," Discussion Paper 2007-101, Tilburg University, Center for Economic Research.
    14. Hao Hu & Renata Sotirov, 2021. "The linearization problem of a binary quadratic problem and its applications," Annals of Operations Research, Springer, vol. 307(1), pages 229-249, December.
    15. Hanif Sherali, 2007. "RLT: A unified approach for discrete and continuous nonconvex optimization," Annals of Operations Research, Springer, vol. 149(1), pages 185-193, February.
    16. 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.
    17. 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.
    18. Stefan Helber & Daniel Böhme & Farid Oucherif & Svenja Lagershausen & Steffen Kasper, 2016. "A hierarchical facility layout planning approach for large and complex hospitals," Flexible Services and Manufacturing Journal, Springer, vol. 28(1), pages 5-29, June.
    19. 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.
    20. 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.

    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:eee:ejores:v:233:y:2014:i:3:p:488-499. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.