Cutting-plane methodology via quantum optimization for solving the Traveling Salesman Problem

Este artigo apresenta uma metodologia iterativa que combina geração dinâmica de restrições e pré-processamento para reduzir o tamanho do modelo do Problema do Caixeiro Viajante, demonstrando através de experimentos computacionais que essa abordagem melhora o desempenho em soluções clássicas, quânticas diretas e híbridas.

O essencial

Imagine que você é um carteiro que precisa entregar cartas em várias casas de uma cidade. O seu objetivo é encontrar o caminho mais curto possível para visitar todas as casas exatamente uma vez e voltar para a sua base, sem se perder e sem repetir ruas. Esse é o famoso Problema do Caixeiro Viajante.

Parece simples, não é? Mas, à medida que a cidade cresce (mais casas), o número de caminhos possíveis explode de forma assustadora. É como tentar adivinhar qual é a combinação correta de uma fechadura com milhões de dígitos, apenas chutando.

Aqui está o que os autores desse artigo fizeram para resolver esse problema, explicado de forma bem simples:

1. O Grande Problema: O "Labirinto de Caminhos Errados"

O maior desafio para resolver esse problema não é apenas encontrar o caminho, mas garantir que você não fique preso em pequenos círculos.

• A Analogia: Imagine que você está visitando casas. De repente, você percebe que foi para a casa A, depois para a B, depois para a C e voltou para a A, sem ter visitado a casa D que fica longe. Você ficou preso num "burburinho" (um sub-tour) e esqueceu o resto da cidade.
• Para evitar isso, os computadores precisam de regras (chamadas de "restrições") que digam: "Não faça esse pequeno círculo". O problema é que, em uma cidade grande, existem bilhões de possíveis pequenos círculos. Tentar escrever todas essas regras de uma vez deixaria o computador louco e lento.

2. A Solução Clássica: O Detetive Inteligente (Método de Corte)

Os autores usaram uma estratégia inteligente chamada Geração de Cortes (Cutting-Plane).

• A Analogia: Em vez de tentar desenhar todas as regras de "não fazer círculos" antes de começar (o que seria impossível), o computador começa a traçar um caminho.
  1. Ele traça um caminho rápido.
  2. Se ele perceber que o carteiro ficou preso num pequeno círculo (ex: A -> B -> A), ele cria uma regra específica naquele momento para proibir aquele círculo específico.
  3. Ele recalcula o caminho.
  4. Repete o processo até que o carteiro consiga visitar todas as casas sem ficar preso em nenhum círculo.
• Resultado: Em vez de ter um livro de regras com milhões de páginas, o computador só escreve as regras que realmente foram necessárias. Isso torna o problema muito mais leve.

3. O "Filtro de Tráfego" (Pré-processamento)

Antes de começar a resolver, eles usaram uma técnica chamada Filtragem de Arcos baseada em Custo (CAF).

• A Analogia: Imagine que você vai dirigir de São Paulo ao Rio. Você sabe que não vai fazer sentido pegar uma estrada que vai para o Norte, longe do seu destino, só para depois voltar.
• O método deles olha para o mapa e diz: "Essas ruas aqui são tão longas e caras que é impossível que o caminho perfeito as use. Vamos ignorá-las e focar apenas nas ruas mais curtas e lógicas."
• Isso reduz drasticamente o tamanho do mapa que o computador precisa analisar.

4. A Tecnologia Quântica: O "Explorador Mágico"

Agora, a parte divertida: eles testaram isso em computadores quânticos (como os da D-Wave).

• O Desafio: Os computadores quânticos atuais são como crianças brilhantes, mas com pouca memória e que se distraem facilmente. Eles não conseguem segurar o problema inteiro (com todas as casas e regras) de uma vez.
• A Estratégia:
  • Abordagem Direta (QPU): Tentaram jogar o problema direto no computador quântico. Funcionou bem para cidades pequenas, mas quando a cidade cresceu, o computador "travou" porque o mapa era grande demais.
  • Abordagem Híbrida (O Vencedor): Aqui está a mágica. Eles usaram uma equipe mista:
    • Um computador clássico (o cérebro lógico) que divide o problema em pedaços menores.
    • O computador quântico (o explorador mágico) que testa rapidamente as melhores opções dentro desses pedaços.
    • Eles trabalham juntos: o clássico prepara o terreno, o quântico dá um "pulo" para encontrar soluções rápidas, e o clássico verifica se está tudo certo.

