Forest-Based Formulation for the Balanced Connected k-Partition Problem

Peilin Chen (), Xulin Wang (), Xin Shu (), Yong Liu () and Pan Wang ()
Additional contact information
Peilin Chen: ByteDance Inc.
Xulin Wang: ByteDance Inc.
Xin Shu: ByteDance Inc.
Yong Liu: ByteDance Inc.
Pan Wang: ByteDance Inc.

A chapter in Operations Research Proceedings 2024, 2025, pp 187-192 from Springer

Abstract: Abstract Partitioning a graph into a fixed number of connected subgraphs with approximately equal weights is a fundamental problem in the fields of graph theory and combinatorial optimization. This problem finds applications in various domains such as farmland allocation, political districting, and sales territory design. However, existing mixed-integer programming (MIP) formulations for this problem struggle to handle large-scale problems, particularly as the number of required subgraphs increases, thereby limiting their practical applicability in real-world scenarios. In this paper, we propose a more compact forest-based formulation for this problem and validate its efficiency and scalability through computational experiments. It has been integrated into our sales territory design system.

Keywords: Combinatorial optimization; Integer programming; Graph theory (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:lnopch:978-3-031-92575-7_26

Ordering information: This item can be ordered from
http://www.springer.com/9783031925757

DOI: 10.1007/978-3-031-92575-7_26

Access Statistics for this chapter

More chapters in Lecture Notes in Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().