Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

AN IMPROVED EXACT METHOD FOR THE UBQP

Daniel Fleischman

Published Aug 4, 2010• 1 citation
Publisher

Abstract

A Programação Quadrática Binária Irrestrita (UBQP) é amplamente\nestudada. Trata-se de uma ferramenta de modelagem poderosa, mas\notimizar de um problema NP-difícil. Neste trabalho uma nova abordagem\né apresentada, que pode ser usada para construir um algoritmo exato.\nAlém disso, a ideia básica que fundamenta o trabalho pode ser usado em\num espectro ainda mais amplo de problemas. O algoritmo exato derivado\ndo novo método é altamente paralelizável, o que é uma característica\ndesejável nos dias de hoje em que cloud computing já é uma realidade. Para\ninstâncias razoavelmente grandes do UBQP, o novo método pode paralelizar\na centenas, ou até milhares, de núcleos com facilidade, com um aumento\nde desempenho quase linear.

DOI
10.17771/pucrio.acad.17054

Related papers

Avaliação Rápida em Problemas de Otimização Binária

Eduardo A.J. Anacleto, Cláudio N. Meneses

Neste trabalho, apresentamos um resultado original que possibilita acelerar o processo de resolucao do problema de Programacao Quadratica Binaria Irrestrita. A partir desse resultado, desenvolvemos um algoritmo e realizamos experimentos computacionais com instâncias disponiveis na literatura do problema.

Proceeding Series of the Brazilian Society of Computational and Applied Mathematics•Feb 14, 2018•0 citations

Algorithms for solving pseudo-boolean optimization problems

Eduardo A.J. Anacleto

Investigamos os problemas de Otimização Pseudo-Booleana (PBO), Otimização Quadrática Binária Irrestrita (QUBO) e Programação Quadrática Booleana com Restrições de Limitantes Superiores Generalizados (BQP-GUB). Estes problemas pertencem 'a classe de complexidade computacional NP-difícil e têm sido estudados desde os anos 60. A busca por m'métodos para resolver esses problemas constitui um campo de pesquisa ativo, devido a situações reais que podem ser modeladas por meio deles. Em virtude de apelos práticos, pesquisadores têm mostrado grande interesse no desenvolvimento desses métodos. Com o intuito de contribuir de maneira significativa para esta área de pesquisa: (a) propomos um algoritmo exato para resolver os problemas PBO e QUBO; (b) projetamos um algoritmo de tempo polinomial para resolver classes de instâncias dos problemas PBO e QUBO; (c) desenvolvemos fórmulas para gerar limitantes para os valores de soluções ótimas para o problema QUBO; (d) criamos fórmulas para calcular rapidamente o valor da função objetivo do BQP-GUB; e (e) reformulamos problemas de otimização combinatória para a forma dos problemas QUBO e BQP-GUB.

•Jun 21, 2023•0 citations

Programmation quadratique en variables binaires

Brossard, Nicolas

•Jan 1, 1995•0 citations

Decomposições Lagrangeanas para o problema de programação quadrática binária irrestrita

Geraldo Regis Mauri, Luiz Antônio Nogueira Lorena

O Problema de Programação Quadrática Binária Irrestrita - PQ é um dos problemas clássicos na área de otimização não-linear cujo objetivo é otimizar uma função quadrática através da escolha de valores binários apropriados para as variáveis de decisão. Este trabalho propõe novas alternativas de decomposição Lagrangeana para obtenção de limitantes para o PQ. Os métodos propostos tratam uma versão linear inteira mista (PQL) do PQ que tem restrições representadas através de um grafo. Esse grafo é particionado em clusters de vértices formando um problema dual cuja solução é dada por um algoritmo de subgradiente. A cada iteração desse método, os subproblemas formados pelos subgrafos gerados são resolvidos pelo CPLEX. Experimentos computacionais tratam um conjunto de dados formado por diversas instâncias de difícil solução e diferentes características. Os resultados mostram a eficiência dos métodos propostos em relação a métodos tradicionais de relaxação Lagrangeana e outros métodos encontrados na literatura.

Pesquisa Operacional•Apr 1, 2009•2 citations

Uma ferramenta para projeto e simulação de circuitos quânticos.

G. E. M. Cabral, Gustavo Eulalio M. Cabral

A Computação Quântica surgiu como uma promissora tecnologia alternativa capaz de contornar os problemas previstos para acontecerem em breve com a saturação da tecnologia atual (Computação Clássica). Estes problemas acontecem quando se trabalha com componentes muito pequenos, da ordem de poucos nanômetros, quando os efeitos da Mecânica Quântica começam a tornar-se mais fortes, gerando resultados aleatórios. A Computação Quântica toma proveito desses efeitos, resultando numa Computação não somente mais rápida, como um novo tipo de Computação, capaz de realizar tipos novos de computação impossíveis, em princípio, de serem realizadas classicamente. Embora a teoria da Computação Quântica venha se desenvolvendo com rapidez, a parte experimental ainda enfrenta grandes dificuldades. Embora implementações de algoritmos simples e com poucos qubits já tenham sido realizadas, ainda há problemas sérios de escalabilidade, descoerência e controlabilidade a serem resolvidos. Devido a esses problemas, torna-se imperativo o uso de simuladores tanto para o desenvolvimento de novos algoritmos quanto para o estudo dos algoritmos existentes. A simulação, porém, apresenta um problema, no que um sistema quântico só pode ser simulado eficientemente por outro sistema quântico. Um sistema quântico de n qubits levará um tempo O(2n ) para ser simulado por um computador clássico. A simulação, entretanto, mostra-se a alternativa mais viável em vista da falta de um hardware quântico. Este trabalho apresenta o processo de concepção e implementação de um simulador universal de circuitos quânticos, denominado Zeno. O modelo de circuitos quânticos foi escolhido por ser amplamente difundido e de fácil assimilação. O trabalho apresenta uma introdução aos conceitos de Computação Quântica usados na implementação do simulador, os requisitos gerais desejáveis para um novo simulador de circuitos quânticos, tanto do ponto de vista funcional quanto do não-funcional, o processo de desenvolvimento utilizado e uma análise dos resultados obtidos com a implementação do simulador.