O Resultado Final?

A combinação de ser inteligente com as regras (só criar quando necessário) + limpar o mapa antes (ignorar ruas inúteis) + usar a força do computador quântico de forma híbrida permitiu que eles resolvessem problemas muito maiores do que era possível antes.

• Cidades pequenas: Resolvidas em frações de segundo.
• Cidades médias (até 25 casas): O computador quântico híbrido encontrou a rota perfeita (100% de sucesso).
• Cidades grandes (30 casas): Encontrou uma rota quase perfeita (99% de eficiência), algo que computadores quânticos puros não conseguiam fazer sozinhos.

Em resumo: O artigo mostra que, para usar computadores quânticos no mundo real hoje, não basta apenas jogar o problema neles. É preciso ser inteligente, simplificar o problema antes e usar uma equipe mista (clássico + quântico) para que a "mágica" quântica realmente funcione.

Resumo técnico

Resumo Técnico: Metodologia de Planos de Corte via Otimização Quântica para o Problema do Caixeiro Viajante

Autores: Alessia Ciacco, Luigi Di Puglia Pugliese, Francesca Guerriero.
Instituições: Universidade da Calábria (Itália) e Consiglio Nazionale delle Ricerche (ICAR-CNR).

1. O Problema

O Problema do Caixeiro Viajante (TSP - Traveling Salesman Problem) é um problema clássico de otimização combinatória NP-difícil, que visa encontrar o caminho mais curto que visita um conjunto de cidades exatamente uma vez e retorna à cidade de origem.

• Desafio Principal: A formulação padrão via Programação Linear Inteira (ILP) exige um número exponencial de restrições de eliminação de subtour (subtours) para garantir que a solução seja um único ciclo Hamiltoniano e não múltiplos ciclos desconexos.
• Limitação Atual: Incluir explicitamente todas essas restrições torna o modelo computacionalmente intratável mesmo para instâncias de tamanho moderado. Além disso, a aplicação de métodos quânticos atuais (como Quantum Annealing) é severamente limitada pela capacidade de qubits e pela dificuldade de codificar restrições complexas em modelos de otimização sem restrições (QUBO).

2. Metodologia Proposta

Os autores propõem um framework híbrido que combina técnicas clássicas de pesquisa operacional com otimização quântica, focando na redução da complexidade do modelo antes e durante a resolução. A abordagem baseia-se em duas estratégias complementares:

1. Abordagem de Planos de Corte (Cutting-Plane Approach - CPA):

   • Em vez de incluir todas as restrições de eliminação de subtour inicialmente, o modelo começa apenas com as restrições de grau (cada cidade visitada uma vez).
   • O problema é resolvido iterativamente. Se a solução gerada contiver subtours (ciclos desconexos), as restrições específicas para eliminar aqueles subtours são adicionadas dinamicamente ao modelo.
   • O processo repete-se até que uma solução sem subtours seja encontrada. Isso evita a explosão combinatória de restrições.

2. Pré-processamento por Filtragem de Arcos Baseada em Custo (CAF - Cost-based Arc Filtering):

   • Antes da otimização, uma fase de pré-processamento elimina arcos (conexões entre cidades) que são improváveis de pertencer a uma solução ótima, baseando-se na estrutura do grafo e nas distâncias.
   • Isso reduz o número de variáveis de decisão e a densidade do modelo, mantendo a conectividade necessária para ciclos Hamiltonianos.

Implementação Quântica:
O estudo compara três abordagens dentro do ecossistema D-Wave:

