Robust optimization of graph partitioning involving interval uncertainty

The graph partitioning problem consists of partitioning the vertex set of a graph into several disjoint subsets so that the sum of weights of the edges between the disjoint subsets is minimized. In this paper, robust optimization models with two decomposition algorithms are introduced to solve the graph partitioning problem with interval uncertain weights of edges. The bipartite graph partitioning problem with edge uncertainty is also presented. Throughout this paper, we make no assumption regarding the probability of the uncertain weights.