In 2025 electricity production from wind power should constitute nearly 50 % of electricity demand in Denmark. In this paper we look at optimal expansion of the transmission network in order to integrate 50 % wind power in the system, while minimising total fixed investment cost and expected cost of power generation. We allow for active switching of transmission elements to eliminate negative effects of Kirchhoffs voltage law. Results show that actively switching transmission lines may yield a better utilisation of transmission networks with large- scale wind power and increased wind power penetration. Furthermore, transmission switching is likely to affect the optimal line capacity expansion plan.

We consider the application of Dantzig-Wolfe decomposition to stochastic integer programming problems arising in the capacity planning of electricity transmission networks that have some switchable transmission elements. The decomposition enables a column-generation algorithm to be applied, which allows the solution of large problem instances. The methodology is illustrated by its application to a problem of determining the optimal investment in switching equipment and transmission capacity for an existing network. Computational tests on IEEE test networks with 73 nodes and 118 nodes confirm the efficiency of the approach.

We introduce the concept of an offer distribution function to analyze randomized offer curves in multi-unit procurement auctions. We characterize mixed-strategy Nash equilibria for pay-as-bid auctions where demand is uncertain and costs are common knowledge; a setting for which pure-strategy supply function equilibria typically do not exist. We generalize previous results on mixtures over horizontal offers as in Bertrand-Edgeworth games, and we also characterize novel mixtures over partly increasing supply functions. We show that the randomization can cause considerable production inefficiencies.

We consider dynamic programming (DP) approximations to hydro-electric reservoir scheduling problems. The first class of approximate DP methods uses decomposition and multimodeling heuristics to produce policies that can be expressed as the sum of one-dimensional Bellman functions. This heuristic allows us to take into account non-convexities (appearing in models with head-effect) by solving a MIP at each time stage. The second class of methods uses cutting planes and sampling. It is able to provide multi-dimensional policies. We show that the cutting plane methods will produce better policies than the first DP approximation on two convex problem formulations of different types. Modifying the cutting plane method to approximate the effect of reservoir head level on generation also yields better results on problems including these effects. The results are illustrated using tests on two river valley systems.

We consider the incorporation of a time-consistent coherent risk measure into a multi-stage stochastic programming model, so that the model can be solved using a SDDP-type algorithm. We describe the implementation of this algorithm, and study the solutions it gives for an application of hydro-thermal scheduling in the New Zealand electricity system. The performance of policies using this risk measure at different levels of risk aversion is compared with the risk-neutral policy.

We discuss some ways of formulating quantile-type models for forecasting variations in wind power in the short term (within a few hours). Such models predict quantiles of the conditional distribution of the wind power available at some future time using information presently available. A natural reference for models of this kind is a "probabilistic persistence" quantile forecast whose only input is the present wind power. Using data from some New Zealand wind farms, we find that more complex quantile models can readily improve on probabilistic persistence in resolution but not in sharpness. The most valuable model inputs, apart from the present power, are found to be real-time air pressure measurements and a power total-variation indicator.

In recent years there has been a move in the majority of industrialized countries to invest in renewable resources for the production of energy. This move has come about as people worldwide are more aware of negative effects of fossil fuel sources of energy on the environment including the release of greenhouse gases such as CO2. Utilization of renewable sources of energy, for instance harnessing wind power in electricity production, is deemed to be reducing the use of fossil fuels and hence results in the reduction of CO2. Mechanisms that promote and facilitate utilization of renewable sources of energy are being developed. In particular, recently stochastic programming market clearing mechanisms have been suggested that would seemingly allow for a more efficient use of wind energy hence reduction of fossil fuel use, that ultimately would result in a reduction of CO2. In this paper we will examine the steady state behaviour of participants in an electricity market to fully analyze the hypothesis that the stochastic programming market clearing mechanism is less fossil fuel (and hence CO2) intensive than a conventional two settlement market through some simple examples.

The behaviour of DC Load-flow formulations when they are used in economic dispatch and nodal pricing models is discussed. It is demonstrated that non-negative prices in these models are sufficient to guarantee global optimality of any local optimum, even if the feasible region is not convex, and so a negative nodal price is an indicator of a possible loss in optimality. It is also discuss the possible effect that negative prices might have on algorithms that assume this convexity.

