IDEAS home Printed from https://ideas.repec.org/a/spr/snopef/v4y2023i4d10.1007_s43069-023-00249-w.html
   My bibliography  Save this article

An Efficient Heuristic for the k-Partitioning Problem

Author

Listed:
  • Pawel Kalczynski

    (California State University-Fullerton)

  • Zvi Goldstein

    (California State University-Fullerton)

  • Zvi Drezner

    (California State University-Fullerton)

Abstract

We investigate the k-partitioning problem, in which a set of items is divided into mutually exclusive and collectively exhaustive non-empty groups (clusters). The number of groups is given, and the distances between items, which may include weights, are defined. The sum of the distances between all members of the same group is calculated for each group, and the objective is to find the partition of the set of items that minimizes the sum of these individual sums. Two formulations of the problem are proposed and solved. In the first problem, the number of items in each group is given. In the second problem, there is no restriction on the number of items in each group. We propose an optimal algorithm for each of these two problems and an efficient heuristic algorithm that found all confirmed optimal solutions and improved several best-known solutions.

Suggested Citation

  • Pawel Kalczynski & Zvi Goldstein & Zvi Drezner, 2023. "An Efficient Heuristic for the k-Partitioning Problem," SN Operations Research Forum, Springer, vol. 4(4), pages 1-21, December.
    • Handle: RePEc:spr:snopef:v:4:y:2023:i:4:d:10.1007_s43069-023-00249-w
    DOI: 10.1007/s43069-023-00249-w
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s43069-023-00249-w
    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/s43069-023-00249-w?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. Zvi Drezner & Alfonsas Misevičius & Gintaras Palubeckis, 2015. "Exact algorithms for the solution of the grey pattern quadratic assignment problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 82(1), pages 85-105, August.
    2. A. Bagirov & B. Ordin & G. Ozturk & A. Xavier, 2015. "An incremental clustering algorithm based on hyperbolic smoothing," Computational Optimization and Applications, Springer, vol. 61(1), pages 219-241, May.
    3. Guillermo Durán & Mario Guajardo & Jaime Miranda & Denis Sauré & Sebastián Souyris & Andres Weintraub & Rodrigo Wolf, 2007. "Scheduling the Chilean Soccer League by Integer Programming," Interfaces, INFORMS, vol. 37(6), pages 539-552, December.
    4. Jack Brimberg & Pierre Hansen & Nenad Mladenović & Eric D. Taillard, 2000. "Improvements and Comparison of Heuristics for Solving the Uncapacitated Multisource Weber Problem," Operations Research, INFORMS, vol. 48(3), pages 444-460, June.
    5. Thiago Pereira & Daniel Aloise & Jack Brimberg & Nenad Mladenović, 2018. "Review of Basic Local Searches for Solving the Minimum Sum-of-Squares Clustering Problem," Springer Optimization and Its Applications, in: Panos M. Pardalos & Athanasios Migdalas (ed.), Open Problems in Optimization and Data Analysis, pages 249-270, Springer.
    6. Eugene L. Lawler, 1963. "The Quadratic Assignment Problem," Management Science, INFORMS, vol. 9(4), pages 586-599, July.
    7. Zvi Drezner & Pawel Kalczynski, 2017. "The continuous grey pattern problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(5), pages 469-483, May.
    8. Michael Brusco & Hans-Friedrich Köhn, 2009. "Clustering Qualitative Data Based on Binary Equivalence Relations: Neighborhood Search Heuristics for the Clique Partitioning Problem," Psychometrika, Springer;The Psychometric Society, vol. 74(4), pages 685-703, December.
    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. Brimberg, Jack & Kalczynski, Pawel & Drezner, Zvi, 2024. "Different formulations of the gray pattern problem and their optimal solutions," European Journal of Operational Research, Elsevier, vol. 316(1), pages 61-71.
    2. Schweiger, Katharina & Sahamie, Ramin, 2013. "A hybrid Tabu Search approach for the design of a paper recycling network," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 50(C), pages 98-119.
    3. Pawel Kalczynski & Jack Brimberg & Zvi Drezner, 2022. "Less is more: discrete starting solutions in the planar p-median problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(1), pages 34-59, April.
    4. Bolte, Andreas & Thonemann, Ulrich Wilhelm, 1996. "Optimizing simulated annealing schedules with genetic programming," European Journal of Operational Research, Elsevier, vol. 92(2), pages 402-416, July.
    5. Guillermo Durán, 2021. "Sports scheduling and other topics in sports analytics: a survey with special reference to Latin America," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(1), pages 125-155, April.
    6. Yunpeng Sun & Ruoya Jia & Asif Razzaq & Qun Bao, 2023. "RETRACTED ARTICLE: Drivers of China’s geographical renewable energy development: evidence from spatial association network structure approaches," Economic Change and Restructuring, Springer, vol. 56(6), pages 4115-4163, December.
    7. Karmitsa, Napsu & Bagirov, Adil M. & Taheri, Sona, 2017. "New diagonal bundle method for clustering problems in large data sets," European Journal of Operational Research, Elsevier, vol. 263(2), pages 367-379.
    8. Dorndorf, Ulrich & Drexl, Andreas & Nikulin, Yury & Pesch, Erwin, 2005. "Flight gate scheduling: State-of-the-art and recent developments," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 584, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    9. Chiang, Wen-Chyuan & Kouvelis, Panagiotis & Urban, Timothy L., 2006. "Single- and multi-objective facility layout with workflow interference considerations," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1414-1426, November.
    10. Caprara, Alberto, 2008. "Constrained 0-1 quadratic programming: Basic approaches and extensions," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1494-1503, June.
    11. Arora, Shalini & Puri, M. C., 1998. "A variant of time minimizing assignment problem," European Journal of Operational Research, Elsevier, vol. 110(2), pages 314-325, October.
    12. Abdelaziz, Fouad Ben & Maddah, Bacel & Flamand, Tülay & Azar, Jimmy, 2024. "Store-Wide space planning balancing impulse and convenience," European Journal of Operational Research, Elsevier, vol. 312(1), pages 211-226.
    13. Gerald Y. Agbegha & Ronald H. Ballou & Kamlesh Mathur, 1998. "Optimizing Auto-Carrier Loading," Transportation Science, INFORMS, vol. 32(2), pages 174-188, May.
    14. Dries Goossens & Jeroen Beliën, 2023. "Teaching Integer Programming by Scheduling the Belgian Soccer League," INFORMS Transactions on Education, INFORMS, vol. 23(3), pages 164-172, May.
    15. Hao Hu & Renata Sotirov, 2021. "The linearization problem of a binary quadratic problem and its applications," Annals of Operations Research, Springer, vol. 307(1), pages 229-249, December.
    16. Vittorio Maniezzo, 1999. "Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 11(4), pages 358-369, November.
    17. Tansel, Barbaros C. & Bilen, Canan, 1998. "Move based heuristics for the unidirectional loop network layout problem," European Journal of Operational Research, Elsevier, vol. 108(1), pages 36-48, July.
    18. D. J. White, 1993. "A parametric‐based heuristic program for the quadratic assignment problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(4), pages 553-568, June.
    19. Ceder, A. & Golany, B. & Tal, O., 2001. "Creating bus timetables with maximal synchronization," Transportation Research Part A: Policy and Practice, Elsevier, vol. 35(10), pages 913-928, December.
    20. Zvi Drezner & Said Salhi, 2017. "Incorporating neighborhood reduction for the solution of the planar p-median problem," Annals of Operations Research, Springer, vol. 258(2), pages 639-654, November.

    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:snopef:v:4:y:2023:i:4:d:10.1007_s43069-023-00249-w. 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.