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

Extensão de limites elipsoidais em programação quadrática inteira

Pinillos Nieto, Ismael Francisco

Published Mar 1, 2017• 0 citations
OpenAlex

Abstract

Limites elipsoidais para problemas de programacao inteira estritamente convexa foram propostos em [1, 2]. A ideia e subestimar a funcao objetivo quadratica q do problema por outra funcao quadratica convexa com o mesmo minimizador continuo da funcao q e para a qual um minimizador inteiro pode ser facilmente calculado. Propomos nesta tese uma maneira diferente de construir o subestimador quadratico para o mesmo problema e entao estender a ideia a outros problemas inteiros quadraticos, onde a funcao objetivo e convexa (nao necessariamente estritamente convexa), e onde a funcao objetivo e nao convexa com a introducao de restricoes de caixa. A qualidade dos limites propostos e avaliada experimentalmente e comparada com as metodologias relacionadas.

Related papers

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

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

A new quadratic relaxation for binary variables with applications to the reliability of electrical distribution networks, segmentation of nerve root images, and distance geometry problems

Petra Maria Bartmeyer

Resumo: Como o título sugere, o foco desta pesquisa é o desenvolvimento de uma nova relaxação quadrática para problemas binários, sua formalização em resultados teóricos, e a aplicação dos novos conceitos em aplicações à confiabilidade de redes de energia elétrica, à segmentação de imagens médicas de nervos e à problemas de geometria de distâncias. Modelos matemáticos contendo va-riáveis de decisões binárias podem ser usados para encontrar as melhores soluções em processos de tomada de decisões, normalmente caracterizando problemas de otimização combinatória difíceis. A solução desses problemas em aplicações de interesse prático requer um grande esforço computacional; por isso, ao longo dos últimos anos, têm sido objeto de pesquisas na área de metaheurísticas. As ideias aqui desenvolvidas abrem novas perspectivas para a abordagem desses problemas apoiando-se em métodos de otimização não-lineares, área que vem sendo povoada por "solvers" muito eficientes. Inicialmente, explorando aspectos formais, a relaxação desenvolvida é parti-cularizada para um problema de otimização quadrática binária irrestrita. O relaxamento permite o desenvolvimento de três estruturas para abordar esta classe de problemas, e explora a convexidade da função objetivo para obter melhorias computacionais. Estudos de casos compararam o relaxamento proposto com os relaxamentos similares apresentados na literatura. Foram desenvolvidas três aplicações para os desenvolvimentos teóricos da pesquisa. A primeira aplicação envolve a melhoria da confiabilidade de redes de energia elétrica. Especificamente, aborda o problema de definir a melhor alternativa para a alocação de sensores na rede, o que permite reduzir os efeitos de ocorrências indesejáveis e ampliar a resiliência das redes. A segunda aplicação envolve o problema de segmentação de imagens médicas associadas a estruturas de nervos. A abordagem proposta interpreta o problema de segmentação como um problema de otimização binária, onde medir cada axônio significa encontrar um ciclo Hamiltoniano, um caso do problema do caixeiro viajante; a solução desses problemas fornece a estatística descritiva para um conjunto de axônios, incluindo o número (de axônios), os diâmetros e as áreas ocupadas. A última aplicação elabora um modelo matemático para o problema de geometria de distâncias sem designação, área ainda pouco estudada e com muitos aspectos em aberto. A relaxação desenvolvida na pesquisa permitiu resolver instâncias com mais de vinte mil variáveis binárias. Esses resultados são bons indicadores dos benefícios alcançáveis com os aspectos teóricos da pesquisa, e abrem novas perspectivas para as aplicações, que incluem inovações em nanotecnologia e bioengenharia

•Apr 27, 2020•0 citations

AN IMPROVED EXACT METHOD FOR THE UBQP

Daniel Fleischman

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.

•Aug 4, 2010•1 citation

Otimização em computadores quânticos: formulação QUBO para o problema CMO

Nicolas M. de Oliveira

A computação quântica é um paradigma computacional que tem motivado o aparecimento de diversas pesquisas que visam apresentar soluções para problemas, atualmente, considerados difíceis. O surgimento de algoritmos quânticos que operam mais rápido que seus análogos clássicos tem feito com que corporações como Google, NASA e IBM invistam nesse paradigma. Por isso, intensificou-se a busca por formulações alternativas para problemas, visando resolvê-los em um ambiente computacional quântico. Entre essas formulações, estão os trabalhos que abordam a resolução de problemas na computação quântica a partir de formulações QUBO (Quadratic Unconstrained Binary Optimization), um problema NP-difícil cujo princípio consiste em minimizar uma função quadrática. O formato QUBO é comumente utilizado na literatura quando da solução quântica de problemas de otimização e diversos autores têm recorrido à esta caracterização devido à sua aplicabilidade em uma considerável gama de problemas. Dessa forma, representar um dado problema como um problema QUBO implica diretamente que podemos executá-lo em um ambiente computacional quântico (genérico ou de propósito específico). O problema CMO (Contact Map Overlap) é definido como um problema de otimização combinatória NPdifícil que consiste na medida de semelhança entre pares de proteínas com base em seus respectivos mapas de contato. Em bioinformática, o estudo de problemas que buscam por funções similares entre estruturas biológicas, especialmente de proteínas, é um campo de grande interesse. Com isso, este trabalho de pesquisa aborda o problema CMO na conjectura da resolução dos problemas de otimização em computadores quânticos através da formulação QUBO dos mesmos. Além de fornecermos uma formulação QUBO para o problema de proteína CMO, resultados experimentais foram obtidos com o auxílio da ferramenta qbsolv e validaram esta abordagem como uma alternativa aos métodos clássicos existentes.

