On the facet pivot simplex method for linear programming

Este artigo propõe um novo método simplex de pivoteamento por facetas para programação linear que demonstra promessa superior à abordagem tradicional de pivoteamento por vértice em testes numéricos, oferecendo nova esperança para a descoberta de um algoritmo de pivoteamento de tempo polinomial.

O essencial

Imagine que você está tentando encontrar o melhor lugar absoluto para montar um quiosque de limonada em uma cidade. A cidade tem a forma de um edifício complexo e poligonal (um poliedro), e você deseja encontrar o canto que lhe trará mais dinheiro.

Por mais de 70 anos, a maneira padrão de fazer isso foi o Método de Pivô de Vértice (inventado por George Dantzig). Pense neste método como um turista caminhando ao exterior do edifício. Ele começa em um canto (vértice), observa os cantos vizinhos e caminha até aquele que parece melhor. Ele continua saltando de canto em canto ao longo das arestas até encontrar o melhor lugar.

O problema é que, às vezes, o edifício é projetado com um labirinto intrincado de cantos. Nos piores cenários, o turista pode ter que passar por cada canto individual em uma ordem específica e exaustiva antes de encontrar o melhor. Isso é como atravessar um labirinto que se torna exponencialmente mais longo à medida que o edifício cresce.

A Nova Ideia: O Método de "Pivô de Faceta"

Neste artigo, o autor, Yaguang Yang, propõe uma nova maneira de resolver esse problema, chamada de Método Simplex de Pivô de Faceta.

Em vez de caminhar ao longo dos cantos (vértices), imagine que você é um inspetor de construção observando as facetas do edifício.

• O Jeito Antigo (Vértice): Você é um turista saltando de canto em canto.
• O Jeito Novo (Faceta): Você é um inspetor trocando as facetas que definem sua "base" atual para chegar mais perto do melhor lugar.

Veja como o novo método funciona em termos simples:

1. Comece pelas Facetas, Não pelos Cantos: Em vez de começar em um canto, o algoritmo começa escolhendo um conjunto de facetas (restrições) que definem uma posição temporária, talvez imperfeita.
2. Troque Facetas, Não Cantos: O algoritmo examina as facetas que estão atualmente "violadas" ou não satisfeitas (como uma faceta que está inclinada para o lado errado). Ele escolhe a pior delas e a troca por uma faceta diferente que ajuda a resolver o problema.
3. Sem Desvio da "Fase 1": O método antigo frequentemente exige uma longa e custosa viagem de "Fase 1" apenas para encontrar um canto inicial válido antes mesmo de poder começar a procurar o melhor. O novo método é inteligente: ele começa com uma configuração matematicamente garantida para funcionar imediatamente, pulando completamente esse longo desvio. É como ter uma chave mágica que abre a porta do edifício instantaneamente, em vez de tentar arrombar a fechadura primeiro.

Por que isso é emocionante?

O artigo afirma que este novo método é muito promissor por duas razões principais:

• É Mais Rápido em Labirintos Difíceis: O autor testou isso em "cubos de Klee-Minty", que são labirintos matemáticos projetados especificamente para enganar o antigo método do turista, fazendo-o levar uma eternidade. O novo método de troca de facetas resolveu esses labirintos muito mais rápido, levando apenas algumas etapas em vez de milhares.
• É Mais Robusto: Quando testado em uma enorme coleção de problemas matemáticos do mundo real (os benchmarks Netlib), o novo método resolveu quase todos com sucesso. O antigo método do "turista" às vezes ficava preso ou levava muito tempo, e o método "dual" (um tipo diferente de turista) às vezes desistia porque a geometria do edifício era muito complicada. O método de troca de facetas lidou melhor com essas geometrias complicadas.

O Obstáculo (e a Esperança)

O artigo admite que, para problemas muito grandes e simples, o método antigo (ou outros métodos como os métodos de "Ponto Interior", que são como voar com um drone pelo meio do edifício) ainda podem ser mais rápidos.

