O algoritmo simplex caminha avidamente nos cantos de um politopo para encontrar a solução ideal para o problema de programação linear. Como resultado, a resposta é sempre um canto do politopo. Os métodos de pontos internos percorrem o interior do politopo. Como resultado, quando um plano inteiro do polítopo é ideal (se a função objetivo for exatamente paralela ao plano), podemos obter uma solução no meio desse plano.
Suponha que desejemos encontrar um canto do politopo. Por exemplo, se queremos fazer a correspondência máxima reduzindo-a à programação linear, não queremos obter uma resposta que consiste em "a correspondência contém 0,34% da borda XY e 0,89% da borda AB e ...". Queremos obter uma resposta com zeros e zeros (o que simplex nos daria, pois todos os cantos consistem em zeros e zeros). Existe uma maneira de fazer isso com um método de ponto interior que garante encontrar soluções exatas de canto em tempo polinomial? (por exemplo, talvez possamos modificar a função objetivo para favorecer os cantos)
Respostas:
Você pode ler o artigo:
fonte
Embora a questão em geral faça sentido, é estranho que você escolha a correspondência máxima como exemplo, porque existem muitos algoritmos (fluxos máximos para correspondência bipartida de cardinalidade máxima, algoritmo de Edmonds para correspondência não bipartida e o algoritmo húngaro para correspondência bipartida de peso máximo) tudo isso dará soluções inteiras de vértices para o problema.
fonte
Por falta de detalhes, este é apenas um comentário mais longo:
O algoritmo de tempo polinomial de Karmarkar se move apenas perto da borda. No final, encontra uma solução básica adequada (por exemplo, canto) que é ideal usando um esquema de purificação ¹. Você pode usar esta ou uma técnica semelhante para mover para um canto de um avião.
¹ Não consigo constar no artigo original de Karmarkar . Minha referência é "Lineare Optimierung und Netzwerkoptimierung" (inglês: otimização linear e de rede) de Hamacher e Klamroth, que tem texto em alemão e inglês lado a lado.
fonte
Sim, existe um método simples e eu o implementei em C ++ para combinar a velocidade dos métodos de pontos interiores com a precisão dos métodos simplex (usando o refinamento iterativo do inverso da matriz base, posso obter precisões de 1 parte em 10 ^ 15 e melhor em matrizes de restrição densa com mais de 1000 variáveis e restrições).
A chave está no método simplex que você usa. Suponha que o método simplex tenha um mecanismo para refatorar uma base (por exemplo, após erros cumulativos de arredondamento tornarem necessário), e que esse método de refatoração simplesmente recrie uma matriz inversa de base para uma base que contenha toda a lista desejada de variáveis básicas. Além disso, suponha que, mesmo que a base desejada não possa ser recriada na íntegra, que o algoritmo simplex possa continuar a partir de uma base que contenha 95% da base de destino, então a resposta é muito simples.
Tudo o que você precisa fazer é pegar a solução a partir do seu método de ponto interior, eliminar a variável cujos valores primários da solução estão implícitos em zero pela folga complementar e, dado um tamanho de base no problema simplex de b, pegar as variáveis b no interior solução pontual com os maiores valores (ou tantos quantos houver valores diferentes de zero se for menor que b) e refatorar a base simples para conter essas b variáveis. Continue o método simplex até que ele seja resolvido. Como você está iniciando o problema simplex próximo ao final, isso geralmente é muito rápido.
fonte