• ILP Completo (CILP): Formulação clássica com todas as restrições (usando o solver Gurobi).
• Execução Direta em QPU: O problema é convertido em um modelo QUBO (Quadratic Unconstrained Binary Optimization) e executado diretamente no processador quântico de annealing. As restrições são codificadas via termos de penalidade na função objetivo.
• Solver Híbrido Quântico-Clássico: Utiliza o modelo CQM (Constrained Quadratic Model), onde as restrições são explicitamente definidas e separadas da função objetivo. O solver híbrido (LeapCQMHybrid) orquestra heurísticas clássicas com annealing quântico para refinar a solução.

3. Contribuições Chave

• Primeira Aplicação de Geração Preguiçosa de Restrições em QA: Este trabalho representa a primeira aplicação de uma abordagem iterativa de geração de restrições (lazy constraint generation) dentro de um framework de Quantum Annealing para TSP.
• Redução de Complexidade Dupla: A combinação de CPA (reduz restrições dinamicamente) e CAF (reduz variáveis estáticamente) cria um modelo compacto, viabilizando a resolução de instâncias maiores do que o permitido por métodos diretos.
• Comparação Abrangente: O estudo avalia sistematicamente a eficácia de modelos QUBO (diretos) versus CQM (híbridos) em instâncias de benchmark padrão (TSPLIB), fornecendo uma análise detalhada de escalabilidade e qualidade da solução.

4. Resultados Computacionais

Os experimentos foram realizados em instâncias do TSPLIB (de 5 a 45 cidades), utilizando hardware clássico e recursos quânticos D-Wave Advantage2.

• Desempenho Clássico (Gurobi):

  • O modelo CILP (completo) torna-se intratável para $V \ge 20$ devido ao tempo de construção do modelo.
  • A combinação CPA + CAF resolveu instâncias de até 45 cidades em frações de segundo, com tempo de execução quase constante e zero gap de otimalidade.

• Otimização Quântica Direta (QPU - QUBO):

  • O modelo CILP falhou em encontrar soluções viáveis para $V \ge 6$.
  • O modelo CPA mostrou-se muito mais robusto, encontrando soluções viáveis e ótimas (ou quase ótimas) até $V = 8$ e mantendo viabilidade parcial até $V = 10$.
  • A limitação principal foi o tamanho do modelo QUBO gerado; mesmo com CPA, instâncias maiores ($V \ge 11$) excederam a capacidade de embedding do hardware atual.

• Otimização Híbrida Quântico-Clássica (CQM):

  • Esta foi a abordagem mais bem-sucedida.
  • O solver híbrido encontrou soluções ótimas (0% de gap) para todas as instâncias de $V = 12$ a $V = 25$.
  • Para a maior instância testada ($V = 30$), obteve-se um gap de otimalidade de apenas 1% (solução de 6206,03 vs. ótima de 6146,65).
  • O tempo de computação escalou de ~44s para $n=12$ até ~140s para $n=30$, demonstrando viabilidade prática.

5. Significância e Conclusões

• Viabilidade Prática: O trabalho demonstra que a otimização quântica para TSP não precisa ser limitada a instâncias triviais (ex: < 10 nós) se forem utilizadas estratégias de redução de modelo adequadas.
• Superioridade do Híbrido: Os resultados confirmam que, no estado atual da tecnologia, os solvers híbridos (CQM) superam significativamente as abordagens diretas em QPU (QUBO) em termos de escalabilidade e qualidade da solução, conseguindo lidar com restrições complexas sem a necessidade de penalidades excessivas que degradam o desempenho quântico.
• Ponte Teórico-Prática: A metodologia proposta preenche a lacuna entre a teoria da otimização quântica e aplicações práticas, permitindo a resolução de instâncias de benchmark padrão que anteriormente eram inacessíveis para hardware quântico.
• Futuro: O estudo sugere que, à medida que o hardware quântico evolui, a combinação de pré-processamento clássico inteligente e annealing quântico será a estratégia dominante para problemas de otimização combinatória complexos.

Em suma, o artigo estabelece que a redução inteligente do espaço de busca (via CAF e CPA) é o fator crítico para habilitar a aplicação de tecnologias quânticas em problemas NP-difíceis de escala real.