No entanto, a grande esperança é que essa nova abordagem de "troca de facetas" possa ser a chave para resolver um famoso mistério matemático de 60 anos: Podemos encontrar um método que seja garantidamente rápido (tempo polinomial) para todo problema?

Por décadas, matemáticos tentaram provar que o antigo método de "salto de canto" é rápido o suficiente, mas encontraram casos em que ele é incrivelmente lento. Este novo método de "troca de facetas" oferece uma perspectiva fresca. Ele não depende das mesmas regras antigas, e testes iniciais sugerem que pode ser o caminho para uma solução que seja tanto rápida quanto confiável para todos os tipos de problemas de programação linear.

Em resumo: O artigo apresenta uma nova maneira de resolver problemas de otimização matemática trocando "facetas" em vez de saltar "cantos". Ele pula as etapas de configuração entediantes, lida melhor com labirintos complicados do que os métodos antigos e dá aos matemáticos uma nova esperança de encontrar uma solução perfeita e rápida para todos os problemas.

Resumo técnico

Resumo Técnico: Sobre o método simplex de pivô de faceta para programação linear

Enunciado do Problema
O artigo aborda a eficiência computacional e as limitações teóricas do método simplex de pivô de vértice padrão para resolver problemas de Programação Linear (PL). Embora o método simplex de vértice de Dantzig permaneça altamente eficaz na prática, carece de um limite de complexidade de tempo polinomial comprovado. Teoricamente, o pior caso para métodos de vértice envolve um número exponencial de iterações (como demonstrado pelos cubos de Klee-Minty), e a busca por um algoritmo de pivô de tempo polinomial tem permanecido elusiva por décadas. Além disso, os métodos de vértice tradicionais frequentemente exigem um processo de "Fase I" computacionalmente caro para encontrar uma solução básica inicial viável, particularmente para problemas de PL gerais envolvendo restrições de desigualdade e limites.

Metodologia
Os autores propõem um método simplex de pivô de faceta que desloca fundamentalmente a operação de pivô de vértices para facetas (restrições).

• Formulação Geral: O método opera sobre uma formulação geral de PL:
  $$\min c^T x$$
  $$\text{sujeito a } A_I x = b_I, \quad A_J x \ge b_J, \quad \ell \le x \le u$$
  Diferentemente de formas padrão que convertem desigualdades em igualdades por meio de variáveis de folga, esta abordagem trata as restrições de desigualdade diretamente como facetas do poliedro viável.

• Lógica Algorítmica:

  • Definição de Base: Em vez de uma base de variáveis (vértices), o algoritmo mantém uma base de $d$ facetas linearmente independentes (restrições), onde $d$ é a dimensão do problema.
  • Processo Iterativo: O algoritmo inicia com uma solução básica inicial (frequentemente derivada diretamente de restrições de limite) que não é necessariamente viável. Em cada iteração, seleciona uma faceta de entrada (uma restrição não básica) e uma faceta de saída (uma restrição básica) para atualizar a base.
  • Viabilidade e Otimalidade: O algoritmo mantém uma representação do vetor objetivo $c$ como uma combinação linear não negativa das facetas básicas atuais (satisfazendo uma condição derivada do Lema de Farkas). Melhora iterativamente a solução substituindo facetas para reduzir violações de restrições.
  • Terminação: O processo para quando uma solução básica viável é encontrada. De acordo com os teoremas de otimalidade apresentados, se o vetor objetivo puder ser expresso como uma combinação não negativa das facetas básicas ativas em um ponto viável, esse ponto é ótimo.
  • Convergência Finita: O artigo prova que, se a "regra do menor/menor índice" for aplicada para selecionar facetas de entrada e saída, o algoritmo evita ciclos e termina em um número finito de etapas.

