dual methods

Treball final de màster sobre mètodes duals aplicats a la l'optimització de problemes estocàstics de mercats elèctrics.

 El passat dimecres 16 de març es va presenta a la Facultat de Matemàtiques i estadística el treball de final de màster titulat Optimización de modelos estocásticos de mercado eléctrico múltiple mediante métodos duales realitzat per l'alumne Unai Aldasoro, del Màster d'Estadística i Investigació Operativa UPC-UB, sota la meva direcció. En aquest treball s'estudia l'aplicació del mètode d'optimització dual conegut com a proximal bundle method, descrit a [1] a la resolució del problema estocàstic d'optimització de l'oferta a mercats elèctrics múltiples desenvolupat a [2].

Aquest treball, que forma part del projecte de recerca del MICINN DPI2008-02153 i va ser sel·leccionat en la 4a convocatòria d'ajuts CERMET de la FME a la realització de treballs finals de màster, li ha estat concedida la menció "Matrícula d'Honor" per la Comissió de d'Avaluació  de Treballs Fí de Màster del MEIO, a proposta del tribunal que el va jutjar.

 
[1]  J. B. Hiriart-Urruty, C. Lemaréchal, Convex Analysis and Minimization Algorithms II – Advanced Theory and Bundle Methods. Springer-Verlag, 1993.

[2] Cristina Corchero, F.-Javier Heredia, Optimal Day-Ahead Bidding in the MIBEL's Multimarket Energy Production System, Proceedings of the 7th Conference on European Energy Market EEM10, Madrid, IEEE, pp. 1 - 6 , DOI: 10.1109/EEM.2010.5558714

Optimización de modelos estocásticos de mercado eléctrico múltiple mediante métodos duales

Publication TypeTesis de Grau i Màster // BSc and MSc Thesis
Year of Publication2011
AuthorsUnai Aldasoro Marcellan
DirectorF. Javier Heredia
Tipus de tesiMSc Thesis
TitulacióMàster in Statistics and Operations Research
CentreFacultat de Matemàtiques i Estadística, departament d'Estadística i Investigació Operativa, UPC
Data defensa16/03/2011
Nota // markMatrícula d'Honor (10/10)
Key Wordsteaching; research; dual methods; electricity markets; DPI2008-02153; mixed integer nonlinear programming; proximal bundle method; optimal day-ahead bid; electricity multimarket; MSc Thesis
AbstractEl presente trabajo plantea la resolución computacional de un modelo de optimización de la oferta de generación eléctrica para compañías eléctricas que participan en el mercado eléctrico liberalizado MIBEL. Dicho mercado se circunscribe a España y Portugal y se compone de una serie de subastas energéticas consecutivas donde el operador de mercado realiza para cada una de ellas la casación entre la oferta y demanda. Así, el objetivo de la compañía generadora será maximizar los beneficios obtenidos en la participación del conjunto de mercados teniendo en cuenta el cumplimiento de las obligaciones contractuales ya establecidas. El modelo matemático propuesto para su caracterización corresponde a un modelo de programación estocástica multietapa cuyo equivalente determinista es un problema de optimización cuadrática con variable binaria. Con el objetivo de aprovechar la estructura del problema se procede a plantear la dualización de un grupo de restricciones que producen que el problema original pueda ser dividido en subproblemas. Para su resolución se deberá estudiar la idoneidad de diversos métodos duales (subgradiente, Bundle Methods, ACCPM) y seleccionar el más conveniente para el caso abordado. La decisión finalmente adoptada ha consistido en elegir como método de resolución el algoritmo Proximal Bundle Method descrito en [18] y adaptado satisfactoriamente a problemas de coordinación de la generación hidro-térmica [17]. El análisis de método Proximal Bundle Method corresponderá a su compresión e interpretación gráfica, a la resolución de un ejemplo de pequeña escala de manera analítica y a su resolución computacional. El objetivo de la fase de resolución será valorar el proceso iterativo y la convergencia del Proximal Bundle Method aplicado al problema multimercado de oferta óptima y la comparación de resultados respecto a otro método dual como el método del subgradiente. La implementación computacional se realizará mediante el lenguaje C++, específicamente se utilizará el metalenguaje Concert Techonolgy creado por IBM para el enlace entre el código C++ y el solver CPLEX. Se comprueba que dicho lenguaje tiene como ventajas principales su simplicidad estructural y el compacto código que produce. No obstante la implementación del Proximal Bundle Method manifiesta una serie de limitaciones prácticas de Concert Technology en cuanto al almacenado y actualización de problemas de optimización. Se propone como línea de futuro el análisis de lenguajes alternativos. En todo caso, los resultados obtenidos desprenden que el Proximal Bundle Method se adapta satisfactoriamente al problema multimercado de oferta óptima, además se concluye que en la aplicación numérica considerada un tamaño de Bundle ilimitado produce los mejores resultados. Además en trabajo propone una serie de líneas de investigación futuras en las que destacan la paralelización de la resolución de los subproblemas, y la definición del subproblema asociado a cada térmica como un problema de caminos mínimos
DOI / handlehttp://hdl.handle.net/2099.1/13917
URLClick Here
ExportTagged XML BibTex

