Traveling Salesman Problem with a preprocessing method for classical and quantum optimization

Este artigo apresenta uma estratégia de pré-processamento que reduz o tamanho do modelo do Problema do Caixeiro Viajante ao restringir os arcos candidatos, demonstrando experimentalmente melhorias no tempo computacional e na qualidade da solução tanto para métodos clássicos quanto para otimização quântica.

O essencial

Imagine que você é um carteiro em uma cidade enorme e precisa entregar cartas em todas as casas, passando por cada uma exatamente uma vez, e voltando para o escritório no final. O seu objetivo é fazer isso gastando a menor quantidade possível de combustível.

Esse é o famoso Problema do Caixeiro Viajante. Parece simples, certo? Mas, à medida que a cidade cresce (mais casas), o número de rotas possíveis explode de forma assustadora. É como tentar encontrar a agulha no palheiro, mas o palheiro está crescendo exponencialmente a cada nova casa adicionada.

Este artigo apresenta uma "mágica" inteligente para resolver esse problema, funcionando tanto para computadores comuns quanto para os supercomputadores do futuro (os computadores quânticos).

Aqui está a explicação, passo a passo, usando analogias do dia a dia:

1. O Problema: O Labirinto Gigante

Pense no mapa da cidade como uma teia de aranha gigante onde cada casa é um ponto e cada rua é um fio. Para encontrar o caminho perfeito, um computador precisa testar milhões de combinações de fios.

• O desafio: Em computadores clássicos, isso demora muito. Em computadores quânticos (que são muito potentes, mas ainda "bebês" e têm poucos recursos), tentar testar todas as ruas é como tentar encher um copo de água com um balde inteiro: o sistema trava porque é grande demais.

2. A Solução: O Filtro "CAF" (A Regra do Vizinho Próximo)

Os autores criaram uma técnica de pré-processamento chamada Filtragem de Arcos Baseada em Custos (CAF).

A Analogia do Restaurante:
Imagine que você está em um restaurante e quer pedir o prato mais barato e gostoso.

• Sem o filtro: Você olha para o cardápio inteiro, que tem 1.000 pratos, e tenta calcular a combinação perfeita de todos eles. É exaustivo.
• Com o filtro (CAF): Você decide uma regra simples: "Eu só vou considerar os 5 pratos mais baratos e mais próximos da minha mesa". Você ignora os 995 pratos que estão no fundo do cardápio ou que são caros demais.

Como funciona na prática:
Para cada cidade (ponto), o método olha para todas as estradas possíveis e corta as estradas longas e caras. Ele mantém apenas as estradas que levam aos vizinhos mais próximos e baratos.

• A garantia matemática: Os autores provaram que, mesmo cortando essas estradas longas, ainda existe pelo menos um caminho perfeito que passa por todas as casas. É como dizer: "Você pode ignorar a estrada que vai para a outra ponta do país, porque a solução ótima quase certamente usa as ruas do bairro".

3. Por que isso é genial?

Para Computadores Clássicos (Os "Gigantes" de Hoje)

Ao remover as estradas longas, o computador tem muito menos trabalho.

• Resultado: O tempo de cálculo cai drasticamente. Em testes, o computador resolveu problemas grandes quase duas vezes mais rápido. É como limpar a mesa de trabalho antes de começar a montar um quebra-cabeça: você joga fora as peças que não servem e foca apenas nas que importam.

Para Computadores Quânticos (Os "Bebês" do Futuro)

Aqui é onde a mágica brilha. Computadores quânticos atuais têm um limite de "memória" (chamada de qubits). Eles não conseguem segurar um problema grande na cabeça.

• O Problema: Antes desse método, só era possível resolver cidades com 5 ou 6 casas em um computador quântico.
• A Mágica: Ao usar o filtro CAF, o problema ficou pequeno o suficiente para caber na "memória" do computador quântico. De repente, eles conseguiram resolver cidades com 15 casas (o dobro do tamanho anterior) usando essa tecnologia.
• A qualidade: Mesmo com menos opções, o computador quântico encontrou soluções quase perfeitas, muito melhores do que tentaria encontrar sem o filtro.

4. A Conclusão em uma Frase

O artigo diz que, em vez de tentar forçar o computador a olhar para tudo, é mais inteligente ensiná-lo a olhar apenas para o que realmente importa (os vizinhos próximos).

Isso torna o problema "mais leve", permitindo que computadores de hoje sejam mais rápidos e que computadores quânticos do futuro consigam resolver problemas reais, e não apenas brinquedos teóricos. É como dar um mapa simplificado para um turista: ele não perde a rota principal, mas chega ao destino muito mais rápido porque não se distrai com becos sem saída.

Resumo técnico

Resumo Técnico: Método de Pré-processamento para o Problema do Caixeiro Viajante (TSP) em Otimização Clássica e Quântica

1. O Problema

O Problema do Caixeiro Viajante (TSP) é um problema fundamental de otimização combinatória onde o objetivo é encontrar o caminho mais curto que visita cada cidade exatamente uma vez e retorna ao ponto de partida.

