  This paper is about how to partition decision variables while decomposing a
large-scale optimization problem for the best performance of distributed
solution methods. Solving a large-scale optimization problem sequen- tially can
be computationally challenging. One classic approach is to decompose the
problem into smaller sub-problems and solve them in a distributed fashion.
However, there is little discussion in the literature on which variables should
be grouped together to form the sub-problems, especially when the optimization
formulation involves complex constraints. We focus on one of the most popular
distributed approaches, dual decomposition and distributed sub-gradient
methods. Based on a theoretical guarantee on its convergence rate, we explain
that a partition of variables can critically affect the speed of convergence
and highlight the importance of the number of dualized constraints. Then, we
introduce a novel approach to find a partition that reduces the number of
dualized constraints by utilizing a community detection algorithm from physics
literature. Roughly speaking, the proposed method groups decision variables
that appear together in con- straints and solves the resulting sub-problems
with blocks of variables in parallel. Empirical experiments on a real
application show that the proposed method significantly accelerates the
convergence of the distributed sub-gradient method. The advantage of our
approach becomes more significant as the size of the problem increases and each
constraint involves more variables.
