Associated Team STEM

2012- 2013 - Scientific achievements over the 3 years

Leaders

  • France: Luce Brotcorne, DOLPHIN project-team, Inria Lille, France
  • Canada: Gilles Savard, Polytechnic School of Montréal, Canada

Partners

Projet INRIA : DOLPHIN
Unité de recherche INRIA : Lille Nord Europe
Thème INRIA : NUM
Organisme étranger partenaire : CIRRELT Montréal Canada

Initial proposition

click here

Summary of the project

The economic rise of developing countries, together with the need to meet ever more stringent pollution reduction targets, will increase the stress on the global energy system. Within this framework, the goal of the current project is to develop decision tools for energy management in a context of market deregulation. We will focus on two issues, namely demand management and production planning.

The first problem is concerned with the efficient management of consumption. More precisely, the short or long term behaviour of customers can be influenced through signals sent by a utility (or several utilities) to the end-users. These signals can take the form of an "optimal" pricing scheme, or yet of devices (timers, automatic switches, etc.) designed to induce an "optimal" behaviour from the users.

The second issue is concerned with efficient management of sustainable energy production. Indeed the development of renewable energy introduces new parameters in the supply/demand global equilibrium process. The issue is to achieve the right trade-off between costs (production, security) and revenues when determining the daily hydro-electricity generation and storage within an environment where demand is stochastic.

The first problem is modeled as a bilevel program, the second one as a integer mutli-objective stochastic program. Efficient and effective solution methods are developed and implemented to solve these problems.

Project Description

The economic rise of developing countries, together with the need to meet ever more stringent pollution reduction targets, will increase the stress on the global energy system. To address this challenge, novel approaches to the production, distribution and consumption of energy will be required. Modern societies will have not only to invest massively in new technologies and reliable infrastructures, but also to achieve a delicate balance between supply and demand policies, taking into account the impact on the economy and the environment.

Within this framework, the goal of the current project is to develop decision tools for energy management in a context of market deregulation. We will focus on two central issues, namely demand management and production planning, for which optimization models will be developed, and efficient and effective solution methods will be implemented.

The first model is concerned with the efficient management of consumption. Quoting from Cappers et al. [1], demand response corresponds to "changes in electric usage by end-use customers from their normal consumption patterns in response to changes in the price electricity over time or to incentive payments designed to induce lower electricity use at times of high wholesale market prices or when reliability is jeopardized". Therefore, the short or long term behaviour of customers can be influenced through signals sent by a utility (or several utilities) to the end-users. These signals can take the form of an "optimal" pricing scheme, or yet of devices (timers, automatic switches, etc.) designed to induce an "optimal" behaviour from the users.

This setting perfectly fits the framework of bilevel programming, whereby the decisions of the leader(s), i.e., the utility (utilities), are taken under the perfect knowledge of the market reaction. Departing from more traditional "marginal cost" or "cost plus" policies, this approach allows for flexible pricing schemes that are not restricted to a predetermined class of policies. Of course, in order that the model be useful for predictive purposes, it should be based on sound theoretical bases, hence the emphasis put on the customer model.

More precisely, the bilevel energy consumption model can be described as follows. The leader consists in a utility that sets energy prices over time. It can also provide regulating devices that will help end-users optimize their consumption and therefore achieve global “green” targets. At the lower level (follower), demand is not provided by an exogenous demand function, but is driven by strategic consumers that minimize their disutility (defined as a combination a cost, quality of service, etc..) by considering the alternatives provided by an oligopoly of suppliers. The equilibrium resulting from the user behaviour can be deterministic or stochastic. For example, discrete choice models [2] can be used to adequately represent both the heterogeneity of the population and the random features of demand.