The Radar Subgradient Method Applied to the Unit Commitment Problem

Publication TypeConference Paper
Year of Publication2000
AuthorsF.-Javier Heredia; Cesar Beltrán
Conference Name9th Stockolm Optimization Days
Conference Date06/2000
Conference LocationStockholm, Sweden
Type of WorkContributed presentation
Key Wordsresearch, radar subgradient; guc
ExportTagged XML BibTex

Generalized unit commitment by the radar multiplier method

Publication TypeThesis
Year of Publication2001
AuthorsCesar Beltran
Academic DepartmentDept. of Statistics and Operations Research. Prof. F.-Javier Heredia, advisor.
Number of Pages147
UniversityUniversitat Politècnica de Catalunya
CityBarcelona
DegreePhD Thesis
Key Wordsresearch; radar multiplier; generalised unit commitment; teaching
AbstractThis operations research thesis should be situated in the field of the power generation industry. The general objective of this work is to efficiently solve the Generalized Unit Commitment (GUC) problem by means of specialized software. The GUC problem generalizes the Unit Commitment (UC) problem by simultane-ously solving the associated Optimal Power Flow (OPF) problem. There are many approaches to solve the UC and OPF problems separately, but approaches to solve them jointly, i.e. to solve the GUC problem, are quite scarce. One of these GUC solving approaches is due to professors Batut and Renaud, whose methodology has been taken as a starting point for the methodology presented herein. This thesis report is structured as follows. Chapter 1 describes the state of the art of the UC and GUC problems. The formulation of the classical short-term power planning problems related to the GUC problem, namely the economic dispatching problem, the OPF problem, and the UC problem, are reviewed. Special attention is paid to the UC literature and to the traditional methods for solving the UC problem. In chapter 2 we extend the OPF model developed by professors Heredia and Nabona to obtain our GUC model. The variables used and the modelling of the thermal, hydraulic and transmission systems are introduced, as is the objective function. Chapter 3 deals with the Variable Duplication (VD) method, which is used to decompose the GUC problem as an alternative to the Classical Lagrangian Relaxation (CLR) method. Furthermore, in chapter 3 dual bounds provided by the VDmethod or by the CLR methods are theoretically compared. Throughout chapters 4, 5, and 6 our solution methodology, the Radar Multiplier (RM) method, is designed and tested. Three independent matters are studied: first, the auxiliary problem principle method, used by Batut and Renaud to treat the inseparable augmented Lagrangian, is compared with the block coordinate descent method from both theoretical and practical points of view. Second, the Radar Sub- gradient (RS) method, a new Lagrange multiplier updating method, is proposed and computationally compared with the classical subgradient method. And third, we study the local character of the optimizers computed by the Augmented Lagrangian Relaxation (ALR) method when solving the GUC problem. A heuristic to improve the local ALR optimizers is designed and tested. Chapter 7 is devoted to our computational implementation of the RM method, the MACH code. First, the design of MACH is reviewed brie y and then its performance is tested by solving real-life large-scale UC and GUC instances. Solutions computed using our VD formulation of the GUC problem are partially primal feasible since they do not necessarily fulfill the spinning reserve constraints. In chapter 8 we study how to modify this GUC formulation with the aim of obtaining full primal feasible solutions. A successful test based on a simple UC problem is reported. The conclusions, contributions of the thesis, and proposed further research can be found in chapter 9.
URLClick Here
ExportTagged XML BibTex

Optimization algorithms for electricity market models

Idees:

  •  Calcular una LB mitjançant LR i passar-li aCPLEX.

Augmented Lagrangean Relaxation and Decomposition Applied to the Short-Term Hydrothermal Coordination Problem