We consider the incorporation of a time-consistent coherent risk measure into a multi-stage stochastic programming model, so that the model can be solved using a SDDP-type algorithm. We describe the implementation of this algorithm, and study the solutions it gives for an application of hydro-thermal scheduling in the New Zealand electricity system. The performance of policies using this risk measure at different levels of risk aversion is compared with the risk-neutral policy.

Electricity market designs that decentralize decision making for participants can lead to inefficiencies in the presence of nonconvexity or missing markets. This has been shown in the case of unit-commitment problems that can make a decentralized market equilibrium less efficient than a centrally-planned solution. Less attention has been focused on systems with large amounts of hydro-electric generation. We describe the results of an empirical study of the New Zealand wholesale electricity market that attempts to quantify production efficiency losses by comparing market outcomes with a counterfactual central plan. (Updated October 11, 2010).

The inter-island HVDC line is a major transmission line in New Zealand, as it is the only link between its two islands. It enables the transfer of electricity between the South Island and the North Island. Because these transfers are generally beneficial to both the generators of the South Island and the consumers of the North Island, South Island generators are currently charged for the cost of the HVDC line based on a peak charge. We investigate an alternative scheme based on auctioning physical flow rights. Using a simplified supply-function equilibrium model we show that this is welfare optimizing in a perfectly competitive setting, but can result in inefficient dispatch and loss of rights revenue if generators bid for capacity strategically.

This paper (to appear in the Wiley Encyclopedia on OR/MS) gives an elementary account of techniques for modeling uncertainty in optimization problems.

Using the concept of market-distribution functions, we derive general optimality conditions for discriminatory divisible-good auctions, which are also applicable to Bertrand games and non-linear pricing. We introduce the concept of offer distribution function to analyze randomized offer curves, and characterize mixed-strategy Nash equilibria for pay-as-bid auctions where demand is uncertain and costs are common knowledge; a setting for which pure-strategy supply function equilibria typically do not exist. We generalize previous results on mixtures over horizontal offers as in Bertrand-Edgeworth games, but more importantly we characterize novel mixtures over partly increasing supply functions.

While operations research is utilized across all sectors of wholesale electricity markets, it is most widely and intensely used in the generation sector. We review the operations of a wholesale electricity market and provide a detailed treatment of optimization in the generation sector.

The idea of rearranging generation assets amongst firms to improve competition has once again surfaced in a recent report on improvements to the New Zealand Electricity Market. We show with examples that rearranging assets, either with asset divestiture to a new firm, or asset swaps between existing firms, may actually reduce competition in electricity markets. Our examples emphasize features that are particular to electricity, such as seasonality and transmission constraints. These results warn that applying economic rules of thumb to electricity markets may lead to erroneous conclusions.

Using the concept of market-distribution functions, we derive general optimality conditions for discriminatory divisible-good auctions, which are also applicable to Bertrand games and non-linear pricing. We introduce the concept of offer distribution function to analyze randomized offer curves, and characterize mixed-strategy Nash equilibria for pay-as-bid auctions where demand is uncertain and costs are common knowledge; a setting for which pure-strategy supply function equilibria typically do not exist. We generalize previous results on mixtures over horizontal offers as in Bertrand-Edgeworth games, but more importantly we characterize novel mixtures over partly increasing supply functions.

The behaviour of DC Load-flow formulations when they are used in economic dispatch and nodal pricing models is discussed. It is demonstrated that non-negative prices in these models are sufficient to guarantee global optimality of any local optimum, even if the feasible region is not convex, and so a negative nodal price is an indicator of a possible loss in optimality. It is also discuss the possible effect that negative prices might have on algorithms that assume this convexity.

The welfare of electricity producers and consumers depends on congestion in the transmission grid, generation costs that consist mainly of fuel costs, and strategic behavior. We formulate a game theoretic model of an oligopolistic electricity market where generation costs are derived from a fuel supply network. The game consists of a fuel dispatcher that transports fuels at minimum cost to meet generator demands, generators that maximize profit in Cournot competition, and an independent system operator (ISO) that sets nodal prices to balance electricity supply with linear demand functions. We prove the existence of an equilibrium. If fuel supplies are unlimited, the same equilibria hold in a simplified version of the game in which each generator optimizes its fuel acquisition from the network. In some very simple examples under different assumptions about the rationality of generators with respect to ISO decisions, paradoxical effects on total welfare can occur from expanding either electricity transmission capacity or the transportation capacity of low-cost fuel. We find some instances in which the paradox occurs only under bounded rationality of the generators, others where it occurs only if the generators are fully rational, and still others where it occurs to different degrees under the two rationality assumptions.

