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. 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.
    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. 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.
    5. 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.
    6. 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.
    7. 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.
    8. Anonymous, 2013. "Introduction to the Issue," Journal of Wine Economics, Cambridge University Press, vol. 8(3), pages 243-243, December.
    9. 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.
    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. 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.
    3. 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.
    4. 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.
    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. 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.
    7. 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.
    8. 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).
    9. 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.
    10. 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.
    11. 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.
    12. 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).
    13. 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.
    14. 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.
    15. Caitlin Robinson & Stefan Bouzarovski & Sarah Lindley, 2018. "Underrepresenting neighbourhood vulnerabilities? The measurement of fuel poverty in England," Environment and Planning A, , vol. 50(5), pages 1109-1127, August.
    16. Michaela Haase & Emmanuel Raufflet, 2017. "Ideologies in Markets, Organizations, and Business Ethics: Drafting a Map: Introduction to the Special Issue," Journal of Business Ethics, Springer, vol. 142(4), pages 629-639, June.
    17. Rafael Alcadipani & Cíntia Rodrigues Oliveira Medeiros, 2020. "When Corporations Cause Harm: A Critical View of Corporate Social Irresponsibility and Corporate Crimes," Journal of Business Ethics, Springer, vol. 167(2), pages 285-297, November.
    18. Mansoora Ahmed & Sun Zehou & Syed Ali Raza & Muhammad Asif Qureshi & Sara Qamar Yousufi, 2020. "Impact of CSR and environmental triggers on employee green behavior: The mediating effect of employee well‐being," Corporate Social Responsibility and Environmental Management, John Wiley & Sons, vol. 27(5), pages 2225-2239, September.
    19. Licsandru, Tana Cristina & Cui, Charles Chi, 2018. "Subjective social inclusion: A conceptual critique for socially inclusive marketing," Journal of Business Research, Elsevier, vol. 82(C), pages 330-339.
    20. Giger, Markus & Mutea, Emily & Kiteme, Boniface & Eckert, Sandra & Anseeuw, Ward & Zaehringer, Julie G., 2020. "Large agricultural investments in Kenya’s Nanyuki Area: Inventory and analysis of business models," Land Use Policy, Elsevier, vol. 99(C).

    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.