Partitioning a graph into balanced connected classes: Formulations, separation and experiments

Flávio K. Miyazawa

doi:10.1016/j.ejor.2020.12.059

Partitioning a graph into balanced connected classes: Formulations, separation and experiments

2021-09-01

17

PRE

AI

DOI：10.1016/j.ejor.2020.12.059

Original

Original request for help

Save

Abstract

En 中文

This work addresses the balanced connected k-partition problem (BCPk), which is formally defined as follows. Given a connected graph G = (V, E) with nonnegative weights on the vertices, find a partition {V-i}(i=1)(k) of V such that each class V-i induces a connected subgraph of G, and the weight of a class with the minimum weight is as large as possible. This problem, known to be NP-hard, has been largely investigated under different approaches and perspectives: exact algorithms, approximation algorithms for some values of k or special classes of graphs, and inapproximability results. On the practical side, BCPk is used to model many applications arising in image processing, cluster analysis, operating systems and robotics. We propose three linear programming formulations for BCPk. The first one contains only binary variables and a potentially large number of constraints that can be separated in polynomial time in the corresponding linear relaxation. We introduce new valid inequalities and design polynomial-time separation algorithms for them. The other two formulations are based on flows and have a polynomial number of constraints and variables. Our computational experiments show that the exact algorithms based on the proposed formulations outperform the other exact approaches presented in the literature. (C) 2021 Elsevier B.V. All rights reserved.

Keywords:

Integer programming

Branch-and-cut

Separation algorithm

Balanced partition

Connected partition

Partitioning a graph into balanced connected classes: Formulations, separation and experiments

Abstract

Journal

Organization