O Algoritmo do Volume: Convergência e Resolução do Problema de Steiner em Grafos
Autores
|
1920 |
330,44
|
|
|
1921 |
330,44
|
Informações:
Publicações do PESC
Este trabalho é dividido em duas partes. Na Parte I propõe-se uma versão revisada do algoritmo do volume (V A) para programação linear, e apresenta-se uma prova de sua convergência. Originalmente, VA foi apresentado como um método de subgradientes para a resolução do problema dual, produzindo passos verdes/amarelos/vermelhos similares aos passos sérios/nulos dos métodos de feixes. Neste trabalho mostra-se que VA é na realidade um método de extragradientes. Junto com isso apresenta-se um novo padrão algorítmico baseado em extragradientes para a resolução de problemas de otimização não-suaves. A versão revisada do algoritmo do volume (RVA) apresentada neste trabalho introduz uma medida precisa é a melhora mínima requerida na função dual para a declaração de um passo sério; esse é o ponto chave da prova de convergência.
Na Parte 11, propõe-se dois novos algoritmos para a resolução do problema de Steiner em grafos (SPG), baseados em VA e RVA. A relaxação contínua de uma formulação multifluxos do SPG é considerada, e então resolvida num contexto de relaxação Lagrangeana.
Os algoritmos propostos não só produzem boas soluções duais como também estimam soluções primais da relaxação contínua do SPG que podem violar as restrições em no máximo 0.1%. Além disso, são propostas novas heurísticas primais baseadas nestas soluções primais estimadas. A boa qualidade dos limites inferiores e superiores obtidos permitiu resolver de maneira provadamente ótima muitas instâncias difíceis da literatura, sem pré-processamento e sem recorrer a nenhum método enumerativo. Além disso, os saltos de dualidade obtidos em instâncias para as quais não foi possível provar otimalidade foram bastante pequenos. Finalmente, reportam-se resultados computacionais para um grande número de problemas da literatura, incluídos aqueles contidos na biblioteca SteinLib.
This work is divided in two parts. In Part I a revised version of the volume algorithm (VA) for linear programming is proposed, and a proof of convergence is presented. Originally, VA was presented as a subgradient-like method for solving the dual, producing green/yellow /red steps similar to the serious/null steps of bundle methods. In this work it is shown that VA is in fact an extragradient method. Together with this it is presented a new algorithmic pattern based on extragradients for solving nonsmooth optimization problems. The revised volume algorithm (RVA) presented in this work introduces a precise measure of the minimum improvement required on the dual function to declare a serious step; this is the key point in the proof of convergence. In Part II, two new algorithms for solving the Steiner Thee Problem in Graphs (SPG) are proposed, based on VA and RVA. The continuous relaxation of a multicommodity flow formulation of the SPG is considered and then solved in a context of Lagrangian relaxation. The proposed algorithms not only produce good dual solutions but also estimate primal solutions of the continuous relaxation of the SPG that might violate the constraints by at most 0.1 %. Additionally, new primal heuristics based on those estimated primal solutions are also proposed. The good quality of the lower and upper bounds obtained made possible solving many difficult instances from the literature to proven optimality without preprocessing and without resorting to branching. Futhermore, the gaps obtained in instances for wich optimality could not be proven, have been fairly small. Finally, computational resulta are reported for a number of problems drown from the literature, including the ones contained in the SteinLib library.