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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Peilin Chen,
  • Xulin Wang,
  • Xin Shu,
  • Yong Liu,
  • Pan Wang

摘要

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.