Algoritmo de Karmarkar

O algoritmo de Karmarkar é um algoritmo introduzido por Narendra Karmarkar, em 1984, para resolver problemas de programação linear. Foi o primeiro algoritmo razoavelmente eficiente para resolver esses problemas em tempo polinomial. O método elipsoide é também de tempo polinomial, mas provou ser ineficaz na prática.

Onde $n$ é o número de variáveis e $L$ é o número de bits de entrada, o algoritmo de Karmarkar requer $O(n^{3.5}L)$ operações, $O(L)$ números de dígitos, enquanto que no algoritmo elipsóide são necessárias $O(n^{6}L)$ operações. O tempo de execução do algoritmo de Karmarkar é:

$O(n^{3.5}L^{2}\cdot \log L\cdot \log \log L)$

usando FFT (Fast Fourier Transform).

O algoritmo de Karmarkar está na classe de método de pontos interiores: a atual estimativa para a solução não segue o limite da região viável como no método simplex, mas ele se move através do interior da região viável, melhorando a aproximação da ótima solução, por uma fração definitiva com cada iteração, e converge para uma ótima solução de dado racional.

O algoritmo

Considere um problema de programação linear na forma de matriz:

maximizar cTx
sujeito a	Ax ≤ b.

O algoritmo de Karmarkar determina a próxima direção viável da e as escalas de volta por um fator de 0 < γ ≤ 1. Ele é descrito em um número de fontes.

Como o atual algoritmo é bastante complicado, os pesquisadores foram à procura de uma versão mais intuitiva, e, em 1985, "inventaram" affine scaling, uma versão do algoritmo de Karmarkar que utiliza transformações afim, onde Karmarkar usava projetiva, apenas para perceber quatro anos mais tarde, que eles tinham reinventado um algoritmo publicado por um matemático Soviético I. I. Dikin em 1967. O método affine scaling pode ser descrito sucintamente da seguinte maneira. Note que o algoritmo affine scaling, enquanto aplicável a pequenos problemas de escala, não é um algoritmo de tempo polinomial. Karmarkar também ampliou o método para resolver problemas com restrições de número inteiro e problemas não convexos.

Algoritmo: affine scaling
  Entrada:  A, b, c, $x^{0}$, Condição de parada, γ.

  $k\leftarrow 0$
  do while Condição de parada não_satisfeita
     $v^{k}\leftarrow b-Ax^{k}$
     $D_{v}\leftarrow \operatorname {diag} (v_{1}^{k},\ldots ,v_{m}^{k})$
     $h_{x}\leftarrow (A^{T}D_{v}^{-2}A)^{-1}c$
     $h_{v}\leftarrow -Ah_{x}$
     if $h_{v}\geq 0$ then
        return unbounded
     end if
     $\alpha \leftarrow \gamma \cdot \min\{-v_{i}^{k}/(h_{v})_{i}\,\,|\,\,(h_{v})_{i}<0,\,i=1,\ldots ,m\}$
     $x^{k+1}\leftarrow x^{k}+\alpha h_{x}$
     $k\leftarrow k+1$
  end do

Exemplo

Exemplo

Considere o programa linear

maximizar		$x_{1}$	+	$x_{2}$
sujeito a		$2px_{1}$	+	$x_{2}$	$\leq$ $p^{2}+1$, $p=0.0,0.1,0.2,\ldots ,0.9,1.0.$

Isto é, existem 2 variáveis $x_{1},x_{2}$ e 11 restrições associadas a diferentes valores de $p$. Esta figura mostra a cada iteração do algoritmo, (pontos vermelho). As restrições são mostradas como linhas azuis.

Controvérsia da patente

Na época em que ele inventou o algoritmo, Karmarkar foi contratado pela IBM como um postdoctoral fellow no IBM San Jose Research Laboratory, na Califórnia. Em 11 de agosto de 1983, ele deu um seminário na Universidade de Stanford, explicando o algoritmo, ainda afiliado à IBM. No Outono de 1983 Karmarkar, quando começou a trabalhar na AT&T e apresentou o seu artigo no 1984 ACM Symposium on Theory of Computing (STOC, realizada entre 30 de abril e 2 de Maio de 1984), declarando a AT&T Bell Laboratories como a sua filiação. Após a aplicação do algoritmo à otimização da rede telefônica da AT&T, eles perceberam que sua invenção poderia ser de importância prática. Em abril de 1985, a AT&T submeteu um pedido de patente para o algoritmo de Karmarkar.

A patente tornou-se mais combustível para a atual controvérsia sobre a questão das patentes de software. Isso deixou muitos matemáticos inquietos, como Ronald Rivest (um dos titulares da patente do algoritmo RSA), que expressaram a opinião de que os algoritmos devem ser livres. Mesmo antes da patente ser concedida, foi alegado que pode ter havido técnica anterior que era aplicável. Matemáticos que se especializaram em análise numérica, incluindo Philip Gill e outros, alegaram que o algoritmo de Karmarkar é equivalente a um método de barreira de Newton com uma função de barreira logarítmica, se os parâmetros forem escolhidos adequadamente. O jurista Andrew Queixo opinou que o argumento Gill foi falho, visto que o método que eles descrevem não constituem um "algoritmo", pois requer escolhas de parâmetros que não seguem a lógica interna do método, mas dependem de orientação externa, essencialmente, a partir do algoritmo de Karmarkar. Além disso, as contribuições de Karmarkar são consideradas longe do óbvio, à luz de todos os trabalhos anteriores, incluindo Fiacco-McCormick, Gill e outros citados por Saltzman. A patente foi debatida no Senado dos EUA e concedida em reconhecimento à originalidade essencial do trabalho de Karmarkar, como Patente E.U.A. 4 744 028: "Métodos e aparelhos para alocação de recursos eficiente", em Maio de 1988.

A AT&T projetou um sistema de computador baeado em vetor de multiprocessador especificamente para executar o algoritmo de Karmarkar, chamando a combinação resultante de hardware e software KORBX, e comercializando este sistema a um preço de USD8.9 milhões. Seu primeiro cliente foi o Pentágono.

Adversários das patentes de software ainda alegam que as patentes arruinam os ciclos de interação positiva que anteriormente caracterizavam o relacionamento entre os pesquisadores em programação linear e a indústria, e, especificamente deixaram Karmakar isolado da rede de pesquisadores matemáticos em sua área.

A patente em si expirou em abril de 2006, e o algoritmo atualmente está em domínio público.

Referências

• Ilan Adler, Narendra Karmarkar, Mauricio G. C. Resende e Geraldo Veiga (1989). "Uma Implementação de Karmarkar do Algoritmo de Programação Linear". Programação matemática, Vol. 44, p. 297–335.
• Narendra Karmarkar (1984). "Um novo algoritmo de tempo polinomial para programação linear", Combinatorica, Vol 4, nr. 4, p. 373–395.