We discuss a stochastic-programming-based method for scheduling electric power generation subject to uncertainty. Such uncertainty may arise from either imperfect forecasting or moment-to-moment fluctuations, and on either the supply or the demand side. The method gives a system of locational marginal prices which reflect the uncertainty, and these may be used in a market settlement scheme in which payment is for energy only. We show that this scheme is revenue-adequate in expectation.

We examine the effect of introducing a carbon tax on electricity generation. We model this by way of a two generator Cournot game over a two node electricity network. We find that within the electricity system, emissions of carbon dioxide can increase after a carbon tax is introduced.

We discuss the almost-sure convergence of a broad class of sampling algorithms for multi-stage stochastic linear programs. Although the convergence of methods of this type is part of the stochastic programming folklore, we provide an explicit convergence proof based on the finiteness of the set of distinct cut coefficients. This differs from existing published proofs in that it does not require a restrictive assumption.

This tutorial is a PDF version of the Introduction to Stochastic Programming tutorial that is provided on the COSP site http:stoprog.org

We develop a generalized Nash equilibrium model with two players to compare the effects of using coincident-peak transmission charges with anytime-peak transmission charges. Players are assumed to be able to shift load between periods with a cost that grows quadratically with the amount shifted. When the shifting costs are large compared with peak charges, the model has a unique equilibrium. Coincident-peak charging and anytime-peak charging give different outcomes when the peak load for one purchaser does not coincide with the coincident peak. Coincident-peak charges favour purchasers whose peaks do not coincide with the system peak. They are more effective than anytime-peak charges at decreasing peak loads and therefore lowering peak charges.

We consider electricity pool markets in radial electricity transmission networks in which the lines have no transmission losses, but have transmission capacities. At each node there is a strategic generator submitting generation quantities to the pool. Prices are determined by a linear competitive fringe at each node. We derive necessary and sufficient conditions on the line capacities that ensure that the unconstrained one-shot Cournot equilibrium remains an equilibrium in the constrained network. These conditions are characterized by a convex polyhedral set.

This paper provides a technique based on stochastic programming to optimally solve the electricity procurement problem faced by a large consumer. Supply sources include bilateral contracts, a limited amount of self-production and the pool. Risk aversion is explicitly modeled using the CVaR methodology. Results from a realistic case study are provided and analyzed.

The market distribution function is a probabilistic device that can be used to model the randomness in dispatch and clearing price that generators in electricity pool markets must take account of when submitting offers. We discuss techniques for estimating the market distribution function, and ways of measuring the quality of these estimators, using both classical statistical approaches and an expected-foregone-revenue approach.

We present a model for the design of a minimum-cost, survivable electricity distribution network, which generalizes to telecommunications, logistics and other network types. We formulate this problem as a two-stage stochastic mixed-integer program in which first-stage decisions expand capacity, and recourse deicisions configure and operate the network so as to be feasible under various scenarios corresponding to individual link failures.

We discuss the effects of setting penalty costs on artificial variables in electricity dispatch software. It is shown under a feasibility assumption that a choice of these can be made to give no shortfalls in grid security and energy, but a possible shortfall in spinning reserve.

We consider an electricity generator making offers of energy into an electricity pool market over a horizon of several trading periods (typically a single trading day). The generator runs a set of generating units with given start-up costs, shut-down costs and operating ranges. At the start of each trading period the generator must submit to the pool system operator a new supply curve defining quantities of offered energy and the prices at which it wants these dispatched. The amount of dispatch depends on the supply curve offered along with the offers of the other generators and market demand, both of which are random, but do not change in response to the actions of the generator we consider. After dispatch the generator determines which units to run in the current trading period to meet the dispatch. The generator seeks a supply function that maximizes its expected profit. We describe an optimization procedure based on dynamic programming that can be used to construct optimal offers in successive time periods over a fixed planning horizon.