Publication TypeConference Paper
Year of Publication1999
AuthorsBeltran, C.; Heredia, F. J.
Conference Name19th IFIP TC7 Conference on System Modelling and Optimization
Conference Date12-16/07/1999
Conference LocationCambridge, U.K.
Type of WorkContributed oral presentation
Key Wordsaugmented lagrangian relaxation; generalized unit commitment; block coordinated descent method; auxiliary principle problem; research
AbstractThe problem dealt with is called the Short-Term Hydrothermal Coordination (SHTC) problem. The objective of this problem is the optimization of electrical production and distribution, considering a short-term planning horizon (from one day to one week). Hydraulic and thermal plants must be coordinated in order to satisfy the customer demand of electricity at the minimum cost and with a reliable service. The model for the STHC problem presented here considers the thermal system, the hydraulic system and the distribution network. Nowadays the Lagrangean Relaxation (LR) method is the most widespread procedure to solve the STHC problem. The initial Classical Lagrangean Relaxation (CLR) method was improved by the Augmented Lagrangean Relaxation (ALR) method, although recent advances in the multiplier updating for the CLR method (cutting plane, bundle methods, etc.) have brought this classical method back into fashion. Two main advantages of the ALR method over the CLR method: (1) the ALR method allows us to obtain a saddle-point even in cases where the CLR method presents a duality gap. The solution of the STHC problem by the CLR method usually yields an infeasible primal solution $x_k$ due to the duality gap, whereas in the ALR method a solution of the dual problem provides a feasible primal solution. (2) The second advantage is that, using the CLR method, the differentiability of the dual function cannot be ensured and therefore nondifferentiable methods must be applied in the CLR method. This difficulty can be overcome if an augmented Lagrangean is used, since the dual function $q_c$ is differentiable for an appropriate c. Thus, the multipliers can be updated using ``large steps''. The main weakness of the ALR method is that the quadratic terms introduced by the augmented Lagrangean are not separable. If we want to solve the STHC problem by decomposition, some methods, such as the Auxiliary Problem Principle, or, as in our case, the Block Coordinate Descent method, must be used. However, the CLR method gives a separable Lagrangean. The starting point is the paper by Batut and Renaud [1] and therefore we use Variable Duplication plus the Augmented Lagrangean Relaxation (ALR) method. The method used by Batut and Renaud is improved theoretically and practically. From the theoretical point of view, the conservative Auxiliary Problem Principle is replaced by the Block Coordinate Descent Method that shows to be faster. From the practical point of view, an effective software package designed to solve the Optimum Short-Term Hydrothermal Coordination Problem, is incorporated in order to speed up the whole algorithm. Several medium to large scale instances of this problem have been solved showing the applicability of the proposed procedure.
ExportTagged XML BibTex

Generalized Unit Commitment (closed)

Under construction

SLOEGAT Project. Short and Long term Optimization of Energy Generation And Trading (Esprit 22695).

Publication TypeFunded research projects
Year of Publication1996
AuthorsF.-Javier Heredia
Type of participationFull time researcher
Duration12/1996-05/1999
Funding organizationEuropean Union, ESPRIT Programme
PartnersUniversidad Politécnica de Catalunya, Iberdrola, Universidad de Aachen, VEW Alemania, SIEMENS Austria
Full time researchers4 (DEIO/UPC)
Budget180.238€
Project codeEsprit 22695
Key Wordsresearch; nonlinear network flows; side constraints; power systems; transmission network; short-term hydrothermal coordination; long-term hydrothermal coordination project; public; competitive; EU
AbstractThe project aims to develop, implement and test, on a high performance computing platform, a software system to simulate and optimise the energy generation and trading coordination planning process in large electricity generating systems, both in the short (1 day-1 week) and medium to long term (one-two years). Special consideration will be given to this process to the growing importance of the energy trading problem in a deregulated market.
URLClick Here
ExportTagged XML BibTex

Planificación Óptima de Gran Dimensión de la Producción Hidrotérmica de Energía Eléctrica a Corto Plazo (TAP96-1044).

Publication TypeFunded research projects
Year of Publication1996
AuthorsF.-Javier Heredia
Type of participationFull time researcher
Duration07/1996-06/1999
Funding organizationMinisterio de Educación y Ciencia / Comisión Interministerial de Ciencia y Tecnologia
PartnersDepartament d'Estadística i Investigació Operativa / Universitat Politècnica de Catalunya
Full time researchers9
Budget56.428€
Project codeTAP96-1044
Key Wordsresearch; nonlinear network flows; side constraints; power systems; transmission network; short-term hydrothermal coordination; project; public; competitive; cicyt
ExportTagged XML BibTex

Planificación óptima de gran dimensión de la produción hidrotérmica de energia eléctrica (TAP99-1075-C02-01).

Publication TypeFunded research projects
Year of Publication2000
AuthorsF.-Javier Heredia
Type of participationFull researcher
Duration01/2000-12/2002
Funding organizationMinisterio de Educación y Ciencia / Comisión Interministerial de Ciencia y Tecnologia
PartnersDepartament d'Estadística i Investigació Operativa, Univ. Politècnica de Catalunya
Full time researchers5
Budget76.785€
Project codeTAP99-1075-C02-01
Key Wordsresearch; nonlinear network flows; side constraints; power systems; transmission network; short-term hydrothermal coordination; long-term hydrothermal coordination; project; public; competitive; cicyt
ExportTagged XML BibTex
Syndicate content