IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v267y2018i3p818-834.html

New special cases of the Quadratic Assignment Problem with diagonally structured coefficient matrices

Author

Listed:
  • Çela, Eranda
  • Deineko, Vladimir
  • Woeginger, Gerhard J.

Abstract

We consider new polynomially solvable cases of the well-known Quadratic Assignment Problem involving coefficient matrices with a special diagonal structure. By combining the new special cases with polynomially solvable special cases known in the literature we obtain a new and larger class of polynomially solvable special cases of the QAP where one of the two coefficient matrices involved is a Robinson matrix with an additional structural property: this matrix can be represented as a conic combination of cut matrices in a certain normal form. The other matrix is a conic combination of a monotone anti-Monge matrix and a down-benevolent Toeplitz matrix. We consider the recognition problem for the special class of Robinson matrices mentioned above and show that it can be solved in polynomial time.

Suggested Citation

  • Çela, Eranda & Deineko, Vladimir & Woeginger, Gerhard J., 2018. "New special cases of the Quadratic Assignment Problem with diagonally structured coefficient matrices," European Journal of Operational Research, Elsevier, vol. 267(3), pages 818-834.
    • Handle: RePEc:eee:ejores:v:267:y:2018:i:3:p:818-834
    DOI: 10.1016/j.ejor.2017.12.024
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221717311438
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2017.12.024?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

    for a different version of it.

    References listed on IDEAS

    as
    1. 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.
    2. Sergey Polyakovskiy & Frits C. R. Spieksma & Gerhard J. Woeginger, 2013. "The three-dimensional matching problem in Kalmanson matrices," Journal of Combinatorial Optimization, Springer, vol. 26(1), pages 1-9, July.
    3. Bettina Klinz & Gerhard J. Woeginger, 1999. "The Steiner Tree Problem in Kalmanson Matrices and in Circulant Matrices," Journal of Combinatorial Optimization, Springer, vol. 3(1), pages 51-58, July.
    4. Laurent, Monique & Seminaroti, Matteo, 2016. "Similarity-First Search : A New Algorithm With Application to Robinsonian Matrix Recognition," Other publications TiSEM 8468be57-ed46-400c-9c0e-7, Tilburg University, School of Economics and Management.
    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. 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.
    2. 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.

    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. Eranda Çela & Vladimir G. Deineko & Gerhard J. Woeginger, 2017. "The multi-stripe travelling salesman problem," Annals of Operations Research, Springer, vol. 259(1), pages 21-34, December.
    2. Yunpeng Sun & Ruoya Jia & Asif Razzaq & Qun Bao, 2023. "RETRACTED ARTICLE: Drivers of China’s geographical renewable energy development: evidence from spatial association network structure approaches," Economic Change and Restructuring, Springer, vol. 56(6), pages 4115-4163, December.
    3. Herrán, Alberto & Manuel Colmenar, J. & Duarte, Abraham, 2021. "An efficient variable neighborhood search for the Space-Free Multi-Row Facility Layout problem," European Journal of Operational Research, Elsevier, vol. 295(3), pages 893-907.
    4. Ricardo M. Lima & Ignacio E. Grossmann, 2017. "On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study," Computational Optimization and Applications, Springer, vol. 66(1), pages 1-37, January.
    5. Alfonsas Misevičius & Aleksandras Andrejevas & Armantas Ostreika & Dovilė Verenė & Gintarė Žekienė, 2024. "An Improved Hybrid Genetic-Hierarchical Algorithm for the Quadratic Assignment Problem," Mathematics, MDPI, vol. 12(23), pages 1-25, November.
    6. Michela Ricciardi Celsi & Lorenzo Ricciardi Celsi, 2024. "Quantum Computing as a Game Changer on the Path towards a Net-Zero Economy: A Review of the Main Challenges in the Energy Domain," Energies, MDPI, vol. 17(5), pages 1-22, February.
    7. Krešimir Mihić & Kevin Ryan & Alan Wood, 2018. "Randomized Decomposition Solver with the Quadratic Assignment Problem as a Case Study," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 295-308, May.
    8. Papahristodoulou, Christos, 2009. "The optimal layout of football players: A case study for AC Milan," MPRA Paper 20102, University Library of Munich, Germany.
    9. Alistair Wilson & Mariagiovanna Baccara & Ayse Imrohoroglu & Leeat Yariv, 2009. "A Field Study on Matching with Network Externalities," Working Paper 486, Department of Economics, University of Pittsburgh, revised Sep 2011.
    10. Jia, Zhao-hong & Li, Kai & Leung, Joseph Y.-T., 2015. "Effective heuristic for makespan minimization in parallel batch machines with non-identical capacities," International Journal of Production Economics, Elsevier, vol. 169(C), pages 1-10.
    11. 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.
    12. Angel Juan & Javier Faulin & Albert Ferrer & Helena Lourenço & Barry Barrios, 2013. "MIRHA: multi-start biased randomization of heuristics with adaptive local search for solving non-smooth routing problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 21(1), pages 109-132, April.
    13. Keller, Birgit & Buscher, Udo, 2015. "Single row layout models," European Journal of Operational Research, Elsevier, vol. 245(3), pages 629-644.
    14. Mădălina M. Drugan, 2015. "Generating QAP instances with known optimum solution and additively decomposable cost function," Journal of Combinatorial Optimization, Springer, vol. 30(4), pages 1138-1172, November.
    15. 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.
    16. Anjos, Miguel F. & Vieira, Manuel V.C., 2017. "Mathematical optimization approaches for facility layout problems: The state-of-the-art and future research directions," European Journal of Operational Research, Elsevier, vol. 261(1), pages 1-16.
    17. 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.
    18. Hengzhao Ma & Jianzhong Li, 2025. "Hardness and algorithms for several new optimization problems on the weighted massively parallel computation model," Journal of Combinatorial Optimization, Springer, vol. 50(1), pages 1-40, August.
    19. Jerzy Grobelny & Rafal Michalski, 2017. "A novel version of simulated annealing based on linguistic patterns for solving facility layout problems," WORking papers in Management Science (WORMS) WORMS/17/07, Department of Operations Research and Business Intelligence, Wroclaw University of Science and Technology.
    20. 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.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:267:y:2018:i:3:p:818-834. 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.