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 que resolve esses problemas em tempo polinomial. O método elipsoide é também de tempo polinomial, mas provou ser ineficaz na prática.

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

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.[1]

O algoritmoEditar

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

maximizar cTx
sujeito a Axb.

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.[2][3][4][5][6][7]

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.[8] O método affine scaling pode ser descrito sucintamente da seguinte maneira.[9] 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[o que?][10][11][12][13] para resolver problemas com restrições de número inteiro e problemas não convexos.[14]

Algoritmo: affine scaling
  Entrada:  A, b, c,  , Condição de parada, γ.
   
  do while Condição de parada não_satisfeita
      
      
      
      
     if   then
        return unbounded
     end if
      
      
      
  end do

ExemploEditar

 
Exemplo

Considere o programa linear

maximizar   +  
sujeito a   +      ,  

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

Controvérsia da patente — Matemática pode ser patenteada?Editar

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.[15] Após a aplicação do algoritmo à otimização da rede telefônica da AT&T,[16] 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.[17] 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.[18] 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.[19] 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.[20] 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.[20][21][22] 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,[23] e comercializando este sistema a um preço de USD8.9 milhões.[24][25] Seu primeiro cliente foi o Pentágono.[26][27]

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.[28]

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

Referências

  1. Strang, Gilbert (1 de junho de 1987). «Karmarkar's algorithm and its place in applied mathematics». New York: Springer. The Mathematical Intelligencer. 9 (2): 4–10. ISSN 0343-6993. MR '''883185'''. doi:10.1007/BF03025891 
  2. http://dl.acm.org/citation.cfm?id=808695
  3. http://link.springer.com/article/10.1007%2FBF02579150
  4. http://onlinelibrary.wiley.com/doi/10.1002/j.1538-7305.1989.tb00316.x/abstract
  5. Karmarkar N.K., An Interior Point Approach to NPComplete Problems Part I, AMS series on Contemporary Mathematics 114, pp. 297308 (June 1990). http://www.ams.org/books/conm/114/conm114-endmatter.pdf
  6. Karmarkar, N.K.., Riemannian Geometry Underlying Interior Point Methods for Linear programming, AMS series on Contemporary Mathematics 114, pp. 5175 (June 1990). http://www.ams.org/books/conm/114/conm114-endmatter.pdf
  7. Karmarkar N. K., Lagarias, J.C., Slutsman, L., and Wang, P., Power Series Variants of KarmarkarType Algorithm, AT & T technical Journal 68, No. 3, May/June (1989).
  8. Vanderbei, R. J.; Lagarias, J. C. (1990). «I. I. Dikin's Convergence Result for the Affine-Scaling Algorithm» (PDF). Contemporary Mathematics. 114 
  9. Robert J. Vanderbei; Meketon, Marc; Freedman, Barry (1986). «A Modification of Karmarkar's Linear Programming Algorithm» (PDF). Algorithmica. 1: 395–407. doi:10.1007/BF01840454 
  10. Karmarkar, N.K.,Interior Point Methods in Optimization, Proceedings of the Second International Conference on Industrial and Applied Mathematics, SIAM, pp. 160181 (1991)
  11. Karmarkar, N. K. and Kamath, A. P., A continuous Approach to Deriving Upper Bounds in Quadratic Maximization Problems with Integer Constraints, Recent Advances in Global Optimization, pp. 125140, Princeton University Press (1992).
  12. 26.
  13. 27.
  14. Karmarkar, N. K., Beyond Convexity: New Perspectives in Computational Optimization.
  15. Karmarkar Algorithm, IBM Research, consultado em 1 de junho de 2016 
  16. Sinha L.P., Freedman, B. A., Karmarkar, N. K., Putcha, A., and Ramakrishnan K.G., Overseas Network Planning, Proceedings of the Third International Network Planning Symposium, NETWORKS' 86, Tarpon Springs, Florida (June 1986).
  17. Kolata, Gina (12 de março de 1989). «IDEAS & TRENDS; Mathematicians Are Troubled by Claims on Their Recipes». The New York Times 
  18. Various posts by Matthew Saltzman, Clemson University
  19. Gill, Philip E.; Murray, Walter; Saunders, Michael A.; Tomlin, J. A.; Wright, Margaret H. (1986). «On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method». Mathematical Programming. 36 (2): 183–209. doi:10.1007/BF02592025 
  20. a b Andrew Chin (2009). «On Abstraction and Equivalence in Software Patent Doctrine: A Response to Bessen, Meurer and Klemens» (PDF). Journal of Intellectual Property Law. 16: 214–223 
  21. Mark A. Paley (1995).
  22. Margaret H. Wright (2004). «The Interior-Point Revolution in Optimization: History, Recent Developments, and Lasting Consequences» (PDF). Bulletins of the American Mathematical Society. 42: 39–56 
  23. Marc S. Meketon; Y.C. Cheng, D.J. Houck, J.M.Liu, L. Slutsman, Robert J. Vanderbei, and P. Wang (1989). «The AT&T KORBX System». AT&T Technical Journal. 68: 7–19 
  24. Lowenstein, Roger (15 de agosto de 1988). «AT&T markets problem solver, based on math whiz's find, for $8.9 million» (PDF). Wall Street Journal 
  25. Markoff, John (13 de agosto de 1988). «Big A.T.&T. Computer for Complexities» 
  26. «Military Is First Announced Customer Of AT&T Software». AP News (em inglês) 
  27. Kennington, J. L. (Dezembro de 1989). «Using KORBX for military airlift applications». Proceedings of the 28th IEEE Conference on Decision and Control,: 1603–1605 vol.2. doi:10.1109/CDC.1989.70419 
  28. «今野浩: カーマーカー特許とソフトウェア – 数学は 特許に なるか (Konno Hiroshi: The Kamarkar Patent and Software – Has Mathematics Become Patentable?)». FFII. Consultado em 2 de julho de 2016. Arquivado do original em 27 de junho de 2008 
  • 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.