Michael C. Caramanis

Ali Khodabakhsh, Ger Yang, Soumya Basu et al.

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.

Bowen Zhang, Michael C. Caramanis, John Baillieul

We propose and solve a stochastic dynamic programming (DP) problem addressing the optimal provision of regulation service reserves (RSR) by controlling dynamic demand preferences in smart buildings. A major contribution over past dynamic pricing work is that we pioneer the relaxation of static, uniformly distributed utility of demand. In this paper we model explicitly the dynamics of energy service preferences leading to a non-uniform and time varying probability distribution of demand utility. More explicitly, we model active and idle duty cycle appliances in a smart building as a closed queuing system with price-controlled arrival rates into the active appliance queue. Focusing on cooling appliances, we model the utility associated with the transition from idle to active as a non-uniform time varying function. We (i) derive an analytic characterization of the optimal policy and the differential cost function, and (ii) prove optimal policy monotonicity and value function convexity. These properties enable us to propose and implement a smart assisted value iteration (AVI) algorithm and an approximate DP (ADP) that exploits related functional approximations. Numerical results demonstrate the validity of the solution techniques and the computational advantage of the proposed ADP on realistic, large-state-space problems.