Presenter : Viet Hung NGUYEN - Professeur LIMOS, Université Clermont Auvergne

Abstract : In this talk, we address the problem of finding the best parameters of an electricity contract for a client based on her past records of electricity consumption over a fixed time period, typically one year.

The electricity bill is composed by some fixed cost, the cost of the subscription of the electricity contract and penalties due to overpowering of consumption. The problem can be formulated as a problem of minimizing a convex separable function with constraints featuring node-arc inciden matrix structure which can be solved in polynomial time by flow-based algorithms (Ahuja et al 2003, Karzanov et al 1997, Minoux 1984, Minoux 1986).

We propose a simple special purpose iterative algorithm for the deterministic version of the problem which has a better time complexity than the above cited algorithms.

We also consider a robust version of the problem using the concept of budget of uncertainty introduced by (Bertsimas and Sim 2004).

We prove that the resulting worst case cost minimisation problem can be solved by using the same algorithm as for the deterministic case.