Estudo do problema do conjunto fechado de peso máximo: aspectos matemáticos, algoritmos e aplicações

CAPESEm diversas situações, faz-se necessário selecionar um subconjunto de itens de uma ampla coleção, mantendo-se a relação que existe entre alguns dos itens, de tal forma que se um item for selecionado, todos os seus sucessores também devem ser selecionados. A cada item é associado um peso e o objetivo é selecionar o conjunto que maximiza a soma dos pesos dos itens selecionados. Este problema é conhecido como problema do conjunto fechado de peso máximo e apresenta diversas aplicações em áreas como gestão de produção e operações, manutenção, defesa e gerenciamento de projetos. O problema do conjunto fechado de peso máximo se assemelha ao problema da mochila, um conhecido problema NP-completo. No entanto, o problema do conjunto fechado de peso máximo pode ser resolvido através de algoritmos polinomiais. Este trabalho é um estudo de revisão bibliográfica acerca do problema do conjunto fechado de peso máximo com foco em três aspectos: desenvolvimento matemático, algoritmos e aplicações. Em termos matemáticos, os resultados importantes são a unimodularidade total da matriz de restrições, a reducibilidade para o problema do corte mínimo e a relação com outros problemas combinatórios. Analisamos as principais características de três algoritmos para o problema do conjunto fechado de peso máximo, indicando o mais eficiente. Além disso, discutimos brevemente algumas das aplicações do problema, sobretudo em áreas de interesse da engenharia de produção. Acreditamos que este trabalho preenche uma lacuna na literatura, aprofundando o entendimento sobre o problema do conjunto fechado de peso máximo e detalhando suas características mais importantes. Com uma formulação abrangente e flexível, o problema em questão pode ser utilizado em diversas áreas da engenharia de produção. Entendemos que o conteúdo desta pesquisa é uma ferramenta necessária para uma maior utilização do problema e para a formulação de novas aplicações.In a variety of situations, one must select a subset of items from a vast collection, preserving the relationship that may exist among some of these items, in such a way that if an item is selected all of its successors must be chosen as well. To each item is associated a weight and the goal is to select the subset that maximizes the weights’ sum of the items selected. This problem is known as the maximum weight closure problem and it has several applications in such areas as production and operations management, maintenance, defense, and project management. The maximum weight closure problem is similar, in a sense, to the knapsack problem, a known NP-complete problem. However, the maximum weight closure problem can be reduced to a minimum cut problem in a special graph and then it can be solved by polynomial algorithms.This work is a bibliographical review study about the maximum weight closure problem focusing in three aspects: mathematical development, algorithms, and applications. In mathematical terms, the important results are the total unimodularity of the constraints matrix, the reducibility to the minimum cut problem, and the relationship with other combinatorial problems. We analysed the main features of three algorithms for the maximum weight closure problem pointing out the most efficient one. Furthermore, we briefly discuss some applications of the problem, specially in industrial engineering related fields. We believe that this work fills a gap in the literature, deepening the understanding about the maximum weight closure problem and detailing its most important features. With a broad and flexible formulation, this problem can be applied to various industrial engineering domains. It is our understanding that the content of this research constitutes a necessary tool for a broader utilization of the maximum weight closure problem and for formulation of new applications