The second issue is concerned with efficient management of sustainable energy production. Indeed the development of renewable energy introduces new parameters in the supply/demand global equilibrium process. The issue is to achieve the right trade-off between costs (production, security) and revenues when determining the daily hydroelectricity generation and storage within an environment where demand is stochastic. More precisely, we focus the study on hydraulic energy production problems through a river valley where storage in reservoirs provides means to optimize revenues by taking advantage of the hourly fluctuations of spot prices. The problem, will be modelled as a nonlinear multi-period multiobjective mathematical program that involves revenue and security criteria, for which we will determine Pareto solutions. The security criteria are related to the minimum and maximum feasible water level in the valley. Production decisions have to be taken at each period (a week) taking into account weekly and yearly data estimation (on the spot prices, the demand, the water levels) refreshed at each period. Note that the spot prices are defined for one hour period and that production decisions may also vary for one hour periods. The complexity of the approach lies in the nonlinearity of functions modelling production costs (nonlinearities in turbine output) and security, as well as conservation constraints. Once a deterministic optimization problem is thoroughly understood, we will introduce uncertainty (related to the fluctuation of the demand and prices) into the model. This added element will require the development of new tools for estimating the Pareto front of the mathematical program representing the energy system.

All optimization problems involved in this project being NP-hard, the exact solution on real-life instances is out of reach. Rather, we aim for efficient hybrid heuristic approaches based on the structure of the problem. The efficiency of solution methods, both in terms of solution quality and computational time, will be assessed on randomly generated instances based on general parameters provided by energy companies with which the researchers involved in the project are collaborating.

[1] Cappers P., Gildman C., and Kathan D., Demand Response in U.S. electricity markets: Empirical Evidence, Energy, 35, pp. 1526-1535, 2010. [2] Ben Akiva M. and Lerman S., Discrete choice analysis: theory and application to travel demand, MIP press, 1985.

2012

Scientific achievements for 2012

In the first year of the Stem project the main scientific achievements concern the efficient consumption management problem. More precisely a state of the art on demand side management approaches in the energy field as well energy pricing problems in a deregulated market has first been conducted. This leads us to consider smart grid management in the context of Demand Side Management (DSM) . In this case, every customer is equipped with a smart meter which is a device that can be programmed to communicate with others and behave accordingly. Smart meters are capable of monitoring the price changes and schedule the consumption of individuals so that the total cost of energy is minimized. The device also enables the supplier to experience the effects of DSM measures in real time.

In the context of this project, a Stackelberg game that is played between a supplier and a group of customers equipped with smart meters (smart grid) is studied. The supplier decides on the prices for each time slot (24 hours in total in our case) and the smart grid decides when a customer uses a particular appliance. Every customer has a demand to utilize a certain appliance within a certain time window. Besides, it is assumed that the customers prefer earlier time slots rather than later ones. A waiting cost is also included in the lower model to reflect this particular situation.

On the other hand, if all customers are scheduled to the same time period, it might be very difficult for the supplier to provide the service since the demand might reach and exceed the available capacity. Therefore, a peak cost is included in the upper model to catch this situation.

Five bilevel models have been developed under different assumptions to analyse this problem. In the first model, it is assumed that the operations are pre-emptive, they can be stopped and continued later on. Also, their consumption can be decreased or increased. This model is designed for appliances like heating and cooling devices, refrigeration systems, air conditioning etc. Hence the lower level model is a type of load balancing problem.

However, not all appliances can be used in a pre-emptive fashion. For instance, a washing machine or a dish washer cannot be stopped or their consumption cannot be changed. A second model is designed to reflect the behaviour of these devices. In the second model, when an operation starts, it cannot be stopped (non-pre-emptive) and its consumption is fixed. The lower level model turns out to be an assignment problem.

Up to now, it is supposed that the supplier is a monopole. However, it may not be the case in reality. In the third model, there exists a competitor with known prices per hour and the leader tries to set his prices in such a way that he does not lose too many customers while not increasing the peak demand too much.

Finally, in the fourth model, it is assumed that there is one supplier with various sources of energy (power plants), like nuclear, solar, hydro, coal etc. In this setting, it is envisioned that the lower level is a discrete choice model. Lastly, a fifth model is designed in which prices are dependent on the hourly loads. Prices are monotonically increasing functions of hourly consumptions, hence the customers will try to lower the peak themselves to face lower prices.

Exact solution approaches based on two mixed integer programming (MIP) formulation have been developed for the first model. This model is bilinear-bilinear, therefore two different linearization techniques are applied after adding the optimality conditions of the lower level model to the upper level. Although the variables are continuous, integer variables are introduced after linearization of complementary slackness constraints. The two MIPs can be solved using a MIP programming solver like CPLEX. Some preliminary results are obtained on randomly generated instances.

