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

Integrating tabu search and VLSN search to develop enhanced algorithms: A case study using bipartite boolean quadratic programs

Author

Listed:
  • Glover, Fred
  • Ye, Tao
  • Punnen, Abraham P.
  • Kochenberger, Gary

Abstract

The bipartite boolean quadratic programming problem (BBQP) is a generalization of the well studied boolean quadratic programming problem. The model has a variety of real life applications; however, empirical studies of the model are not available in the literature, except in a few isolated instances. In this paper, we develop efficient heuristic algorithms based on tabu search, very large scale neighborhood (VLSN) search, and a hybrid algorithm that integrates the two. The computational study establishes that effective integration of simple tabu search with VLSN search results in superior outcomes, and suggests the value of such an integration in other settings. Complexity analysis and implementation details are provided along with conclusions drawn from experimental analysis. In addition, we obtain solutions better than the best previously known for almost all medium and large size benchmark instances.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:241:y:2015:i:3:p:697-707
    DOI: 10.1016/j.ejor.2014.09.036
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221714007759
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2014.09.036?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. 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.
    2. 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).
    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. 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.
    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. Zeng, Zhizhong & Yu, Xinguo & He, Kun & Huang, Wenqi & Fu, Zhanghua, 2016. "Iterated Tabu Search and Variable Neighborhood Descent for packing unequal circles into a circular container," European Journal of Operational Research, Elsevier, vol. 250(2), pages 615-627.
    2. 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.
    3. 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.
    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. 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.
    6. Vladyslav Sokol & Ante Ćustić & Abraham P. Punnen & Binay Bhattacharya, 2020. "Bilinear Assignment Problem: Large Neighborhoods and Experimental Analysis of Algorithms," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 730-746, July.

    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. 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.
    2. 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.
    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. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Katayama, Kengo & Narihisa, Hiroyuki, 2001. "Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem," European Journal of Operational Research, Elsevier, vol. 134(1), pages 103-119, October.
    10. Gary Kochenberger & Jin-Kao Hao & Fred Glover & Mark Lewis & Zhipeng Lü & Haibo Wang & Yang Wang, 2014. "The unconstrained binary quadratic programming problem: a survey," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 58-81, July.
    11. García-Martínez, C. & Rodriguez, F.J. & Lozano, M., 2014. "Tabu-enhanced iterated greedy algorithm: A case study in the quadratic multiple knapsack problem," European Journal of Operational Research, Elsevier, vol. 232(3), pages 454-463.
    12. Gary Kochenberger & Fred Glover & Bahram Alidaee & Cesar Rego, 2005. "An Unconstrained Quadratic Binary Programming Approach to the Vertex Coloring Problem," Annals of Operations Research, Springer, vol. 139(1), pages 229-241, October.
    13. Namgil Lee & Jong-Min Kim, 2018. "Block tensor train decomposition for missing data estimation," Statistical Papers, Springer, vol. 59(4), pages 1283-1305, December.
    14. Tao Pham Dinh & Nam Nguyen Canh & Hoai Le Thi, 2010. "An efficient combined DCA and B&B using DC/SDP relaxation for globally solving binary quadratic programs," Journal of Global Optimization, Springer, vol. 48(4), pages 595-632, December.
    15. 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.
    16. Fred Glover & Jin-Kao Hao, 2016. "f-Flip strategies for unconstrained binary quadratic programming," Annals of Operations Research, Springer, vol. 238(1), pages 651-657, March.
    17. Goldengorin, Boris & Ghosh, Diptesh, 2004. "A Multilevel Search Algorithm for the Maximization of Submodular Functions," Research Report 04A20, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    18. Wang, Haibo & Alidaee, Bahram, 2019. "Effective heuristic for large-scale unrelated parallel machines scheduling problems," Omega, Elsevier, vol. 83(C), pages 261-274.
    19. Gillard, Jonathan & Usevich, Konstantin, 2018. "Structured low-rank matrix completion for forecasting in time series analysis," International Journal of Forecasting, Elsevier, vol. 34(4), pages 582-597.
    20. Glover, Fred & Lewis, Mark & Kochenberger, Gary, 2018. "Logical and inequality implications for reducing the size and difficulty of quadratic unconstrained binary optimization problems," European Journal of Operational Research, Elsevier, vol. 265(3), pages 829-842.

    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:241:y:2015:i:3:p:697-707. 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.