IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v68y2017i1d10.1057_s41274-016-0031-4.html
   My bibliography  Save this article

A note on heuristic approach based on UBQP formulation of the maximum diversity problem

Author

Listed:
  • Bahram Alidaee

    (The University of Mississippi)

  • Haibo Wang

    (Texas A&M International University)

Abstract

The maximum diversity problem (MDP) is a challenging NP-hard problem with a wide range of real applications. Several researchers have pointed out close relationship between the MDP and unconstrained binary quadratic program (UBQP). In this paper, we provide procedures to solve MDP ideas from the UBQP formulation of the problem. We first give some local optimality results for r-flip improvement procedures on MDP. Then, a set of highly effective diversification approaches based on sequential improvement steps for MDP are presented. Four versions of the approaches are used within a simple tabu search and applied to 140 benchmark MDP problems available on the Internet. The procedures solve all 80 small- to medium-sized problems instantly to the best known solutions. For 22 of the 60 large problems, the procedures improved by significant amounts the best known solutions in reasonably short CPU time.

Suggested Citation

  • 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.
    • Handle: RePEc:pal:jorsoc:v:68:y:2017:i:1:d:10.1057_s41274-016-0031-4
    DOI: 10.1057/s41274-016-0031-4
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/s41274-016-0031-4
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/s41274-016-0031-4?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. Duarte, Abraham & Marti, Rafael, 2007. "Tabu search and GRASP for the maximum diversity problem," European Journal of Operational Research, Elsevier, vol. 178(1), pages 71-84, April.
    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. Anonymous, 2013. "Introduction to the Issue," Journal of Wine Economics, Cambridge University Press, vol. 8(2), pages 129-130, November.
    4. 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.
    5. 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.
    6. Michel Gendreau & Alain Hertz & Gilbert Laporte, 1992. "New Insertion and Postoptimization Procedures for the Traveling Salesman Problem," Operations Research, INFORMS, vol. 40(6), pages 1086-1094, December.
    7. Anonymous, 2013. "Introduction to the Issue," Journal of Wine Economics, Cambridge University Press, vol. 8(3), pages 243-243, December.
    8. Alidaee, Bahram & Glover, Fred & Kochenberger, Gary & Wang, Haibo, 2007. "Solving the maximum edge weight clique problem via unconstrained quadratic programming," European Journal of Operational Research, Elsevier, vol. 181(2), pages 592-597, September.
    9. Bahram Alidaee & Gary Kochenberger & Haibo Wang, 2010. "Theorems Supporting r-flip Search for Pseudo-Boolean Optimization," International Journal of Applied Metaheuristic Computing (IJAMC), IGI Global, vol. 1(1), pages 93-109, January.
    10. 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.
    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. Wang, Haibo & Alidaee, Bahram, 2019. "Effective heuristic for large-scale unrelated parallel machines scheduling problems," Omega, Elsevier, vol. 83(C), pages 261-274.

    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. 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.
    2. Aringhieri, Roberto & Cordone, Roberto & Grosso, Andrea, 2015. "Construction and improvement algorithms for dispersion problems," European Journal of Operational Research, Elsevier, vol. 242(1), pages 21-33.
    3. Lozano, M. & Molina, D. & GarcI´a-MartI´nez, C., 2011. "Iterated greedy for the maximum diversity problem," European Journal of Operational Research, Elsevier, vol. 214(1), pages 31-38, October.
    4. 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.
    5. Ranjana Raghunathan, 2022. "Everyday Intimacies and Inter-Ethnic Relationships: Tracing Entanglements of Gender and Race in Multicultural Singapore," Sociological Research Online, , vol. 27(1), pages 77-94, March.
    6. Balint, T. & Lamperti, F. & Mandel, A. & Napoletano, M. & Roventini, A. & Sapio, A., 2017. "Complexity and the Economics of Climate Change: A Survey and a Look Forward," Ecological Economics, Elsevier, vol. 138(C), pages 252-265.
    7. Lamperti, Francesco & Bosetti, Valentina & Roventini, Andrea & Tavoni, Massimo & Treibich, Tania, 2021. "Three green financial policies to address climate risks," Journal of Financial Stability, Elsevier, vol. 54(C).
    8. Songsore, Emmanuel & Buzzelli, Michael, 2014. "Social responses to wind energy development in Ontario: The influence of health risk perceptions and associated concerns," Energy Policy, Elsevier, vol. 69(C), pages 285-296.
    9. 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.
    10. Tapsuwan, Sorada & Polyakov, Maksym & Bark, Rosalind & Nolan, Martin, 2015. "Valuing the Barmah–Millewa Forest and in stream river flows: A spatial heteroskedasticity and autocorrelation consistent (SHAC) approach," Ecological Economics, Elsevier, vol. 110(C), pages 98-105.
    11. Omar Al-Ubaydli & John List & Claire Mackevicius & Min Sok Lee & Dana Suskind, 2019. "How Can Experiments Play a Greater Role in Public Policy? 12 Proposals from an Economic Model of Scaling," Artefactual Field Experiments 00679, The Field Experiments Website.
    12. Nepomuceno, Marcelo Vinhal & Laroche, Michel, 2015. "The impact of materialism and anti-consumption lifestyles on personal debt and account balances," Journal of Business Research, Elsevier, vol. 68(3), pages 654-664.
    13. Bertschek, Irene & Kesler, Reinhold, 2022. "Let the user speak: Is feedback on Facebook a source of firms’ innovation?," Information Economics and Policy, Elsevier, vol. 60(C).
    14. Avelino, Flor & Wittmayer, Julia M. & Pel, Bonno & Weaver, Paul & Dumitru, Adina & Haxeltine, Alex & Kemp, René & Jørgensen, Michael S. & Bauler, Tom & Ruijsink, Saskia & O'Riordan, Tim, 2019. "Transformative social innovation and (dis)empowerment," Technological Forecasting and Social Change, Elsevier, vol. 145(C), pages 195-206.
    15. Gigi Foster, 2020. "The behavioural economics of government responses to COVID-19," Journal of Behavioral Economics for Policy, Society for the Advancement of Behavioral Economics (SABE), vol. 4(S3), pages 11-43, December.
    16. Audoly, Richard & Vogt-Schilb, Adrien & Guivarch, Céline & Pfeiffer, Alexander, 2018. "Pathways toward zero-carbon electricity required for climate stabilization," Applied Energy, Elsevier, vol. 225(C), pages 884-901.
    17. Gerards, Ruud & Welters, Ricardo, 2016. "Impact of financial pressure on unemployed job search, job find success and job quality," ROA Research Memorandum 008, Maastricht University, Research Centre for Education and the Labour Market (ROA).
    18. Cairns, George & Wright, George & Fairbrother, Peter, 2016. "Promoting articulated action from diverse stakeholders in response to public policy scenarios: A case analysis of the use of ‘scenario improvisation’ method," Technological Forecasting and Social Change, Elsevier, vol. 103(C), pages 97-108.
    19. Vasile-Daniel Păvăloaia & Elena-Mădălina Teodor & Doina Fotache & Magdalena Danileţ, 2019. "Opinion Mining on Social Media Data: Sentiment Analysis of User Preferences," Sustainability, MDPI, vol. 11(16), pages 1-21, August.
    20. Cailong Xu & Ruidong Li & Wenwen Song & Tingting Wu & Shi Sun & Shuixiu Hu & Tianfu Han & Cunxiang Wu, 2021. "Responses of Branch Number and Yield Component of Soybean Cultivars Tested in Different Planting Densities," Agriculture, MDPI, vol. 11(1), pages 1-12, 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:pal:jorsoc:v:68:y:2017:i:1:d:10.1057_s41274-016-0031-4. 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.palgrave-journals.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.