Um Algoritmo Branch-and-Price para Instâncias de Grande Porte do Modelo Brasileiro de Planejamento da Expansão da Geração de Energia Elétrica a Longo Prazo
Autores
|
5442 |
918,44,519
|
|
|
5443 |
918,44,519
|
|
|
5444 |
918,44,519
|
Informações:
Publicações do PESC
Título
Um Algoritmo Branch-and-Price para Instâncias de Grande Porte do Modelo Brasileiro de Planejamento da Expansão da Geração de Energia Elétrica a Longo Prazo
Linha de pesquisa
Otimização
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
21/6/2013
Resumo
Desde meados da década de 90, o CEPEL vem desenvolvendo o modelo computacional MELP para o problema do planejamento da expansão da geração a longo prazo do sistema elétrico brasileiro. Para reduzir a complexidade do problema, foram adotadas hipóteses simplificadoras que permitiram derivar uma formulação com base em Programação Linear Inteira Mista, adotando como metodologia de solução o algoritmo Branch-and-Cut disponível em um software comercial no estado-da-arte.
Estudos recentes evidenciaram a necessidade de uma modelagem mais detalhada de certos aspectos do problema, que aumentam as dimensões das instâncias e comprometem a resolução do mesmo sob o ponto de vista computacional. Por exemplo, para uma análise operativa em base semestral ou com um maior número de patamares de demanda, nem mesmo a relaxação linear do problema pode ser obtida em tempo computacional aceitável para o sistema elétrico brasileiro. Com isso, a metodologia de solução adotada tornou-se inadequada.
Este trabalho teve por objetivo desenvolver uma nova metodologia de otimização exata para o modelo MELP capaz de tratar instâncias de grande porte do problema. Para isto foi proposto para o mesmo uma nova formulação matemática e, com base nesta, desenvolvido um algoritmo do tipo Branch-and-Price. Este algoritmo apresenta certas características diferentes daqueles encontrados na literatura, como o procedimento de estabilização dos duais e a regra de ramificação para a árvore de enumeração guiada por limites primais ao invés dos limites duais. São feitas aplicações do algoritmo para instâncias anteriormente intratáveis do problema em questão.
Estudos recentes evidenciaram a necessidade de uma modelagem mais detalhada de certos aspectos do problema, que aumentam as dimensões das instâncias e comprometem a resolução do mesmo sob o ponto de vista computacional. Por exemplo, para uma análise operativa em base semestral ou com um maior número de patamares de demanda, nem mesmo a relaxação linear do problema pode ser obtida em tempo computacional aceitável para o sistema elétrico brasileiro. Com isso, a metodologia de solução adotada tornou-se inadequada.
Este trabalho teve por objetivo desenvolver uma nova metodologia de otimização exata para o modelo MELP capaz de tratar instâncias de grande porte do problema. Para isto foi proposto para o mesmo uma nova formulação matemática e, com base nesta, desenvolvido um algoritmo do tipo Branch-and-Price. Este algoritmo apresenta certas características diferentes daqueles encontrados na literatura, como o procedimento de estabilização dos duais e a regra de ramificação para a árvore de enumeração guiada por limites primais ao invés dos limites duais. São feitas aplicações do algoritmo para instâncias anteriormente intratáveis do problema em questão.
Abstract
Since mid-90’s the Brazilian Electric Energy Research Center has been developing the MELP computational model for the Brazilian long term power generation expansion planning problem. In order to reduce the problem complexity some assumptions have been adopted and a mathematical formulation based on Mixed Integer Linear Programming has been derived. Such formulation is solved by a Branch-and-Cut algorithm available in a state-of-the-art commercial optimization package.
Recent analysis has highlighted the need of modeling enhancement of some aspects of the problem, which will increase the scale of the instances and the computational effort. As an example, an operative analysis on seasonal basis instead of annual basis, or considering more than two energy demand levels, even the linear relaxation of the problem could not be attained in a reasonable computational time.
The objective of this work is the development of an exact optimization procedure for the MELP model to tackle large scale instances of the problem. Based on a mathematical reformulation derived for MELP model, a Branch-and-Price algorithm has been developed. The proposed algorithm deals with some relevant points in a nonstandard way, like the duals stabilization procedure and the branch rules for the enumeration tree guided by primal bounds instead of dual bounds. The proposed algorithm is applied to previously untractable large scale instances of the problem.
Recent analysis has highlighted the need of modeling enhancement of some aspects of the problem, which will increase the scale of the instances and the computational effort. As an example, an operative analysis on seasonal basis instead of annual basis, or considering more than two energy demand levels, even the linear relaxation of the problem could not be attained in a reasonable computational time.
The objective of this work is the development of an exact optimization procedure for the MELP model to tackle large scale instances of the problem. Based on a mathematical reformulation derived for MELP model, a Branch-and-Price algorithm has been developed. The proposed algorithm deals with some relevant points in a nonstandard way, like the duals stabilization procedure and the branch rules for the enumeration tree guided by primal bounds instead of dual bounds. The proposed algorithm is applied to previously untractable large scale instances of the problem.
Arquivo