Premium
Linear programing relaxations for a strategic pricing problem in electricity markets
Author(s) -
Fampa Marcia,
Pimentel Wagner
Publication year - 2016
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12293
Subject(s) - relaxation (psychology) , mathematical optimization , bidding , mathematics , linearization , heuristic , quadratically constrained quadratic program , semidefinite programming , quadratic growth , linear programming , quadratic programming , nonlinear system , algorithm , economics , psychology , social psychology , physics , quantum mechanics , microeconomics
Strategic bidding problems in energy markets have been vastly studied in the literature due to their economic importance and mathematical difficulty. In this paper, we consider this problem under the natural uncertainty associated to the competitors' bids and the system demand, and formulate it as a nonconvex quadratically constrained quadratic program. In order to solve this nonconvex maximization problem or to evaluate the quality of heuristic solutions, it is important to know good upper bounds to its optimal value. With this goal, we apply a cutting plane algorithm (CPA) to solve an extended linear relaxation of the problem, which is an outer approximation of a semidefinite relaxation. Valid inequalities are added to an initial linear relaxation at each iteration of the CPA improving the bound computed, including inequalities derived from reformulation linearization techniques (RLTs) and semidefinite programing (SDP) cuts that enforce the positive semidefiniteness of the matrix variable. SDP cuts are well known to considerably delay the solution of the relaxation because of their density, and therefore, we apply a sparsification procedure for the cuts, introduced by Margot et al. in [Margot, M., 2012]. We propose a modification to the algorithm in Margot et al. to better control the density of the SDP cuts; and after tuning the parameters of our algorithm, we show the trade‐off between the bounds and the density of the cuts for test instances derived from the Brazilian electric system.