The Battery Charging Problem and Linear Programs with Random Coefficient Matrix

This dissertation includes two main topics. First it concerns the problem of scheduling a generic battery energy storage in order to maximize the (expected) arbitrage as a result of optimizing charge and discharge decisions. We draw tools from network optimization and stochastic optimization, and reinforcement learning to analyze the problem and propose alternative solution methods. We reformulate a standard mixed integer linear formulation of a battery as a shortest path problem and as result we propose a polynomial algorithm to solve the problem in the deterministic setting. Then we study the optimization of a battery under the uncertainty of charge and discharge prices. We compare the performance of various policy generation methods in Markovian or near-Markovian settings to optimize expected arbitrage under price uncertainty. Our simulations leverage both a Markov model of prices and historical data to evaluate the relative performance of traditional stochastic optimization methods, such as two-stage stochastic programming and stochastic dynamic programming, against an approximate model-free method, Q-learning. The second topic of the dissertation, explores linear programs with random coefficient matrix. We first provide theoretical and computational results on the magnitude of optimal objective of linear programs with random coefficient matrix. Then we adapt an algorithm to find near-optimal solution of such programs. At last, we study two stage stochastic programs with random technology matrix and propose an algorithm for decoupling the first and second stages of these programs when the technology matrix is standard Gaussian.