The second issue of the project is concerned with efficient management of sustainable energy production namely the study on hydraulic energy production problems through a river valley. Storage energies through reservoirs provides means to optimize revenues by taking advantage of the hourly fluctuations of spot prices. In that context a state of the art on hydro-electric unit commitment problems and on hydro-electric scheduling problems has been done. We also specified a deterministic multiobjective hydro-electric energy production model (one objective being the revenue to maximize, the other one being security measure to respect).

Ongoing work

Concerning the energy demand management issue, we are studying properties and developing efficient solution methods for the bilevel models proposed in the first year. An invited talk in “Les Entretiens Jacques Cartier: Colloque Electricité Intelligente » in Lausanne will be given on that subject.

Concerning the efficient management of sustainable energy production we are specifying a stochastic multiobjective hydro-electric energy production models. The specification of the problem and the model definition are sharply related to the solution method development phase.

Conclusions

In conclusion Task 1.1.1 (State of the art, demand side management in the energy field, consumer behaviour models, energy pricing problems in a deregulated market, bilevel nonlinear models), Task 1.1.2 (1.1.2: Specification of consumer behaviour models), Task 1.1.3 (Specification of a bilevel models based on consumers models defined in 1.1.2 taking into account nonlinear properties of the revenue function.), Task 1.2.1 ( State of the art on hydro-electric unit commitment problems, on hydro-electric scheduling problems and on integer dynamic nonlinear stochastic programs. (mono or multiobjective)), Task 1.2.2 (Specification of deterministic multiobjective hydro-electric energy production) are done.

Task 2.1.1 (Solution methods development for efficient management of consumption) and Task 1.2.3 (Specification of stochastic multiobjective hydro-electric energy production models) are in progress.

Involved researchers and students for 2012

Visits from France to Canada

  1. El Ghazali Talbi visited the Canadian team from July 7th to July 13th
  2. Sezin Afsar (PhD) visited the Canadian team from September 1st to September 29th
  3. Luce Brotcorne visited the Canadian team from September 16th to September 21th
  4. Meeting between L. Brotcorne, G. Savard, M. Gendreau, S. Afsar in Lausanne during the in “Les Entretiens Jacques Cartier: Colloque Electricité Intelligente », Lausanne, November 15-16. 2012.

Visits from Canada to France

  1. Michel Gendreau visited the French Team from November 18th to November 23th
  2. Gilles Savard will visit the French Team from February 2 th 2013 to February 8 th 2013

Production/Publications

  1. “A Bilevel Approach to an Energy Pricing Problem Using Smart Grid Technology”, CIRRELT Seminar, talk given by S. Afsar , Montréal, September 20 th.
  2. “Tarification et Smart Grid Technology » invited talk (Luce Brotcorne) in “Les Entretiens Jacques Cartier: Colloque Electricité Intelligente », Lausanne, November 15, 16 2012.
  3. Séminaire de Michel Gendreau sur le "deterministic and stochastic unit commitment problem" à venir en novembre 2012.

Scientific achievements for the second year (2013)

A pricing approach for Demand Side Management

During this second year, we focused on the development of solution methods to solve the five models proposed during the first year. Indeed at the end of the first year we were only able to solve the first model. The approach was based on a reformulation of the problem as a Mixed Integer Program. Unfortunately solving this program using one of the shelf Integer programming software allows the solution of instances too small (with respect to the number of scheduled appliances) to be realistic. Therefore our goal was to design more efficient solution methods sharply based on the structure of the problems.

We focused mainly our attention on the models with competition in the pre-emptive and non pre-emptive case. The main difference between these two models is that in the non-pre-emptive case binary constraints on variables can not be relaxed. This sharply increases the difficult to define solution methods. Indeed a non convex second level program does not allow to use duality arguments to rewrite a bilevel model as a single level one.

