Appendix B

Uncertainty is represented by a set of possible demand vectors. Each of these vectors-or scenarios-represents a limited amount of information about the system uncertainty. Each scenario is assigned a weight, , that reflects the possibility of its occurrence in the future.

The policy we are looking for must satisfy the constraint that if two different scenarios and are indistinguishable at time period on the basis of information available about them at time , then the decision made for scenario must be the same as that of scenario . The previous constraint is modeled by partitioning the scenario set at each time period into disjoint subsets

that are called scenario bundles. Clearly, a bundle at time is refined in subsequent time periods into smaller disjoint bundles [Rockafellar and Wets 1991].

To clarify the previous concept, assume that the unit commitment problem was solved for demand vectors, , which resulted in a three-dimensional array representing the status of each unit at each time period under each scenario, . The system administrator needs to make a decision concerning the status of each unit, , during the first time period based on the solutions obtained. In general, the values of , are not equal. An optimal decision cannot be made without reformulating the problem so that the decisions are the same for all and .

One must not only consider the first time period but must also take into account all subsequent bundles that could affect the decisions made throughout the study horizon. Two scenarios are members of the same bundle, , at time period if both of them have the same demand values for all time periods . Note that each scenario is a member of exactly one bundle at each time period, which motivates the notation . If two scenarios, and , are members of the same bundle at time , then their bundles in time periods are also the same. In other words, To represent the bundle constraints, we define to be the first period in which a scenario, , does not share a bundle with another scenario . We also define to be a scenario that shares the same bundle with at all time periods prior to and including . The bundle constraints are then written as

Mathematically, a bundle at time period is represented as a constraint on the decision variables, , of its scenarios. Adding the bundle constraints results in a large-scale mixed-integer quadratic program that combines unit commitment problems together. The objective function is to minimize the weighted sum of the objective functions of the smaller problems; that is, to minimize the expected cost over all possible scenarios. Here is the mathematical formulation:

and

We solve program (2) using a Lagrangian relaxation technique. A multiplier, , is associated with the bundle constraint on each variable . The corresponding penalty term, , is added to the objective function. The goal becomes maximizing the Lagrangian dual, , over all possible , where is given by: Then, the value of the Lagrange function, , is computed by solving minimization problems. Each of these problems is an independent unit commitment problem and can be solved as described in Appendix A. If the resulting primal solution is feasible, it provides an upper bound and provides a lower bound on the optimal value of (2). Otherwise, the penalties, , are updated and the process is repeated.