TITLE:  Large-Scale Unit Commitment: Decentralized Mixed Integer Programming Approaches

ABSTRACT:

In this dissertation, we investigate theory and application of decentralized optimization for mixed integer programming (MIP) problems. Our focus is on loosely coupled MIPs where different blocks of the problem have mixed integer linear feasible sets and a small number of linear constraints couple these blocks together. We develop decentralized optimization approaches based on Lagrangian and augmented Lagrangian duals for such MIPs. The contributions of this dissertation are as follows: a) proof of exactness of augmented Lagrangian dual (ALD) for MIPs, b) decentralized exact and heuristic algorithms for MIPs, and c) application to decentralized unit commitment (UC).

First, we prove that ALD is able to close the duality gap for MIPs. In particular, we show that with non-negative level bounded augmenting functions, ALD is able to asymptotically achieve zero duality gap for MIPs, when the penalty coefficient is allowed to go to infinity. We further show that, under some mild conditions, using any norm as the augmenting function ALD is able to close the duality gap of a MIP with a finite penalty coefficient.  

Nonlinear objective functions in ALD destroy the decomposability which exists in classical Lagrangian dual for a loosely coupled MIP. A key challenge is that, because of the non-convex nature of MIPs, classical distributed and decentralized optimization approaches such as alternating direction method of multipliers (ADMM) cannot be applied directly to find their optimal solutions. We propose three exact and one heuristic decentralized algorithms, which are based on extensions of ADMM and dual decomposition techniques.

 Finally, we apply the developed algorithms to solve decentralized UC. We present mathematical formulations for the UC problem which are appropriate for the proposed decentralized algorithms. Privacy concerns of the participants in UC are taken into account in these formulations. We propose a solution approach for decentralized UC, which exploits the structure of UC in our decentralized algorithms. We present extensive computational experiments for solving UC instances with different decentralized approaches. We illustrate the challenges arising from nonconvexity of UC problem and show how the proposed algorithms overcome these challenges. We demonstrate remarkable performance of parallel implementation of the heuristic decentralized algorithm to solve large scale UC instances on power systems of more than 3,000 buses. We also show that for small UC instances, the proposed exact algorithms are able to find global optimal solutions.