IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v25y2019i4d10.1007_s10732-018-9399-4.html
   My bibliography  Save this article

Diversification methods for zero-one optimization

Author

Listed:
  • Fred Glover

    (University of Colorado – Boulder)

  • Gary Kochenberger

    (University of Colorado at Denver)

  • Weihong Xie

    (Guangdong University of Technology)

  • Jianbin Luo

    (Guangdong University of Technology)

Abstract

We introduce new diversification methods for zero-one optimization that significantly extend strategies previously introduced in the setting of metaheuristic search. Our methods incorporate easily implemented strategies for partitioning assignments of values to variables, accompanied by processes called augmentation and shifting which create greater flexibility and generality. We then show how the resulting collection of diversified solutions can be further diversified by means of permutation mappings, which equally can be used to generate diversified collections of permutations for applications such as scheduling and routing. These methods can be applied to non-binary vectors using binarization procedures and by diversification-based learning procedures that provide connections to applications in clustering and machine learning. Detailed pseudocode and numerical illustrations are provided to show the operation of our methods and the collections of solutions they create.

Suggested Citation

  • Fred Glover & Gary Kochenberger & Weihong Xie & Jianbin Luo, 2019. "Diversification methods for zero-one optimization," Journal of Heuristics, Springer, vol. 25(4), pages 643-671, October.
  • Handle: RePEc:spr:joheur:v:25:y:2019:i:4:d:10.1007_s10732-018-9399-4
    DOI: 10.1007/s10732-018-9399-4
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-018-9399-4
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10732-018-9399-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. M Gallego & M Laguna & R Martí & A Duarte, 2013. "Tabu search with strategic oscillation for the maximally diverse grouping problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 64(5), pages 724-734, May.
    3. Vicente Campos & Manuel Laguna & Rafael Martí, 2005. "Context-Independent Scatter and Tabu Search for Permutation Problems," INFORMS Journal on Computing, INFORMS, vol. 17(1), pages 111-122, February.
    Full references (including those not matched with items on IDEAS)

    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. Zhou, Qing & Benlic, Una & Wu, Qinghua & Hao, Jin-Kao, 2019. "Heuristic search to the capacitated clustering problem," European Journal of Operational Research, Elsevier, vol. 273(2), pages 464-487.
    2. Lai, Xiangjing & Hao, Jin-Kao, 2016. "Iterated maxima search for the maximally diverse grouping problem," European Journal of Operational Research, Elsevier, vol. 254(3), pages 780-800.
    3. Jesús Sánchez-Oro & Manuel Laguna & Rafael Martí & Abraham Duarte, 2016. "Scatter search for the bandpass problem," Journal of Global Optimization, Springer, vol. 66(4), pages 769-790, December.
    4. 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.
    5. Parreño, Francisco & Álvarez-Valdés, Ramón & Martí, Rafael, 2021. "Measuring diversity. A review and an empirical analysis," European Journal of Operational Research, Elsevier, vol. 289(2), pages 515-532.
    6. 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.
    7. Fung, Richard Y.K. & Liu, Ran & Jiang, Zhibin, 2013. "A memetic algorithm for the open capacitated arc routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 50(C), pages 53-67.
    8. Martí, Rafael & Gallego, Micael & Duarte, Abraham, 2010. "A branch and bound algorithm for the maximum diversity problem," European Journal of Operational Research, Elsevier, vol. 200(1), pages 36-44, January.
    9. Daniel Porumbel & Jin-Kao Hao, 2020. "Distance-guided local search," Journal of Heuristics, Springer, vol. 26(5), pages 711-741, October.
    10. 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.
    11. 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.
    12. Yang, Xiao & Cai, Zonghui & Jin, Ting & Tang, Zheng & Gao, Shangce, 2022. "A three-phase search approach with dynamic population size for solving the maximally diverse grouping problem," European Journal of Operational Research, Elsevier, vol. 302(3), pages 925-953.
    13. Arne Schulz, 2022. "A new mixed-integer programming formulation for the maximally diverse grouping problem with attribute values," Annals of Operations Research, Springer, vol. 318(1), pages 501-530, November.
    14. Lai, Xiangjing & Hao, Jin-Kao & Fu, Zhang-Hua & Yue, Dong, 2021. "Neighborhood decomposition based variable neighborhood search and tabu search for maximally diverse grouping," European Journal of Operational Research, Elsevier, vol. 289(3), pages 1067-1086.
    15. A. D. López-Sánchez & J. Sánchez-Oro & M. Laguna, 2021. "A New Scatter Search Design for Multiobjective Combinatorial Optimization with an Application to Facility Location," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 629-642, May.
    16. Anna Martínez-Gavara & Vicente Campos & Micael Gallego & Manuel Laguna & Rafael Martí, 2015. "Tabu search and GRASP for the capacitated clustering problem," Computational Optimization and Applications, Springer, vol. 62(2), pages 589-607, November.
    17. 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.
    18. Geiza Silva & André Leite & Raydonal Ospina & Víctor Leiva & Jorge Figueroa-Zúñiga & Cecilia Castro, 2023. "Biased Random-Key Genetic Algorithm with Local Search Applied to the Maximum Diversity Problem," Mathematics, MDPI, vol. 11(14), pages 1-11, July.
    19. M Laguna & J Molina & F Pérez & R Caballero & A G Hernández-Díaz, 2010. "The challenge of optimizing expensive black boxes: a scatter search/rough set theory approach," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(1), pages 53-67, January.
    20. Schulz, Arne, 2021. "The balanced maximally diverse grouping problem with block constraints," European Journal of Operational Research, Elsevier, vol. 294(1), pages 42-53.

    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:spr:joheur:v:25:y:2019:i:4:d:10.1007_s10732-018-9399-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.springer.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.