•Jul 21, 2004•0 citations

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
A Programação Quadrática Binária Irrestrita (UBQP) é amplamente\nestudada. Trata-se de uma ferramenta de modelagem poderosa, mas\notimizar de um problema NP-difícil. Neste trabalho uma nova abordagem\né apresentada, que pode ser usada para construir um algoritmo exato.\nAlém disso, a ideia básica que fundamenta o trabalho pode ser usado em\num espectro ainda mais amplo de problemas. O algoritmo exato derivado\ndo novo método é altamente paralelizável, o que é uma característica\ndesejável nos dias de hoje em que cloud computing já é uma realidade. Para\ninstâncias razoavelmente grandes do UBQP, o novo método pode paralelizar\na centenas, ou até milhares, de núcleos com facilidade, com um aumento\nde desempenho quase linear.
Investigamos os problemas de Otimização Pseudo-Booleana (PBO), Otimização Quadrática Binária Irrestrita (QUBO) e Programação Quadrática Booleana com Restrições de Limitantes Superiores Generalizados (BQP-GUB). Estes problemas pertencem 'a classe de complexidade computacional NP-difícil e têm sido estudados desde os anos 60. A busca por m'métodos para resolver esses problemas constitui um campo de pesquisa ativo, devido a situações reais que podem ser modeladas por meio deles. Em virtude de apelos práticos, pesquisadores têm mostrado grande interesse no desenvolvimento desses métodos. Com o intuito de contribuir de maneira significativa para esta área de pesquisa: (a) propomos um algoritmo exato para resolver os problemas PBO e QUBO; (b) projetamos um algoritmo de tempo polinomial para resolver classes de instâncias dos problemas PBO e QUBO; (c) desenvolvemos fórmulas para gerar limitantes para os valores de soluções ótimas para o problema QUBO; (d) criamos fórmulas para calcular rapidamente o valor da função objetivo do BQP-GUB; e (e) reformulamos problemas de otimização combinatória para a forma dos problemas QUBO e BQP-GUB.
O Problema de Programação Quadrática Binária Irrestrita - PQ é um dos problemas clássicos na área de otimização não-linear cujo objetivo é otimizar uma função quadrática através da escolha de valores binários apropriados para as variáveis de decisão. Este trabalho propõe novas alternativas de decomposição Lagrangeana para obtenção de limitantes para o PQ. Os métodos propostos tratam uma versão linear inteira mista (PQL) do PQ que tem restrições representadas através de um grafo. Esse grafo é particionado em clusters de vértices formando um problema dual cuja solução é dada por um algoritmo de subgradiente. A cada iteração desse método, os subproblemas formados pelos subgrafos gerados são resolvidos pelo CPLEX. Experimentos computacionais tratam um conjunto de dados formado por diversas instâncias de difícil solução e diferentes características. Os resultados mostram a eficiência dos métodos propostos em relação a métodos tradicionais de relaxação Lagrangeana e outros métodos encontrados na literatura.
A Computação Quântica surgiu como uma promissora tecnologia alternativa capaz de contornar os problemas previstos para acontecerem em breve com a saturação da tecnologia atual (Computação Clássica). Estes problemas acontecem quando se trabalha com componentes muito pequenos, da ordem de poucos nanômetros, quando os efeitos da Mecânica Quântica começam a tornar-se mais fortes, gerando resultados aleatórios. A Computação Quântica toma proveito desses efeitos, resultando numa Computação não somente mais rápida, como um novo tipo de Computação, capaz de realizar tipos novos de computação impossíveis, em princípio, de serem realizadas classicamente. Embora a teoria da Computação Quântica venha se desenvolvendo com rapidez, a parte experimental ainda enfrenta grandes dificuldades. Embora implementações de algoritmos simples e com poucos qubits já tenham sido realizadas, ainda há problemas sérios de escalabilidade, descoerência e controlabilidade a serem resolvidos. Devido a esses problemas, torna-se imperativo o uso de simuladores tanto para o desenvolvimento de novos algoritmos quanto para o estudo dos algoritmos existentes. A simulação, porém, apresenta um problema, no que um sistema quântico só pode ser simulado eficientemente por outro sistema quântico. Um sistema quântico de n qubits levará um tempo O(2n ) para ser simulado por um computador clássico. A simulação, entretanto, mostra-se a alternativa mais viável em vista da falta de um hardware quântico. Este trabalho apresenta o processo de concepção e implementação de um simulador universal de circuitos quânticos, denominado Zeno. O modelo de circuitos quânticos foi escolhido por ser amplamente difundido e de fácil assimilação. O trabalho apresenta uma introdução aos conceitos de Computação Quântica usados na implementação do simulador, os requisitos gerais desejáveis para um novo simulador de circuitos quânticos, tanto do ponto de vista funcional quanto do não-funcional, o processo de desenvolvimento utilizado e uma análise dos resultados obtidos com a implementação do simulador.
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.