During this year we mainly designed two types of solution methods (exact or heuristic). i) Exact method In the pre-emptive case (convex second level program), we first study the polyhedral structure of the feasible set to design new cuts. Including these cuts in the Mixed Integer formulation of the problem allows to solve more efficiently exactly larger instances. Nevertheless in order to tackle more realistic size instances we decided to design math-heuristic approaches. ii) Heuristic methods - The first heuristic is based on the structure of the customers problems (second level problem). More precisely for fixed prices we first assign the tasks to their favorite schedules. Next we compute the peak and shift from the peak one task (with the smallest waiting time interval) to another schedule. For this new feasible customer solution it is possible to determine the tariffs maximizing the revenue of the leader by solving a linear program, named inverse optimisation program. The algorithm iterates between these two steps ( shift in the customers' schedule and computation of tariffs) up to reaching a stopping criteria. This approach can be used for the pre-emptive and non pre-emptive case. In the non pre-emptive case a worst case analysis has been proposed. - The second heuristic is devoted the bilevel model with integer variables (the non pre-emptive case). It consists in defining some rules aiming to reduce the size of the exploration tree of the branch and bound algorithm.

These three solution approaches have been implemented. In order to test them we first had to settle a protocol to define randomly generated instances. Generating demand profiles close to reality was not an easy think.

Some preliminary results assess their quality to find good quality solutions in moderate computational time.

Efficient management of sustainable energy production

The problem we are dealing with can be defined as an Active Demand Side Management problem with PV energy in the residential sector. More precisely, with the rising prices of the retail electricity and the decreasing cost of the Pv technology, the self-consumption concept has sharply increases in most of the european countries. In more details, we consider the problem of the owner of a residential house equipped with Pv and batteries and connected to a grid. When producing its own electricity, the owner of the house has to decide to consume its own produced energy or to consume grid energy and storing the produced one or to consume grid energy and to sell to the grid the consumed energy. These decisions, sharply depending on the prices of electricity defined by the grid, can not be taken by the decision maker itself but by a smart meter equipped with a decision support tool.

The problem described hereafter can be modelled in its simplest version as a linear program by assuming that all the data (grid prices, weather previsions), demand are known a priori and that the battery follows a standard linear loading and unloading steps. Up to now, we solved it and provided some sensitivity analysis of the results to the parameter. Even if this problem has been recently considered by engineers, our approach is the first one to provide a numerical approach to solve it.

In conclusions For the first area, task 1 devoted to model definitions is finished. Task 2 devoted to numerical solution development and talk 3 devoted to validation are in progress.

For the second area, task 1 (formulation of the problem) was revised following discussions we had we some practice people during the meeting " Entretiens Jacques Cartier: Colloque Electricité Intelligente » held in Lausanne in 2012. Task 2 is in progress.

Exchange Program during the second year (2013)

Visits from France to Canada

  • Sezin Afsar (PhD) visited the Canadian team from May 13th to May 27th
  • Luce Brotcorne visited the Canadian team from September 21th to September 28th
  • Sezin Afsar (PhD) visited the Canadian team from September 21st to October 5th
  • Meeting between L. Brotcorne, S. Afsar, P. Marcotte in Rome during the Euro.

Visits from Canada to France

  • Michel Gendreau visited the French Team from November 12th to November 17th

Patrice Marcotte will visit the French Team from December 16th to December 21th

Production during the second year

  1. S Afsar, L Brotcorne, P. Marcotte, G. Savard: A Bilevel Approach for Energy Pricing Problem Using Smart Grids, Roadef , Troye, March 2013
  2. S Afsar, L Brotcorne, P. Marcotte, G. Savard: A Bilevel Approach for Energy Pricing Problem, Euro conference , Rome, July 2013.
  3. S Afsar, L Brotcorne, P. Marcotte, G. Savard "Bilevel Modeling for Demand Side Management in Energy Market", May 2013, ECCO, Paris
  4. A paper entitled "Smart Grid Pricing for demand side management" will be submitted to C&OR in a few days.

Scientific achievements over the 3 years

The economic rise of developing countries, together with the need to meet ever more stringent pollution reduction targets, increases the stress on the global energy system. Within this framework, the goal of the current project is to develop decision tools for energy management in a context of market deregulation. We focus on two issues, namely demand management and production planning.

The first problem is concerned with the efficient management of consumption. More precisely, the short or long term behaviour of customers can be influenced through signals sent by a utility (or several utilities) to the end-users. These signals can take the form of an "optimal" pricing scheme, or yet of devices (timers, automatic switches, etc.) designed to induce an "optimal" behaviour from the users.

The second issue is concerned with efficient management of sustainable energy production. Indeed the development of renewable energy introduces new parameters in the supply/demand global equilibrium process. The issue is for the owner of a green source of energy (a Pv Panel ,..) to achieve the right trade-off between consuming its own produced electricity or consuming grid energy while storing the produced one or finally selling to the grid the produced electricity.

The first problem is modeled as a bilevel program, the second one as a stochastic program. Efficient and effective solution methods are developed and implemented to solve these problems.

1) Bilevel Modelling for Energy Pricing Problems