Interconnecting distinct electricity markets by adding a new transmission line affects the outcomes in these markets. We examine the effects of interconnection using market distribution functions. We give analytical formulae for computing market outcomes when the uncertain events in the markets being connected are statistically independent, and show by example how to compute these outcomes when these events are correlated.

We describe a general multi-stage stochastic integer-programming model for planning discrete capacity expansion of production facilities. A scenario tree represents uncertainty in the model. Variable splitting leads to two forms of this model: the first allows multiple expansions of each facility over the planning horizon while the second allows at most one. Dantzig-Wolfe decomposition of either split-variable model results in a binary master problem that solves easily, as its linear-programming relaxation tends to yield integer solutions. For each scenario-tree node, the decomposition defines a subproblem that may be viewed as a single-period, deterministic capacity-expansion problem. An effective solution procedure results as long as the subproblems solve efficiently, and the procedure incorporates a good “duals stabilization scheme”. We present computational results for a model to plan the capacity expansion of a real-world electricity distribution network given uncertain future demand. The largest problem we solve to optimality has 6 stages and 243 scenarios corresponding to a deterministic equivalent with a quarter of a million binary variables.

We consider a purchaser of electricity, bidding into a wholesale electricity pool market that operates a day ahead of dispatch. The purchaser must arrange purchase for an uncertain demand that occurs the following day. Deviations from the day-ahead purchase are bought in a secondary market. We study conditions under which the retailer should bid their expected demand, and derive conditions on the optimal demand curve that they should bid if the behaviour of the other participants is unknown, but can be modelled by a market distribution function.

In an electricity pool market, each generator is required to submit a supply function (offer stack), indicating how much power it will generate as a function of the price. For a generator operating a hydro-electric reservoir, the optimal stack to offer in each trading period over a planning horizon can be computed using dynamic programming. However, the market trading period (usually 1 hour or less) may be much shorter than the inherent time scale of the reservoir (often many months). We devise a dynamic programming model for such situations in which each stage represents many trading periods. In this model, the decision made at the beginning of each stage consists of a target mean and variance of the water release in the coming stage. This decomposes the problem into inter-stage and intra-stage subproblems. The application of the model to a real generation system is described.

The paper presents a convergence proof for a broad class of sampling algorithms for multi-stage stochastic linear programs in which the uncertain parameters occur only in the constraint right-hand sides. This class includes SDDP, AND, ReSa, and CUPPS. We show under an independence assumption on the sampling procedure that the algorithms converge with probability 1.

We describe a mixed integer programming model for scheduling mechanical pulp production with uncertain electricity prices.

The New Zealand transmission grid operator Transpower uses special constraints in the SPD dispatch software to ensure that in the event of a single transmission line failure, remaining circuits are not over-loaded. We discuss a mechanism by which these constraints might be able to be relaxed by making use of interruptible load.

We consider a simple game-theoretical model in which an electricity retailer and a network owner offer incentives to consumers to shift load from a peak period to an off-peak period. Using a simple example we compare the market outcomes from collusion with those from the equilibrium of a non-cooperative game, and examine the behaviour in this game when it is repeated in a situation in which agents have imperfect information.

The market distribution function is a probabilistic device that can be used to model the randomness in dispatch and clearing price that generators in electricity pool markets must take account of when submitting offers. We discuss techniques for estimating the market distribution function, and ways of measuring the quality of these estimators, using both classical statistical approaches and in the context of optimization.

This paper studies financial transmission rights in electricity pool markets with nodal pricing, when these rights are to be allocated by an auction mechanism. We prove that simultaneous feasibility entails revenue adequacy in a general framework of convex optimization, and show by counterexample how this result might fail in the absence of convexity. A market distribution function approach is used to investigate the effects on electricity offering behaviour when participants hold financial transmission rights, and the implications of this for the auction design are discussed. The paper also discusses the incentives provided by financial transmission rights for encouraging investment in network transmission capacity.

In an electricity pool market the market distribution function gives the probability that a generator offering a certain quantity of power at a certain price will not be dispatched all of this quantity by the pool. It represents the uncertainty in a pool market associated with the offers of the other agents as well as demand. We present a general Bayesian update scheme for market distribution functions. To illustrate the approach a particular form of this procedure is applied to real data obtained from a New Zealand electricity generator.