• Desafios: O TSP é classificado como NP-difícil. A complexidade computacional cresce exponencialmente com o número de cidades ($n$), resultando em um espaço de busca vasto.
• Limitações Atuais:
  • Clássico: Modelos de Programação Linear Inteira (ILP) exigem um grande número de variáveis de decisão e restrições de eliminação de sub-tours, tornando a resolução lenta para instâncias médias e grandes.
  • Quântico: O uso de Quantum Annealing (QA) e solvers híbridos quântico-clássicos (como os da D-Wave) é limitado pela conectividade do hardware e pelo número de qubits disponíveis. Problemas de roteamento exigem estruturas de restrições complexas que aumentam drasticamente o número de variáveis e interações nos modelos QUBO (Quadratic Unconstrained Binary Optimization), impedindo a resolução de instâncias realistas.

2. Metodologia Proposta: Filtragem de Arcos Baseada em Custos (CAF)

Os autores propõem uma estratégia de pré-processamento chamada CAF (Cost-Based Arc Filtering) para reduzir o tamanho do modelo de otimização sem comprometer a viabilidade da solução.

• Princípio Teórico: O método baseia-se no Teorema de Dirac da teoria dos grafos, que estabelece que um grafo com $n$ vértices é Hamiltoniano (contém um ciclo que visita todos os vértices) se o grau mínimo de cada vértice for pelo menos $n/2$.
• Algoritmo CAF:
  1. Para cada vértice (cidade) $i$, os arcos (rotas) para outros vértices são ordenados por custo crescente.
  2. Mantém-se apenas os $k = \lceil n/2 \rceil$ vizinhos com os menores custos.
  3. Os arcos restantes são removidos do conjunto de candidatos.
• Garantias:
  • Viabilidade: O grafo reduzido resultante mantém um grau mínimo suficiente para garantir a existência de pelo menos um ciclo Hamiltoniano (teorema de Dirac).
  • Qualidade da Solução: Em instâncias Euclidianas (distâncias geográficas), as soluções ótimas tendem a conectar vértices próximos. Ao filtrar arcos de longa distância, o método concentra a busca na região mais promissora do espaço de soluções.

3. Abordagem de Solução

O estudo compara a eficácia do CAF em dois ambientes:

1. Otimização Clássica: Utilização do solver comercial Gurobi para resolver o modelo ILP com e sem pré-processamento.
2. Otimização Híbrida Quântica: Utilização do solver híbrido LeapCQM da D-Wave (baseado em Constrained Quadratic Model - CQM) para resolver as instâncias pré-processadas.

4. Resultados Computacionais

Os experimentos foram realizados em instâncias do benchmark TSPLIB (especificamente derivadas de berlin52.tsp), variando de 5 a 50 vértices.

• Redução do Modelo:

  • O CAF reduz o número de variáveis de decisão em aproximadamente 30% em média.
  • A redução torna-se mais significativa à medida que o número de vértices aumenta (ex: de 2450 variáveis para 1652 em $n=50$).

• Desempenho Clássico (Gurobi):

  • Tempo de Resolução: Para instâncias médias e grandes ($V \ge 10$), o tempo de resolução foi reduzido em 32% a 54%.
  • Qualidade: Para instâncias até $V=20$, a otimalidade foi provada em ambos os casos. Para $V=21$, onde o solver sem pré-processamento atingiu o limite de tempo (300s) sem encontrar um limite inferior válido, a versão com CAF encontrou uma solução com valor objetivo melhor, demonstrando vantagem prática mesmo sem garantia de otimalidade.

• Desempenho Quântico (D-Wave):

  • Escalabilidade: O pré-processamento permitiu resolver instâncias com até 15 clientes usando otimização quântica, um tamanho superior ao comumente relatado na literatura devido às limitações de hardware.
  • Qualidade da Solução: O uso do CAF reduziu a lacuna de otimalidade (optimality gap) em média em 29-31% em comparação com o modelo completo.
    • Exemplo: Para $V=13$, o gap caiu de 43% (sem CAF) para 11% (com CAF).
  • Eficiência: Houve uma redução média de 5% no tempo total de computação e de 17% no tempo de solução pura para a maior instância testada ($V=15$).

5. Contribuições Principais

1. Novo Método de Pré-processamento: Introdução do CAF, que alia a teoria dos grafos (Dirac) com heurísticas de custo para reduzir drasticamente a complexidade do TSP.
2. Viabilidade Garantida: Prova teórica de que a redução de arcos não elimina a existência de soluções viáveis (ciclos Hamiltonianos).
3. Avaliação Híbrida: Uma das primeiras avaliações que utiliza benchmarks padrão (TSPLIB) em vez de problemas artificiais para testar a otimização quântica no TSP.
4. Ponte Clássico-Quântica: Demonstra que técnicas de pré-processamento clássicas são essenciais para tornar problemas de roteamento viáveis para os atuais solvers quânticos híbridos.

6. Significância e Conclusão

O artigo demonstra que a escalabilidade de modelos de otimização combinatória, especialmente para hardware quântico emergente, depende criticamente da redução do espaço de busca antes da execução do solver.

• A estratégia CAF não apenas melhora o desempenho de solvers clássicos tradicionais, mas é crucial para a aplicação prática de computação quântica em problemas de roteamento realistas.
• Ao permitir a resolução de instâncias maiores (até 15 nós no contexto quântico testado) com maior qualidade de solução e menor tempo, o método posiciona-se como uma ferramenta prática para superar as limitações atuais de conectividade e número de qubits.
• Trabalhos futuros sugerem a exploração de técnicas iterativas e refinamento dinâmico do modelo para lidar com instâncias de escala ainda maior.