Demand for energy grows very rapidly due to technological advancements. Instabilities trigger a chain of negative effects for all energy users, therefore many highly conservative measures are taken by energy suppliers in order to avoid a probable future imbalance. One of such precautions is keeping a large capacity which is a high cost solution. Therefore, demand side management (DSM) programs are often employed to control and manipulate the energy consumption at the customer side in order to meet capacity constraints DSM can be also defined as a group of methods that aims to shape utility's load curve. Load shifting is one of the most desired objectives and hence, the focus of this project. Peak load defines the minimum capacity level that should be kept by the supplier in order to sustain the balance. The fluctuations in the load curve are huge and the generation capacity is partially idle most of the time. It is also foreseen that the importance of load shifting will become even more apparent when plug-in hybrid electric cars are more spread out. The main contribution is a new way to model this problem using bilevel programming. (not used to model Energy Pricing Problem (EPP) before). Bilevel programming is a branch of mathematical programming where a static Stackelberg game is played between two decision makers. In bilevel setting, there is a leader who takes decisions while taking the reaction of the follower into consideration. Once the leader decides on his variables, the follower solves his own optimization problem taking leader's decisions as given. Bilevel programming framework is particularly advantageous when the two players have conflicting objectives. In the context of EPP, this method allows us to integrate DSM techniques and demand response into the optimization problem of an energy provider. Several bilevel programs are defined. Monopolist, competitive, preemptive and nonpreemptive variants are developed. The relation between an energy provider (leader) and its customers (follower) is analyzed. The customers are inter-connected via smart metering devices (automatic energy consumption scheduler (ECS) ). Therefore, the customers not only share an energy source, but also communicate with each other via the network of smart meters which is also referred as a smart grid. It is assumed that the leader applies dayahead pricing DSM method to control and smoothen the load curve. Without the smart grid technology, it is difficult for customers to keep track of hourly prices and shift their demand accordingly. Hence, it is not possible to observe the real demand response to the pricing strategy. Smart meter enables two-way information flow and constitutes an important aspect of the design by facilitating the correct application of DSM techniques and observation of the corresponding demand response. It is important to note that optimistic approach is used to model the problem, that is, when two solutions are identical for the follower, the one that is better for the leader is chosen. The objective function of the follower minimizes the total electricity payment of all customers besides minimizing the inconvenience cost of everyone. In other words, customers would like to buy electricity at the cheapest possible price without delaying their consumption too much. The objective function of leader is maximizing net revenue and has two terms: revenue and peak cost. Naturally, peak weight plays a central role in the function, the magnitude of it with respect to the prices sets the balance. The aim of including peak term in the objective function is to obtain a smoother load curve regarding the revenue. The revenue term that is maximized by leader and electricity cost that is minimized by the follower are the same which shows that two decision makers have conflicting objectives. One of the classical methods of solving a bilevel program is rearranging it into an equivalent mixed integer program (MIP). Then it becomes a still difficult but solvable problem using commercial solvers like CPLEX. However, it is a costly method in terms of time and memory resources. Besides solving the MIP with CPLEX, some heuristic algorithms are also developed in the context of this work. First heuristic method suggests that it is possible to find better suited schedules if the price vector is arranged in a better way. It is assumed that at the beginning, the leader gives the maximum possible prices to the customers and they choose their favorite time slots in order to use certain electrical appliances that they have. Naturally, this is the worst solution for both since both the peak load and prices are highest. After observing where the bottleneck is, or in other words, when peak occurs, leader offers lower prices for the following couple of hours. For instance, if peak is at 7 pm, leader offers lower prices from 8 to 11 pm. Some people would consider this discount worth for their waiting time and accept this offer. Others may find it inconvenient and keep using 7 pm. Hence, the schedule and load distribution would change. Once we obtain a different schedule, the corresponding optimal prices are calculated using Inverse Optimization (IO). Based on the new schedule, a new peak is found and the procedure is repeated until no further improvement is possible. The whole procedure takes only a few seconds. Second heuristic is based on the idea of using peak load information and performing a local search over it. First the algorithm determines the maximum and minimum possible peak load values. Then, it carries out a local search on peak load. It fixes this value, finds the best schedule for follower with respect to that and then calculates the corresponding optimal prices by IO. At the end of both heuristics, the MIP is solved with an extra constraint which fixes peak load. Hence, an optimistic solution is obtained. The algorithm itself takes about a couple of seconds and last step (MIP solution) is limited by 300 seconds. Experimental results based on randomly generated instances are performed. They put into highlight the efficiency of the heuristics to produce optimal or near optimal solution for large scale instances in moderate computation time . Moreover, results show that bilevel approach decreases peak cost of the leader and hence increases efficiency of the system while decreasing the total cost for customers. They further implicate that it is possible to convince some customers to shift their jobs to off-peak hours by offering them lower prices.

