  Distribution network reconfiguration (DNR) is a tool used by operators to
balance line load flows and mitigate losses. As distributed generation and
flexible load adoption increases, the impact of DNR on the security,
efficiency, and reliability of the grid will increase as well. Today,
heuristic-based actions like branch exchange are routinely taken, with no
theoretical guarantee of their optimality. This paper considers loss
minimization via DNR, which changes the on/off status of switches in the
network. The goal is to ensure a radial final configuration (called a spanning
tree in the algorithms literature) that spans all network buses and connects
them to the substation (called the root of the tree) through a single path. We
prove that the associated combinatorial optimization problem is strongly
NP-hard and thus likely cannot be solved efficiently. We formulate the loss
minimization problem as a supermodular function minimization under a single
matroid basis constraint, and use existing algorithms to propose a polynomial
time local search algorithm for the DNR problem at hand and derive performance
bounds. We show that our algorithm is equivalent to the extensively used branch
exchange algorithm, for which, to the best of our knowledge, we pioneer in
proposing a theoretical performance bound. Finally, we use a 33-bus network to
compare our algorithm's performance to several algorithms published in the
literature.
