Computationally efficient MIP formulation and algorithms for European day-ahead electricity market auctions

We consider the optimization problem implementing current market rules for European day-ahead electricity markets. We propose improved algorithmic approaches for that problem. First, a new MIP formulation is presented which avoids the use of complementarity constraints to express market equilibrium conditions, and also avoids the introduction of auxiliary continuous or binary variables. Instead, we rely on strong duality theory for linear or convex quadratic optimization problems to recover equilibrium constraints. When so-called stepwise bid curves are considered to describe continuous bids, the new formulation allows to take full advantage of state-of-the-art MILP solvers, and in most cases, an optimal solution including market prices can be computed for large-scale instances without any further algorithmic work. Second, the new formulation suggests a Benders-like decomposition procedure. This helps in the case of piecewise linear bid curves that yield quadratic primal and dual objective functions leading to a dense quadratic constraint in the formulation. This procedure essentially strengthens classical Benders cuts locally. Computational experiments using 2011 historical instances for the Central Western Europe region show excellent results. In the linear case, both approaches are very efficient, while for quadratic instances, only the decomposition procedure is appropriate. Finally, when most orders are block orders, and instances are combinatorially very hard, the direct MILP approach is substantially more efficient. (C) 2014 Elsevier By. All rights reserved.