•Feb 22, 2018•0 citations

Tutoriel : Reformulation Quadratique Convexe pour l'optimisation Quadratique discrète : résultats de base et extensions récentes

Sourour Elloumi

Nous considérons le problème (QP) de la minimisation d'une fonction quadratique sous des contraintes linéaires ou quadratiques. Les variables sont entières et bornées. Ce problème très général permet de modéliser de nombreux problèmes classiques en Optimisation Combinatoire et constitue une première généralisation de la programmation linéaire en nombres entiers. Une différence majeure entre (QP) et les programmes linéaires en nombres entiers réside dans le fait que, en général, sa relaxation continue fournit un problème lui aussi NP-difficile. Pour contourner cette difficulté, la reformulation quadratique convexe transforme (QP) en un problème (QP') équivalent mais dont la relaxation continue est un problème convexe. Afin de calculer une solution optimale de (QP), on peut alors résoudre (QP') par un algorithme d'énumération implicite basé sur l'optimisation continue convexe. Nous faisons un tour d'horizon de développements récents de cette approche. Nous montrons en particulier comment les relaxations semi-définies positives permettent de construire les problèmes équivalents (QP') les plus intéressants. Dans le cas des variables binaires, nous donnons une vision des linéarisations classiques comme un cas particulier de reformulation quadratique convexe. Enfin, nous illustrons la généralité et l'efficacité expérimentale de la résolution exacte par reformulation quadratique convexe sur différents problèmes d'Optimisation Combinatoire. Références A. Billionnet et S. Elloumi. Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem . Mathematical Programming, 109(1): 55-68, 2007. A. Billionnet, S. Elloumi et M.-C. Plateau. Improving standard solvers convex reformulation for constrained quadratic 0-1 programs: the QCR method. Discrete Applied Math, vol. 157(6), 2009, pp. 1185-1197. A. Billionnet, S. Elloumi et A. Lambert. Extending the QCR method to general mixed-integer programs. Mathematical Programming, vol. 131(1), 2012, pp.381-401

•Feb 26, 2014•0 citations
Limites elipsoidais para problemas de programacao inteira estritamente convexa foram propostos em [1, 2]. A ideia e subestimar a funcao objetivo quadratica q do problema por outra funcao quadratica convexa com o mesmo minimizador continuo da funcao q e para a qual um minimizador inteiro pode ser facilmente calculado. Propomos nesta tese uma maneira diferente de construir o subestimador quadratico para o mesmo problema e entao estender a ideia a outros problemas inteiros quadraticos, onde a funcao objetivo e convexa (nao necessariamente estritamente convexa), e onde a funcao objetivo e nao convexa com a introducao de restricoes de caixa. A qualidade dos limites propostos e avaliada experimentalmente e comparada com as metodologias relacionadas.
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.
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.
Resumo: Como o título sugere, o foco desta pesquisa é o desenvolvimento de uma nova relaxação quadrática para problemas binários, sua formalização em resultados teóricos, e a aplicação dos novos conceitos em aplicações à confiabilidade de redes de energia elétrica, à segmentação de imagens médicas de nervos e à problemas de geometria de distâncias. Modelos matemáticos contendo va-riáveis de decisões binárias podem ser usados para encontrar as melhores soluções em processos de tomada de decisões, normalmente caracterizando problemas de otimização combinatória difíceis. A solução desses problemas em aplicações de interesse prático requer um grande esforço computacional; por isso, ao longo dos últimos anos, têm sido objeto de pesquisas na área de metaheurísticas. As ideias aqui desenvolvidas abrem novas perspectivas para a abordagem desses problemas apoiando-se em métodos de otimização não-lineares, área que vem sendo povoada por "solvers" muito eficientes. Inicialmente, explorando aspectos formais, a relaxação desenvolvida é parti-cularizada para um problema de otimização quadrática binária irrestrita. O relaxamento permite o desenvolvimento de três estruturas para abordar esta classe de problemas, e explora a convexidade da função objetivo para obter melhorias computacionais. Estudos de casos compararam o relaxamento proposto com os relaxamentos similares apresentados na literatura. Foram desenvolvidas três aplicações para os desenvolvimentos teóricos da pesquisa. A primeira aplicação envolve a melhoria da confiabilidade de redes de energia elétrica. Especificamente, aborda o problema de definir a melhor alternativa para a alocação de sensores na rede, o que permite reduzir os efeitos de ocorrências indesejáveis e ampliar a resiliência das redes. A segunda aplicação envolve o problema de segmentação de imagens médicas associadas a estruturas de nervos. A abordagem proposta interpreta o problema de segmentação como um problema de otimização binária, onde medir cada axônio significa encontrar um ciclo Hamiltoniano, um caso do problema do caixeiro viajante; a solução desses problemas fornece a estatística descritiva para um conjunto de axônios, incluindo o número (de axônios), os diâmetros e as áreas ocupadas. A última aplicação elabora um modelo matemático para o problema de geometria de distâncias sem designação, área ainda pouco estudada e com muitos aspectos em aberto. A relaxação desenvolvida na pesquisa permitiu resolver instâncias com mais de vinte mil variáveis binárias. Esses resultados são bons indicadores dos benefícios alcançáveis com os aspectos teóricos da pesquisa, e abrem novas perspectivas para as aplicações, que incluem inovações em nanotecnologia e bioengenharia
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.
A computação quântica é um paradigma computacional que tem motivado o aparecimento de diversas pesquisas que visam apresentar soluções para problemas, atualmente, considerados difíceis. O surgimento de algoritmos quânticos que operam mais rápido que seus análogos clássicos tem feito com que corporações como Google, NASA e IBM invistam nesse paradigma. Por isso, intensificou-se a busca por formulações alternativas para problemas, visando resolvê-los em um ambiente computacional quântico. Entre essas formulações, estão os trabalhos que abordam a resolução de problemas na computação quântica a partir de formulações QUBO (Quadratic Unconstrained Binary Optimization), um problema NP-difícil cujo princípio consiste em minimizar uma função quadrática. O formato QUBO é comumente utilizado na literatura quando da solução quântica de problemas de otimização e diversos autores têm recorrido à esta caracterização devido à sua aplicabilidade em uma considerável gama de problemas. Dessa forma, representar um dado problema como um problema QUBO implica diretamente que podemos executá-lo em um ambiente computacional quântico (genérico ou de propósito específico). O problema CMO (Contact Map Overlap) é definido como um problema de otimização combinatória NPdifícil que consiste na medida de semelhança entre pares de proteínas com base em seus respectivos mapas de contato. Em bioinformática, o estudo de problemas que buscam por funções similares entre estruturas biológicas, especialmente de proteínas, é um campo de grande interesse. Com isso, este trabalho de pesquisa aborda o problema CMO na conjectura da resolução dos problemas de otimização em computadores quânticos através da formulação QUBO dos mesmos. Além de fornecermos uma formulação QUBO para o problema de proteína CMO, resultados experimentais foram obtidos com o auxílio da ferramenta qbsolv e validaram esta abordagem como uma alternativa aos métodos clássicos existentes.
Nous considérons le problème (QP) de la minimisation d'une fonction quadratique sous des contraintes linéaires ou quadratiques. Les variables sont entières et bornées. Ce problème très général permet de modéliser de nombreux problèmes classiques en Optimisation Combinatoire et constitue une première généralisation de la programmation linéaire en nombres entiers. Une différence majeure entre (QP) et les programmes linéaires en nombres entiers réside dans le fait que, en général, sa relaxation continue fournit un problème lui aussi NP-difficile. Pour contourner cette difficulté, la reformulation quadratique convexe transforme (QP) en un problème (QP') équivalent mais dont la relaxation continue est un problème convexe. Afin de calculer une solution optimale de (QP), on peut alors résoudre (QP') par un algorithme d'énumération implicite basé sur l'optimisation continue convexe. Nous faisons un tour d'horizon de développements récents de cette approche. Nous montrons en particulier comment les relaxations semi-définies positives permettent de construire les problèmes équivalents (QP') les plus intéressants. Dans le cas des variables binaires, nous donnons une vision des linéarisations classiques comme un cas particulier de reformulation quadratique convexe. Enfin, nous illustrons la généralité et l'efficacité expérimentale de la résolution exacte par reformulation quadratique convexe sur différents problèmes d'Optimisation Combinatoire. Références A. Billionnet et S. Elloumi. Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem . Mathematical Programming, 109(1): 55-68, 2007. A. Billionnet, S. Elloumi et M.-C. Plateau. Improving standard solvers convex reformulation for constrained quadratic 0-1 programs: the QCR method. Discrete Applied Math, vol. 157(6), 2009, pp. 1185-1197. A. Billionnet, S. Elloumi et A. Lambert. Extending the QCR method to general mixed-integer programs. Mathematical Programming, vol. 131(1), 2012, pp.381-401