• Distinções Chave em Relação ao Simplex Dual: Embora o método de pivô de faceta compartilhe algumas similaridades geométricas com o método simplex dual (movendo-se entre bases de restrições), ele é distinto porque opera exclusivamente sobre o problema primal sem construir ou resolver explicitamente um problema dual. Ele lida diretamente com a forma geral, evitando a conversão para a forma padrão.

Contribuições Principais

1. Proposta Algorítmica: O artigo introduz um algoritmo específico de pivô de faceta (Algoritmo 4.1) que resolve problemas gerais de PL sem exigir uma etapa de inicialização de Fase I.
2. Garantias Teóricas: Os autores fornecem provas matemáticas (baseadas no Lema de Farkas) demonstrando que o algoritmo encontra uma solução ótima em iterações finitas e identifica corretamente problemas inviáveis ou ilimitados.
3. Implementação: É fornecida uma implementação em MATLAB do algoritmo, juntamente com implementações do simplex de Dantzig, simplex dual e métodos de ponto interior para comparação.
4. Tratamento de Restrições: O método lida naturalmente com limites inferiores e superiores e variáveis livres sem introduzir variáveis de folga artificiais, resultando em um tamanho de problema menor comparado às conversões para forma padrão.

Resultados Experimentais
Os autores conduziram testes numéricos em vários conjuntos de referência:

• Benchmarks Netlib: Em problemas Netlib padrão com limites inferiores e superiores, o método de pivô de faceta geralmente exigiu menos segundos de CPU do que a regra de pivô mais negativa de Dantzig. Ele resolveu com sucesso problemas onde o método simplex dual falhou devido a deficiência de posto ou mau condicionamento.
• Problemas de Grande Escala: Para problemas muito grandes (por exemplo, $n > 50.000$), os Métodos de Ponto Interior (MPI) superaram todos os métodos de pivô, como esperado. No entanto, o método de pivô de faceta demonstrou robustez onde o método simplex dual falhou.
• Cubos de Klee-Minty: O método de pivô de faceta demonstrou desempenho significativamente melhor do que o método de vértice de Dantzig em variantes de Klee-Minty, exigindo muito menos iterações (frequentemente lineares ou quase lineares na dimensão $d$) em comparação com as iterações exponenciais exigidas pelo método de vértice.
• Problemas Gerais Aleatórios: Para problemas gerais de PL que exigem uma Fase I em métodos padrão, o método de pivô de faceta foi significativamente mais eficiente do que o método de Dantzig porque contornou a inicialização de Fase I.
• Problemas Aleatórios Padrão: Para problemas de PL padrão onde a Fase I não é necessária, o método de Dantzig foi observado como ligeiramente mais eficiente em tempo de CPU, embora as contagens de iterações fossem comparáveis.

Significado e Alegações
O artigo alega que o método simplex de pivô de faceta oferece uma alternativa promissora aos métodos baseados em vértices, particularmente para problemas gerais de PL com restrições de desigualdade. Seu significado principal reside em:

• Eliminação da Fase I: Ao iniciar a partir de uma solução básica derivada de restrições de limite, evita a fase de inicialização cara exigida pelos métodos simplex tradicionais para problemas gerais.
• Robustez: Demonstra maior estabilidade numérica do que o método simplex dual em problemas Netlib mal condicionados.
• Esperança para Complexidade Polinomial: Embora os autores não aleguem ter provado um limite de tempo polinomial, eles sugerem que este novo tipo de algoritmo de pivô (operando em facetas em vez de vértices) fornece uma nova via de pesquisa para encontrar um método simplex de pivô polinomial, abordando o 9º problema de Smale.
• Eficiência Prática: O método mostrou-se altamente competitivo e frequentemente superior ao método de Dantzig para problemas envolvendo muitas restrições de desigualdade, sem a sobrecarga de convertê-las em igualdades.

Os autores mantêm um tom modesto, reconhecendo que os Métodos de Ponto Interior permanecem superiores para problemas de escala muito grande e que o método de pivô de faceta é uma nova direção que requer investigação adicional para compreender plenamente seus limites de complexidade teórica.