1 |
[en] MODELS AND ALGORITHMS FOR THE GENERALIZED ASSIGNMENT PROBLEM (PAG) AND APPLICATIONS / [pt] MODELOS E ALGORITMOS PARA O PROBLEMA DE ALOCAÇÃO GENERALIZADA (PAG) E APLICAÇÕESALEXANDRE ALTOE PIGATTI 17 November 2003 (has links)
[pt] Esta dissertação estuda modelos e algoritmos para o
Problema de Alocação Generalizada (PAG) . A motivação para
este estudo foi uma nova aplicação do PAG: o Problema de
Carregamento de Caminhões (PCC) . A pesquisa desenvolvida
concentra-se no estudo e na proposta de algoritmos
aproximados (metaeurísticas) e exatos para a resolução do
PAG. Os algoritmos aproximados propostos baseiam-se em um
conceito recentemente criado por Fischetti e Lodi (2003),
que utiliza programação matemática inteira para a
exploração eficiente de vizinhanças mais abrangentes. Os
resultados obtidos foram comparáveis aos melhores
conhecidos, com a vantagem de exigir um esforço pequeno de
implementação e um menor tempo de processamento. O
algoritmo exato proposto é um algoritmo de branch-and-cut-
and-price, que tem como ponto de partida o algoritmo
de branch-and-price de Savelsbergh (1997). Técnicas de
estabilização da geração de colunas similares às propostas
por Du Merle, Villeneuve, Desrosiers e Hansen (1999), foram
estudadas no âmbito desta dissertação, que experimenta
com diferentes implementações deste mecanismo. O algoritmo
de branch-andcut-and-price estabilizado demonstrou sua
eficiência ao resolver à otimalidade instâncias que se
encontravam em aberto na literatura. Finalmente,
experiências com PCC permitiram que os códigos
desenvolvidos pudessem ser avaliados em problemas reais. / [en] This dissertation tackles the Generalized Assignment
Problem (PAG), models and algorithms are studied and
proposed. This work was motivated by a real world
application: the Truck Loading Problem (PCC). Research was
done on approximated (metaheuristics) and exact algorithm
for solving the PAG. The approximated algorithms proposed
were based on a recent idea from Fischetti and Lodi (2003).
It uses integer programming to explore wider neighborhoods.
The results were compared to the best known, while
demanding much less implementation effort and using less
cpu time. The exact algorithm proposed is a branch-and-cut-
and-price developed from the branch-and-price algorithm of
Savelsbergh (1997). We used stabilized column generation
techniques similar to the one by Du Merle, Villeneuve,
Desrosiers and Hansen (1999), and devised experiments with
different implementations of this mechanism. The resulting
algorithm proved its efficiency by solving to optimality
open instances from the literature. Finally, experiments
with the PCC turned possible the evaluation of the codes
developed on real problems.
|
2 |
[pt] ALGORITMO PRICE-AND-CUT COM 3-SRCS E ENUMERAÇÃO DE COLUNAS PARA O PROBLEMA DE ALOCAÇÃO GENERALIZADA / [en] PRICE-AND-CUT ALGORITHM WITH 3-SRCS CUTS AND COLUMN ENUMERATION FOR THE GENERALIZED ASSIGNMENT PROBLEMRAFAEL AZEVEDO MOSCOSO SILVA CRUZ 15 June 2021 (has links)
[pt] Esta dissertação estuda formulações, algoritmos e métodos exatos para resolver instâncias do Problema de Alocação Generalizada (PAG) com uma separação de desigualdades (3, 0.5)-SRC que viabilize a enumeração de colunas. Este trabalho é motivado pela perspectiva de alcançar o estado-da-arte com
resultados competitivos comparáveis às melhores soluções encontradas na literatura por Avella (2010) e Michelon (2012). A pesquisa abrange métodos exatos e heurísticas, com ênfase no estudo que aborda a decomposição de Dantzig-Wolfe, o algoritmo de geração de colunas, a estabilização de colunas
por meio da ponderação de duais proposto por Wentges (1997) e a enumeração de colunas habilitada pela minimização do gap decorrente do algoritmo de price-and-cut. O algoritmo de price-and-cut desenvolvido recorre à geração de colunas (pricing) aliada à separação de (3, 0.5)-SRCs para aumentar o lower bound gerado, assim minimizando o gap. A geração de colunas implementada é inspirada no algoritmo de Savelsbergh (1997); e a separação de (3, 0.5)-SRCs é motivada pelo trabalho de Jepsen (2008) e pelo algoritmo branch-cut-andprice proposto por Poggi e Uchoa (2016) para o CVRP. De acordo com os
experimentos computacionais, as desigualdades adotadas são capazes de reduzir o gap suficientemente para viabilizar a enumeração de colunas em diversas instâncias do PAG com até 200 tarefas e 20 máquinas. O método utilizado obteve resultados compatíveis às melhores soluções conhecidas, enumerando todas as colunas necessárias para cobrir o gap determinado pelo price-and-cut. Esse
resultado incentiva futuras pesquisas para estender a aplicação do algoritmo a instâncias maiores e mais difíceis. / [en] This dissertation deals with formulations, algorithms and exact methods for solving the well-known Generalized Assignment Problem (GAP) through a price-and-cut approach with the separation of (3, 0.5)-SRC inequalities in order to improve column enumeration feasibility and efficiency. This work is
motivated by the perspective of reaching state-of-the-art performance, attaining competitive results which are comparable with the best known solutions found in the literature by Avella (2010) and Michelon (2012). This research was build on exact methods and some heuristics with emphasis on the Dantzig-
Wolfe decomposition, the column generation algorithm, the stabilization through weighted Dantzig-Wolfe decomposition proposed byWentges (1997) and finally the column enumeration motivated by the gap minimization reached through the price-and-cut algorithm. The price-and-cut algorithm proposed here resort to column generation (pricing) combined with the separation of (3, 0.5)-SRC cuts in order to increase the generated lower bound, thus minimizing the attained gap. This column generation algorithm follows the work of Savelsbergh (1997); and the separation of (3, 0.5)-SRCs is formulated by Jepsen (2008) and motivated by the branch-cut-and-price algorithm proposed by Poggi and Uchoa (2016) for the CVRP. According to computational experiments, the adopted inequalities are capable of sufficiently reducing the gap, assuring the feasibility of column enumeration for several GAP instances with up to 200 tasks and 20 machines. This method achieved expressive results, compatible with the best known solutions, enumerating all the necessary columns to cover the gap found by the price-and-cut. Therefore, these results motivate future research towards the extension of the method s applicability to larger and more complex instances.
|
Page generated in 0.0486 seconds