2) Optimization of PV energy consumption, production and storage in a smart house.

In this work we focus on optimizing energy flows for demand charge management in a gridconnected, photovoltaic (PV) and battery combined system in smart house. The smartly scheduled way of using, storing, generating, buying and selling energy allows customers to reduce electricity payments, to be less dependent on the grid and avoid creating peak power demand in the grid. Having renewable source of energy and domestic storage system the customers might take advantage of the energy price fluctuations. One can purchase the energy during low-cost hours, charge a battery during daytime, discharge it and sell surplus energy generated during the peak hours realizing cost savings. In this work we imply that solar energy produced could be used to satisfy a customer's demand and could be sold into a grid. To the best of our knowledge there is no model that takes into account both of these opportunities up to present. An electrical energy system considered in this work integrates a PV generator, AC to DC and DC to AC invertors, a storage system (or a battery), a grid connection and different loads representing the customers' demands. Most PV systems are used for DC electrical appliances (personal computer, electric cars, lights etc.) because the current produced by a PV cell is basically of the DC type. However a grid provides with AC electricity to run the AC appliances (fluorescent lights, radio, refrigerator etc.). Thus generally to convert the DC (AC) into AC (DC) electricity inverters are added to the system. However without loss of generality we neglect the energy losses during DC-AC conversion and we do not distinguish DC or AC electricity. The aim of this work is to manage with energy flows such that to satisfy the energy demands minimizing the total electrical customers' costs taking into account the profit received from selling surplus energy to the grid. For this purpose we propose a stochastic mathematical linear program. Stochastic program allow to make an optimal decision with the lack of perfect information, here about purchasing electricity prices and energy produced by PV generator. The preliminary simulations for deterministic and stochastic programs were implemented on test instances. Each instance for the stochastic model is 4-stage problem with 9 scenarios, each stage represents a point in time where decisions are made. All data (PV energy produced, energy demand, buying and selling energy prices, size of battery) were randomly generated. Input parameters for the deterministic model are the expectations of the corresponded stochastic input parameters. The difference in the instances is based on large variations of purchasing prices and PV energy produced,. The instances were solved by CPLEX in GAMS. For each instance we calculated the value of stochastic solution (VSS) that provides a measure of the gain of stochastic solution against deterministic one. These preliminary results are promising. Further perspectives are to generate a sufficient number of scenarios so that these scenarios cover the most plausible realizations of the considered stochastic process. We are planning to generate these scenarios based on realistic data about solar radiation, electricity hourly prices available at internet. The number of variables and constraints in the deterministic model grows linearly in the size of the problem so that it is solved by any linear programming optimization solver in a reasonable time. It is not the case for the stochastic program: the number of stochastic variables and associated constraints is dramatically increased in the size of input data, which if handled without care may lead to intractability. Thus we have to develop an appropriate procedure to deal with large-size program

Conclusion

The results obtained for the study of the two types of problems for energy demand and production management are innovative and are of the main interest for the OR community.