No description available.

In this dissertation we focus on two main topics. Under the first topic, we develop a new framework for stochastic network interdiction problem to address ambiguity in the defender risk preferences. The second topic is dedicated to computational studies of two-stage stochastic integer programs. More specifically, we consider two cases. First, we develop some solution methods for two-stage stochastic integer programs with continuous recourse; second, we study some computational strategies for two-stage stochastic integer programs with integer recourse. We study a class of stochastic network interdiction problems where the defender has incomplete (ambiguous) preferences. Specifically, we focus on the shortest path network interdiction modeled as a Stackelberg game, where the defender (leader) makes an interdiction decision first, then the attacker (follower) selects a shortest path after the observation of random arc costs and interdiction effects in the network. We take a decision-analytic perspective in addressing probabilistic risk over network parameters, assuming that the defender's risk preferences over exogenously given probabilities can be summarized by the expected utility theory. Although the exact form of the utility function is ambiguous to the defender, we assume that a set of historical data on some pairwise comparisons made by the defender is available, which can be used to restrict the shape of the utility function. We use two different approaches to tackle this problem. The first approach conducts utility estimation and optimization separately, by first finding the best fit for a piecewise linear concave utility function according to the available data, and then optimizing the expected utility. The second approach integrates utility estimation and optimization, by modeling the utility ambiguity under a robust optimization framework following \cite{armbruster2015decision} and \cite{Hu}. We conduct extensive computational experiments to evaluate the performances of these approaches on the stochastic shortest path network interdiction problem. In third chapter, we propose partition-based decomposition algorithms for solving two-stage stochastic integer program with continuous recourse. The partition-based decomposition method enhance the classical decomposition methods (such as Benders decomposition) by utilizing the inexact cuts (coarse cuts) induced by a scenario partition. Coarse cut generation can be much less expensive than the standard Benders cuts, when the partition size is relatively small compared to the total number of scenarios. We conduct an extensive computational study to illustrate the advantage of the proposed partition-based decomposition algorithms compared with the state-of-the-art approaches. In chapter four, we concentrate on computational methods for two-stage stochastic integer program with integer recourse. We consider the partition-based relaxation framework integrated with a scenario decomposition algorithm in order to develop strategies which provide a better lower bound on the optimal objective value, within a tight time limit.

Conventionally, to support varying power demand, the utility company must prepare to supply more electricity than actually needed, which causes inefficiency and waste. With the increasing penetration of renewable energy which is intermittent and stochastic, how to balance the power generation and demand becomes even more challenging. Demand response, which reschedules part of the elastic load in users' side, is a promising technology to increase power generation efficiency and reduce costs. However, how to coordinate all the distributed heterogeneous elastic loads efficiently is a major challenge and sparks numerous research efforts. In this thesis, we investigate different methods to provide demand response and improve power grid efficiency. First, we consider how to schedule the charging process of all the Plugged-in Hybrid Electrical Vehicles (PHEVs) so that demand peaks caused by PHEV charging are flattened. Existing solutions are either centralized which may not be scalable, or decentralized based on real-time pricing (RTP) which may not be applicable immediately for many markets. Our proposed PHEV charging approach does not need complicated, centralized control and can be executed online in a distributed manner. In addition, we extend our approach and apply it to the distribution grid to solve the bus congestion and voltage drop problems by controlling the access probability of PHEVs. One of the advantages of our algorithm is that it does not need accurate predictions on base load and future users' behaviors. Furthermore, it is deployable even when the grid size is large. Different from PHEVs, whose future arrivals are hard to predict, there is another category of elastic load, such as Heating Ventilation and Air-Conditioning (HVAC) systems, whose future status can be predicted based on the current status and control actions. How to minimize the power generation cost using this kind of elastic load is also an interesting topic to the power companies. Existing work usually used HVAC to do the load following or load shaping based on given control signals or objectives. However, optimal external control signals may not always be available. Without such control signals, how to make a tradeoff between the fluctuation of non-renewable power generation and the limited demand response potential of the elastic load, and to guarantee user comfort level, is still an open problem. To solve this problem, we first model the temperature evolution process of a room and propose an approach to estimate the key parameters of the model. Then, based on the model predictive control, a centralized and a distributed algorithm are proposed to minimize the fluctuation and maximize the user comfort level. In addition, we propose a dynamic water level adjustment algorithm to make the demand response always available in two directions. Extensive simulations based on practical data sets show that the proposed algorithms can effectively reduce the load fluctuation. Both randomized PHEV charging and HVAC control algorithms discussed above belong to direct or centralized load shaping, which has been heavily investigated. However, it is usually not clear how the users are compensated by providing load shaping services. In the last part of this thesis, we investigate indirect load shaping in a distributed manner. On one hand, we aim to reduce the users' energy cost by investigating how to fully utilize the battery pack and the water tank for the Combined Heat and Power (CHP) systems. We first formulate the queueing models for the CHP systems, and then propose an algorithm based on the Lyapunov optimization technique which does not need any statistical information about the system dynamics. The optimal control actions can be obtained by solving a non-convex optimization problem. We then discuss when it can be converted into a convex optimization problem. On the other hand, based on the users' reaction model, we propose an algorithm, with a time complexity of O(log n), to determine the RTP for the power company to effectively coordinate all the CHP systems and provide distributed load shaping services. / Graduate