Método de Enumeração Implícita Empregado na Resolução de Problemas de Decomposição
Autores
|
2018 |
44,860
|
|
|
2019 |
44,860
|
Informações:
Publicações do PESC
Neste trabalho. consideramos um problema mestre de Benders, onde a grande dificuldade reside no fato de que todas as soluções são viáveis. Caso fôssemos calcular todas as soluções, teríamos uma nova situação, que é a inviabilidade de tempo, principalmente para problemas com um número elevado de variáveis. Desta forma, aplicamos o método de enumeração implícita, o qual obtém a solução ótima sem que todas elas tenham que ser calculadas. Para isto, devemos associar uma variável a um nó, onde uma alternativa é utilizar alguns critérios para tal associação, chamados de heurísticas. Com base nos resultados fornecidos por estas heurísticas, considerando inclusive o número de nós avaliados e o tempo de cálculo até se obter a solução ótima, podemos ter conhecimento sobre qual delas teve um melhor desempenho em uma determinada situação que lhe foi apresentada, de acordo com o número de variáveis, o número de expressões, a porcentagem de negativos e o valor máximo que um coeficiente pode assumir.
In this work, we considered a Benders' master problem, where the great difficulty is the fact of all solutions are feasible. If we wanted to compute all the solutions, we'd have a new situation, that is the infeasibility of time, mainly to problems with a high number of variables. Then, we applied the implicit enumeration method, that gets the best solution without the computation of all of them. For this, we must associate a variable to a node, where a alternative is to use some criterion for this association, called heuristics. Based on the results given by these heuristics, considering also the number of avaliated nodes and the computation time until getting the best solution, we can have knowledge about which of them had the best performance in a specific situation that was presented, according to the number of variables, the number of expressions, the porcentage of negatives and the maximum value that a coefficient can assume.