[pt] BUSCA PARAMÉTRICA PARA VARIANTES DO PROBLEMA DE ALOCAÇÃO DE RECURSO ANINHADO - JOAO PEDRO TEIXEIRA BRANDAO (2021)
[pt] Os problemas de alocação de recurso procuram encontrar uma repartição ideal de recursos a um número fixo de áreas. Nesta dissertação, consideramos um problema de alocação de recurso com uma função objetiva linear e dois conjuntos distintos de restrições: um conjunto de restrições aninhados, onde as somas parciais das variáveis de decisão são limitadas por cima e uma restrição linear que define um hiperplano. Propomos um algoritmo fracamente e um fortemente polinomial. O algoritmo fracamente polinomial requer algumas suposições sobre os dados e possui complexidade de O(n log n log |Λ|/|I|), onde n é o número de variáveis, Λ é um intervalo no espaço dual, e |I| está relacionado com a precisão dos dados. O algoritmo fortemente polinomial é baseado na técnica de busca paramétrica de Megiddo e obtém uma complexidade O(n log n). As complexidades obtidas são superiores à complexidade do método genérico de Pontos Interiores, O(n 3/ log n). Além disso, uma análise experimental foi realizada e os algoritmos mostraram-se mais eficientes e produziram soluções ótimas para instâncias de problemas com até 1.000.000 variáveis.