dual methods
Wed, 03/30/2011 - 11:00 — admin
 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
Wed, 03/30/2011 - 09:47 — admin
| Publication Type | Tesis de Grau i Màster // BSc and MSc Thesis |
| Year of Publication | 2011 |
| Authors | Unai Aldasoro Marcellan |
| Director | F. Javier Heredia |
| Tipus de tesi | MSc Thesis |
| Titulació | Màster in Statistics and Operations Research |
| Centre | Facultat de Matemàtiques i Estadística, departament d'Estadística i Investigació Operativa, UPC |
| Data defensa | 16/03/2011 |
| Nota // mark | Matrícula d'Honor (10/10) |
| Key Words | teaching; research; dual methods; electricity markets; DPI2008-02153; mixed integer nonlinear programming; proximal bundle method; optimal day-ahead bid; electricity multimarket; MSc Thesis |
| Abstract | El 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 / handle | http://hdl.handle.net/2099.1/13917 |
| URL | Click Here |
| Export | Tagged XML BibTex |
Fri, 12/31/2010 - 18:11 — admin
Wed, 12/29/2010 - 16:48 — admin
| Publication Type | Thesis |
| Year of Publication | 2001 |
| Authors | Cesar Beltran |
| Academic Department | Dept. of Statistics and Operations Research. Prof. F.-Javier Heredia, advisor. |
| Number of Pages | 147 |
| University | Universitat Politècnica de Catalunya |
| City | Barcelona |
| Degree | PhD Thesis |
| Key Words | research; radar multiplier; generalised unit commitment; teaching |
| Abstract | This 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.
|
| URL | Click Here |
| Export | Tagged XML BibTex |
Tue, 03/03/2009 - 17:10 — admin
Idees:
- Calcular una LB mitjançant LR i passar-li aCPLEX.
Mon, 10/29/2007 - 18:36 — admin
| Publication Type | Conference Paper |
| Year of Publication | 1999 |
| Authors | Beltran, C.; Heredia, F. J. |
| Conference Name | 19th IFIP TC7 Conference on System Modelling and Optimization |
| Conference Date | 12-16/07/1999 |
| Conference Location | Cambridge, U.K. |
| Type of Work | Contributed oral presentation |
| Key Words | augmented lagrangian relaxation; generalized unit commitment; block coordinated descent method; auxiliary principle problem; research |
| Abstract | The 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. |
| Export | Tagged XML BibTex |
Mon, 10/29/2007 - 16:21 — admin
Thu, 10/25/2007 - 00:30 — admin
Thu, 10/25/2007 - 00:23 — admin
Thu, 10/25/2007 - 00:19 — admin
|