We consider a generator making offers of energy into an electricity pool market. For a given time period, it must submit an offer stack, consisting of a fixed number of quantities of energy and prices at which it wants these quantities dispatched. We assume that the generator cannot offer enough power to substantially affect the market price, so the optimal response would be to offer energy at marginal cost. However, the market rules do not permit an arbitrary function, so the problem is to find an offer stack approximating marginal cost in a way that maximizes its profit. We give optimality conditions for this problem and derive an optimization procedure based on dynamic programming. This procedure is illustrated by applying it to several examples with different costs of production.

In a nodal spot market for electricity, there may be circumstances in which generators may wish to offer energy at negative prices, e.g. to avoid being shut down for a short period. Such behaviour can create some severe computational difficulties for the system dispatcher. The ``must-run dispatch auction" is a system used to handle such cases in New Zealand; we construct an equilibrium model for generators' behaviour in the auction under stochastic demands. An interesting feature of the auction is that its outcome may be economically sub-optimal even under very idealized assumptions of perfect competition.

We consider wholesale electricity market pools in which generators must offer supply functions that are centrally dispatched. Each generator seeks a supply function to offer to the spot market, so as to maximise expected return. We give conditions under which a supply function exists that optimises return for every demand realisation. We also analyse the case in which the behaviour of the competition can be modelled by an appropriate probability distribution, and derive optimality conditions for the optimal supply-function offer in this case. The paper concludes with some remarks on applying the theory to the case where each generator must offer a limited number of prices in their stack.

In this paper we study strategies for generators making offers into electricity markets in circumstances where both the demand for electricity and the behaviour of competing generators is unknown, but can be represented by a probability distribution. Given this probability distribution we derive necessary optimality conditions for a broad class of supply offer curves. We show how these can be used to construct an optimal solution for a simple example. We also consider the case where a generator is restricted in the number of prices at which power can be offered.

In this paper we study strategies for generators making offers into electricity markets in circumstances where demand is unknown in advance. We concentrate on a model with smooth supply functions and derive conditions under which a single supply function can represent an optimal response to the offers of the other market participants over a range of demands. In order to apply this approach in practice it may be necessary to approximate the supply functions of other players. We derive bounds on the loss in revenue that occurs in comparison with the exact supply function response, when a generator uses an approximation both for its own supply function and for the supply functions of other players. We also demonstrate the existence of symmetric supply-function equilibria.

We consider the problem of offering electricity produced by a series of hydroelectric reservoirs to a pool-type central market. The market model is a simplified version of the New Zealand wholesale electricity market, with prices modelled by a stochastic process. The demand for electricity is not explicitly modelled. The hydroelectric generator is assumed to be unable to influence market prices (i.e. to be a price-taker). We discuss the resulting stochastic dynamic program, methods for its solution, and the explicit optimal offer curves that it produces.

We consider the problem of scheduling daily hydro-electricity generation in a river valley. Each generating station in this river valley has a number of turbines which incur fixed charges on startup and have a generation efficiency which varies nonlinearly with flow. With appropriate approximations the problem of determining what turbine units to commit in each half hour of the day can be formulated as a large mixed-integer linear programming problem. In practice the generation required from this group of stations in each half hour is often different from that forecast. We investigate the impact of this uncertainty on the unit commitment by using an optimization-based heuristic to give an approximate solution to the stochastic problem.

Spot prices of electricity are determined in New Zealand (and a number of other electricity markets in the world) using a linear programming model to construct a dispatch schedule to meet metered loads at the nodes of the transmission network. The linear program seeks to minimise in each half hour the delivered cost of the energy, as represented by the prices that generators offer their power to the market, while accounting for transmission losses, network constraints and spinning reserve constraints. The ex-post electricity price at any given node of the transmission system is given by the shadow price of the energy balance constraint at optimality. We discuss the results of some experiments carried out with a small electricity pricing model developed in the Department of Engineering Science. The prices obtained from these linear programming models have some interesting properties. Some of these properties, although counterintuitive, have rational explanations. Other properties are less benign, and arise in circumstances when a linear programming model is an inappropriate approximation of the true load flow problem. We shall explain these effects, and discuss some possible remedies.