IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v32y2020i1p74-89.html
   My bibliography  Save this article

Advanced Tabu Search Algorithms for Bipartite Boolean Quadratic Programs Guided by Strategic Oscillation and Path Relinking

Author

Listed:
  • Qinghua Wu

    (School of Management, Huazhong University of Science and Technology, 430074 Wuhan, China;)

  • Yang Wang

    (School of Management, Northwestern Polytechnical University, 710072 Xi’an, China;)

  • Fred Glover

    (Electrical, Computer, and Energy Engineering, School of Engineering and Science, University of Colorado Boulder, Boulder, Colorado 80309)

Abstract

The bipartite Boolean quadratic programming problem (BBQP) is a generalization of the well-studied NP-hard Boolean quadratic programming problem and can be regarded as a unified model for many graph theoretic optimization problems, including maximum weight-induced subgraph problems, maximum weight biclique problems, matrix factorization problems, and maximum cut problems on bipartite graphs. This paper introduces three main algorithms for solving the BBQP, based on three variants of tabu search, the first two consisting of strategic oscillation–tabu search (SO-TS) algorithms, which use destructive and constructive procedures to guide the search into unexplored and promising areas. The third algorithm, whichDoes also incorporates the SO-TS algorithms as solution improvement methods, uses a path relinking (PR) algorithm that is capable of further enhancing search performance. Experimental results demonstrate that all three algorithms perform very effectively compared with the best methods in the literature, and the PR algorithm joined with tabu search is able to discover new best solutions for two-thirds of the large problem instances and match the previous best known solutions for the other instances. Additional analysis discloses the contributions of the key ingredients of each of the proposed algorithms.

