RESOLVENDO O PROBLEMA DA MOCHILA CÚBICA COM MÉTODOS CLÁSSICOS E TECNOLOGIAS QUÂNTICAS
Thiago Alves de Queiroz, Manuel Iori, Alberto Locatelli +1 more
XLV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUÇÃO "Produção inteligente para um futuro renovável" Natal, Rio Grande do Norte, 14 a 17 de outubro de 2025. 1 1.Introdução A computação quântica está se tornando uma realidade palpável em comparação com o paradigma de computação clássico.Os recentes avanços em termos de hardware e software para esse novo paradigma de computação têm permitido cientistas realizarem suas pesquisas com o uso de tecnologia quântica.Dentro da pesquisa operacional, atenção tem sido dada aos problemas de otimização combinatória e, recentemente, aos algoritmos de otimização quânticos ou inspirados na computação quântica.Vários desses algoritmos estão sendo definidos para resolver problemas de otimização combinatória de forma mais eficiente se comparados aos algoritmos clássicos (ALBASH; LIDAR, 2018).Dentre os avanços na computação quântica, pode-se citar o recozimento quântico (quantum annealer -QA).Ele é uma tecnologia projetada para lidar com problemas de otimização.A ideia é encontrar o estado de menor energia do sistema, o que corresponde a uma solução ótima do problema.Um exemplo de QA é o sistema D-Wave Advantage, que possui mais de 5 mil bits quânticos (qubits) e tem um resolvedor que pode lidar com problemas de até 2 milhões de variáveis e 100 mil restrições (BOIXO et al., 2014).Por outro lado, um ponto fraco de QAs está no número de conexões entre os qubits e os ruídos que surgem da comunicação entre eles, o que na prática limita a sua aplicação na resolução de problemas reais (DU et al., 2025).Uma outra tecnologia é o recozimento digital (digital annealer -DA), que foi proposto pela Fujitsu Ltd e é inspirado em tecnologia quântica.Ele não se trata de um computador quântico, mas de um hardware dedicado construído com a convencional tecnologia CMOS (Complementary Metal-Oxide-Semiconductor), o que permite seu funcionamento em temperatura ambiente.Para encontrar soluções de problemas de otimização, ele executa um algoritmo similar a metaheurística recozimento simulado (simulated annealing) que, por sua vez, é baseada na analogia do recozimento térmico de sólidos para a obtenção de estados de baixa energia.Uma vantagem do DA em comparação a um QA é a sua performance, com capacidade para lidar com problemas grandes e reais (FUKUSHIMA-KIMURA et al., 2023).Neste artigo, o DA é aplicado para resolver o problema da mochila cúbica (PMC).O PMC é um problema de otimização combinatória não-linear e que pertence a classe NP-Difícil.Ele possui aplicação, por exemplo, em problemas da área logística, na satisfatibilidade de fórmulas booleanas, em leilões combinatórios e na seleção de portfólio (FORRESTER; WADDELL, 2022).O objetivo desta pesquisa é avaliar o desempenho do DA sobre uma modelagem baseada na otimização binária irrestrita de ordem superior (higher-order unconstrained binary optimization -HUBO).Para isso, experimentos computacionais são realizados com exemplares XLV ENCONTRO NACIONAL DE ENGENHARIA DE PRODUÇÃO "Produção inteligente para um futuro renovável" Natal, Rio Grande do Norte, 14 a 17 de outubro de 2025. 2 de teste variando entre 40 e 100 itens e considerando diferentes densidades de coeficientes não nulos para a função objetivo do PMC.As soluções encontradas pelo DA são comparadas com aquelas obtidas por uma heurística gulosa e um modelo de programação linear inteira publicados recentemente na literatura especializada.Vale destacar que alguns desses resultados foram publicados em Queiroz et al. (2025).O presente artigo está organizado da seguinte forma.A Seção 2 contém o referencial teórico, com uma breve revisão da literatura sobre o problema da mochila e do uso do DA para resolver problemas de otimização.A Seção 3 apresenta a metodologia de pesquisa, incluindo a definição formal do PMC, o modelo cúbico a ser resolvido pelo DA, a heurística gulosa e o modelo de programação linear inteira.A Seção 4 discute os resultados computacionais, com uma tabela comparativa e análises referentes a performance de cada método de solução sobre os exemplares de teste.A Seção 5 traz as considerações finais. Referencial TeóricoEsta pesquisa contempla um problema de otimização combinatória, dentro da pesquisa operacional.Problemas de otimização combinatória possuem domínio finito, porém muito grande.O interesse está em soluções que maximizam uma certa função objetivo sujeita a diferentes restrições do problema sendo tratado (ARENALES et al., 2007).Para o modelo de computação clássica, esses problemas são computacionalmente difíceis, ou seja, estão na classe NP-Difícil.Isso significa que, até o presente momento, não se conhece algoritmos exatos de tempo polinomial para resolvê-los na otimalidade (GAREY; JOHNSON, 1979). Problema da mochilaProblemas empacotamento, como é o caso do problema da mochila, vêm sendo investigados há muito tempo por pesquisadores da área de pesquisa operacional (IORI et al., 2021).Dada a grande variedade desses problemas, existem características que permitem classificá-los.A tipologia mais recente foi proposta por Wäscher, Haussner e Schumann (2007).Ela parte de uma classificação anterior da literatura, introduzindo novas caraterísticas, sendo mais precisa e cobrindo um maior número de problemas.O problema da mochila possui um modelo matemático simples e aplicações em diversas áreas, além de aparecer como subproblema de outros problemas de otimização combinatória.A sua versão clássica é definida sobre um dado recipiente de capacidade de peso limitada e um conjunto de itens com valor e peso.O objetivo é escolher um subconjunto de itens de máximo valor cujo peso total respeite a capacidade de peso do recipiente.
Anais ... Encontro Nacional de Engenharia de Produção/Anais do Encontro Nacional de Engenharia de Produção•Nov 4, 2025•0 citations