Suggested Citation

  • Qinghua Wu & Yang Wang & Fred Glover, 2020. "Advanced Tabu Search Algorithms for Bipartite Boolean Quadratic Programs Guided by Strategic Oscillation and Path Relinking," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 74-89, January.
    • Handle: RePEc:inm:orijoc:v:32:y:2020:i:1:p:74-89
    DOI: 10.1287/ijoc.2018.0871
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2018.0871
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2018.0871?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
    ---><---

    References listed on IDEAS

    as
    1. Mauricio G.C. Resende & Celso C. Ribeiro & Fred Glover & Rafael Martí, 2010. "Scatter Search and Path-Relinking: Fundamentals, Advances, and Applications," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, chapter 0, pages 87-107, Springer.
    2. Fred Glover & Gary A. Kochenberger & Bahram Alidaee, 1998. "Adaptive Memory Tabu Search for Binary Quadratic Programs," Management Science, INFORMS, vol. 44(3), pages 336-345, March.
    3. Yagiura, Mutsunori & Ibaraki, Toshihide & Glover, Fred, 2006. "A path relinking approach with ejection chains for the generalized assignment problem," European Journal of Operational Research, Elsevier, vol. 169(2), pages 548-569, March.
    4. Manuel Laguna & Rafael Marti, 1999. "GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization," INFORMS Journal on Computing, INFORMS, vol. 11(1), pages 44-52, February.
    5. GILLIS, Nicolas & GLINEUR, François, 2010. "Low-rank matrix approximation with weights or missing data is NP-hard," LIDAM Discussion Papers CORE 2010075, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    6. Wang, Yang & Lü, Zhipeng & Glover, Fred & Hao, Jin-Kao, 2012. "Path relinking for unconstrained binary quadratic programming," European Journal of Operational Research, Elsevier, vol. 223(3), pages 595-604.
    7. Carlton, William B. & Barnes, J. Wesley, 1996. "A note on hashing functions and tabu search algorithms," European Journal of Operational Research, Elsevier, vol. 95(1), pages 237-239, November.
    8. Lü, Zhipeng & Glover, Fred & Hao, Jin-Kao, 2010. "A hybrid metaheuristic approach to solving the UBQP problem," European Journal of Operational Research, Elsevier, vol. 207(3), pages 1254-1262, December.
    9. Glover, Fred & Ye, Tao & Punnen, Abraham P. & Kochenberger, Gary, 2015. "Integrating tabu search and VLSN search to develop enhanced algorithms: A case study using bipartite boolean quadratic programs," European Journal of Operational Research, Elsevier, vol. 241(3), pages 697-707.
    10. Karapetyan, Daniel & Punnen, Abraham P. & Parkes, Andrew J., 2017. "Markov Chain methods for the Bipartite Boolean Quadratic Programming Problem," European Journal of Operational Research, Elsevier, vol. 260(2), pages 494-506.
    11. R Aringhieri & R Cordone, 2011. "Comparing local search metaheuristics for the maximum diversity problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(2), pages 266-280, February.
    12. Rafael Martí & Abraham Duarte & Manuel Laguna, 2009. "Advanced Scatter Search for the Max-Cut Problem," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 26-38, February.
    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. Li, Mingjie & Hao, Jin-Kao & Wu, Qinghua, 2024. "A flow based formulation and a reinforcement learning based strategic oscillation for cross-dock door assignment," European Journal of Operational Research, Elsevier, vol. 312(2), pages 473-492.
    2. Wei, Zequn & Hao, Jin-Kao & Ren, Jintong & Glover, Fred, 2023. "Responsive strategic oscillation for solving the disjunctively constrained knapsack problem," European Journal of Operational Research, Elsevier, vol. 309(3), pages 993-1009.

    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. Punnen, Abraham P. & Wang, Yang, 2016. "The bipartite quadratic assignment problem and extensions," European Journal of Operational Research, Elsevier, vol. 250(3), pages 715-725.
    2. Glover, Fred & Ye, Tao & Punnen, Abraham P. & Kochenberger, Gary, 2015. "Integrating tabu search and VLSN search to develop enhanced algorithms: A case study using bipartite boolean quadratic programs," European Journal of Operational Research, Elsevier, vol. 241(3), pages 697-707.
    3. Wang, Yang & Lü, Zhipeng & Glover, Fred & Hao, Jin-Kao, 2012. "Path relinking for unconstrained binary quadratic programming," European Journal of Operational Research, Elsevier, vol. 223(3), pages 595-604.
    4. Wang, Yang & Wu, Qinghua & Glover, Fred, 2017. "Effective metaheuristic algorithms for the minimum differential dispersion problem," European Journal of Operational Research, Elsevier, vol. 258(3), pages 829-843.
    5. Fred Glover & Gary Kochenberger & Moses Ma & Yu Du, 2022. "Quantum Bridge Analytics II: QUBO-Plus, network optimization and combinatorial chaining for asset exchange," Annals of Operations Research, Springer, vol. 314(1), pages 185-212, July.
    6. Michele Samorani & Yang Wang & Yang Wang & Zhipeng Lv & Fred Glover, 2019. "Clustering-driven evolutionary algorithms: an application of path relinking to the quadratic unconstrained binary optimization problem," Journal of Heuristics, Springer, vol. 25(4), pages 629-642, October.
    7. Xiaoyuan Liu & Hayato Ushijima-Mwesigwa & Avradip Mandal & Sarvagya Upadhyay & Ilya Safro & Arnab Roy, 2022. "Leveraging special-purpose hardware for local search heuristics," Computational Optimization and Applications, Springer, vol. 82(1), pages 1-29, May.
    8. Bahram Alidaee & Haibo Wang, 2017. "A note on heuristic approach based on UBQP formulation of the maximum diversity problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(1), pages 102-110, January.
    9. Gili Rosenberg & Mohammad Vazifeh & Brad Woods & Eldad Haber, 2016. "Building an iterative heuristic solver for a quantum annealer," Computational Optimization and Applications, Springer, vol. 65(3), pages 845-869, December.
    10. Fred Glover & Gary Kochenberger & Rick Hennig & Yu Du, 2022. "Quantum bridge analytics I: a tutorial on formulating and using QUBO models," Annals of Operations Research, Springer, vol. 314(1), pages 141-183, July.
    11. Fernando Stefanello & Vaneet Aggarwal & Luciana S. Buriol & Mauricio G. C. Resende, 2019. "Hybrid algorithms for placement of virtual machines across geo-separated data centers," Journal of Combinatorial Optimization, Springer, vol. 38(3), pages 748-793, October.
    12. Martí, Rafael & Martínez-Gavara, Anna & Pérez-Peló, Sergio & Sánchez-Oro, Jesús, 2022. "A review on discrete diversity and dispersion maximization from an OR perspective," European Journal of Operational Research, Elsevier, vol. 299(3), pages 795-813.
    13. Fred Glover & Gary Kochenberger & Moses Ma & Yu Du, 2020. "Quantum Bridge Analytics II: QUBO-Plus, network optimization and combinatorial chaining for asset exchange," 4OR, Springer, vol. 18(4), pages 387-417, December.
    14. Ricardo N. Liang & Eduardo A. J. Anacleto & Cláudio N. Meneses, 2022. "Data structures for speeding up Tabu Search when solving sparse quadratic unconstrained binary optimization problems," Journal of Heuristics, Springer, vol. 28(4), pages 433-479, August.
    15. Lü, Zhipeng & Glover, Fred & Hao, Jin-Kao, 2010. "A hybrid metaheuristic approach to solving the UBQP problem," European Journal of Operational Research, Elsevier, vol. 207(3), pages 1254-1262, December.
    16. Fred Glover & Vicente Campos & Rafael Martí, 2021. "Tabu search tutorial. A Graph Drawing Application," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(2), pages 319-350, July.
    17. Wu, Qinghua & Hao, Jin-Kao, 2013. "A hybrid metaheuristic method for the Maximum Diversity Problem," European Journal of Operational Research, Elsevier, vol. 231(2), pages 452-464.
    18. Fuda Ma & Jin-Kao Hao, 2017. "A multiple search operator heuristic for the max-k-cut problem," Annals of Operations Research, Springer, vol. 248(1), pages 365-403, January.
    19. M Büther, 2010. "Reducing the elastic generalized assignment problem to the standard generalized assignment problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(11), pages 1582-1595, November.
    20. Seyedmohammadhossein Hosseinian & Dalila B. M. M. Fontes & Sergiy Butenko, 2020. "A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 747-762, July.

    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:inm:orijoc:v:32:y:2020:i:1:p:74-89. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.