El algoritmo de Karmarkar es un algoritmo introducido por Narendra Karmarkar en 1984 para resolver problemas de programación lineal . Fue el primer algoritmo razonablemente eficiente que resuelve estos problemas en tiempo polinomial . El método del elipsoide también es de tiempo polinómico, pero demostró ser ineficaz en la práctica.
Denotando como el número de variables y como el número de bits de entrada al algoritmo, el algoritmo de Karmarkar requiere operaciones en números de dígitos, en comparación con tales operaciones para el algoritmo elipsoide. Por tanto, el tiempo de ejecución del algoritmo de Karmarkar es
utilizando la multiplicación basada en FFT (consulte la notación Big O ).
El algoritmo de Karmarkar cae dentro de la clase de métodos de punto interior : la estimación actual de la solución no sigue el límite del conjunto factible como en el método simplex , sino que se mueve a través del interior de la región factible, mejorando la aproximación de la solución óptima. por una fracción definida con cada iteración, y convergiendo a una solución óptima con datos racionales. [1]
El algoritmo
Considere un problema de programación lineal en forma de matriz:
maximizar c T x | |
sujeto a | Ax ≤ b . |
El algoritmo de Karmarkar determina la siguiente dirección factible hacia la optimización y se reduce en un factor 0 <γ ≤ 1 . Se describe en varias fuentes. [2] [3] [4] [5] [6] [7] Karmarkar también ha extendido el método [8] [9] [10] [11] para resolver problemas con restricciones de números enteros y problemas no convexos. [12]
Escalado afín del algoritmo
Dado que el algoritmo real es bastante complicado, los investigadores buscaron una versión más intuitiva del mismo, y en 1985 desarrollaron el escalado afín , una versión del algoritmo de Karmarkar que usa transformaciones afines donde Karmarkar usó proyectivas , solo para darse cuenta cuatro años después de que habían redescubierto un algoritmo publicado por el matemático soviético II Dikin en 1967. [13] El método de escalado afín se puede describir sucintamente como sigue. [14] El algoritmo de escalado afín, si bien es aplicable a problemas de pequeña escala, no es un algoritmo de tiempo polinomial. [ cita requerida ]
Entrada: A, b, c, , criterio de parada , γ .
hacer mientras se detiene el criterio no se cumple Si luego devuelve el final ilimitado si fin de hacer
- "←" denota asignación . Por ejemplo, " más grande ← artículo significa" que el valor de los mayores cambios en el valor del elemento .
- " return " termina el algoritmo y genera el siguiente valor.
Ejemplo
Considere el programa lineal
Es decir, hay 2 variables y 11 restricciones asociadas con valores variables de . Esta figura muestra cada iteración del algoritmo como puntos del círculo rojo. Las restricciones se muestran como líneas azules.
Controversia sobre patentes: ¿se pueden patentar las matemáticas?
En el momento en que inventó el algoritmo, IBM contrató a Karmarkar como becario postdoctoral en el Laboratorio de Investigación de IBM San José en California. El 11 de agosto de 1983, dio un seminario en la Universidad de Stanford explicando el algoritmo, y su afiliación aún figuraba como IBM. En el otoño de 1983, Karmarkar comenzó a trabajar en AT&T y presentó su artículo al Simposio ACM sobre Teoría de la Computación de 1984 (STOC, celebrado del 30 de abril al 2 de mayo de 1984), declarando a AT&T Bell Laboratories como su afiliación. [15] Después de aplicar el algoritmo para optimizar la red telefónica de AT&T, [16] se dieron cuenta de que su invento podría ser de importancia práctica. En abril de 1985, AT&T solicitó rápidamente una patente sobre el algoritmo de Karmarkar.
La patente se convirtió en más combustible para la controversia en curso sobre el tema de las patentes de software . [17] Esto dejó a muchos matemáticos incómodos, como Ronald Rivest (él mismo uno de los titulares de la patente del algoritmo RSA ), quien expresó la opinión de que la investigación procedía sobre la base de que los algoritmos deberían ser libres. Incluso antes de que se concediera realmente la patente, se argumentó que podría haber existido un estado de la técnica que fuera aplicable. [18] Los matemáticos que se especializaron en análisis numérico , incluidos Philip Gill y otros, afirmaron que el algoritmo de Karmarkar es equivalente a un método de barrera de Newton proyectado con una función de barrera logarítmica , si los parámetros se eligen adecuadamente. [19] El erudito legal Andrew Chin opina que el argumento de Gill era defectuoso, en la medida en que el método que describen no constituye un "algoritmo", ya que requiere elecciones de parámetros que no se derivan de la lógica interna del método, sino que se basan en orientación externa, esencialmente del algoritmo de Karmarkar. [20] Además, las contribuciones de Karmarkar se consideran lejos de ser obvias a la luz de todos los trabajos anteriores, incluidos Fiacco-McCormick, Gill y otros citados por Saltzman. [20] [21] [22] La patente fue debatida en el Senado de Estados Unidos [ cita requerida ] y concedida en reconocimiento de la originalidad esencial del trabajo de Karmarkar, como Patente de Estados Unidos 4.744.028 : "Métodos y aparatos para la asignación eficiente de recursos" en mayo de 1988 .
AT&T diseñó un sistema informático multiprocesador vectorial específicamente para ejecutar el algoritmo de Karmarkar, y denominó KORBX a la combinación resultante de hardware y software, [23] y comercializó este sistema a un precio de 8,9 millones de dólares. [24] [25] Su primer cliente fue el Pentágono . [26] [27]
Los opositores a las patentes de software han argumentado además que las patentes arruinaron los ciclos de interacción positiva que previamente caracterizaban la relación entre los investigadores en programación lineal y la industria, y específicamente aislaron al propio Karmarkar de la red de investigadores matemáticos en su campo. [28]
La patente en sí expiró en abril de 2006 y actualmente el algoritmo es de dominio público .
La Corte Suprema de los Estados Unidos ha sostenido que las matemáticas no pueden patentarse en Gottschalk v. Benson , [29] En ese caso, la Corte primero abordó si los algoritmos de computadora podían patentarse y sostuvo que no podían porque el sistema de patentes no protege las ideas y abstracciones similares. En Diamond v. Diehr , [30] la Corte Suprema declaró: "Una fórmula matemática como tal no recibe la protección de nuestras leyes de patentes, y este principio no puede ser eludido intentando limitar el uso de la fórmula a un entorno tecnológico particular. . [31] En Mayo Collaborative Services v. Prometheus Labs., Inc. , [32] la Corte Suprema explicó además que "simplemente implementar un principio matemático en una máquina física, a saber, una computadora, [i] no es una aplicación patentable de ese principio ". [33]
Referencias
- Adler, Ilan; Karmarkar, Narendra; Resende, Mauricio GC; Veiga, Geraldo (1989). "Una implementación del algoritmo de Karmarkar para la programación lineal". Programación matemática . 44 (1-3): 297-335. doi : 10.1007 / bf01587095 .
- Narendra Karmarkar (1984). " Un nuevo algoritmo de tiempo polinomial para la programación lineal ", Combinatorica , Vol 4 , nr. 4, pág. 373–395.
- ^ Strang, Gilbert (1 de junio de 1987). "El algoritmo de Karmarkar y su lugar en las matemáticas aplicadas". El inteligente matemático . 9 (2): 4–10. doi : 10.1007 / BF03025891 . ISSN 0343-6993 . Señor 0883185 .
- ^ http://dl.acm.org/citation.cfm?id=808695
- ^ Karmarkar, N. (1984). "Un nuevo algoritmo de tiempo polinomial para la programación lineal". Combinatorica . 4 (4): 373–395. doi : 10.1007 / BF02579150 .
- ^ Karmarkar, Narendra K. (1989). "Variantes de la serie de potencia de los algoritmos de tipo Karmarkar". Revista técnica de AT&T . 68 (3): 20–36. doi : 10.1002 / j.1538-7305.1989.tb00316.x .
- ^ Karmarkar, Narendra (1990). "Un enfoque de punto interior para problemas NP-completos. I". Desarrollos matemáticos derivados de la programación lineal (Brunswick, ME, 1988) . Matemáticas contemporáneas. 114 . Providence, RI: Sociedad Matemática Estadounidense. págs. 297-308. doi : 10.1090 / conm / 114/1097880 . Señor 1097880 .
- ^ Karmarkar, Narendra (1990). "Geometría riemanniana subyacente a métodos de punto interior para programación lineal". Desarrollos matemáticos derivados de la programación lineal (Brunswick, ME, 1988) . Matemáticas contemporáneas. 114 . Providence, RI: Sociedad Matemática Estadounidense. págs. 51–75. doi : 10.1090 / conm / 114/1097865 . Señor 1097865 .
- ^ Karmarkar NK, Lagarias, JC, Slutsman, L. y Wang, P., Variantes de la serie de potencia del algoritmo KarmarkarType, AT&T Technical Journal 68, No. 3, mayo / junio (1989).
- ^ Karmarkar, NK, Métodos de puntos interiores en optimización, Actas de la Segunda Conferencia Internacional sobre Matemáticas Industriales y Aplicadas, SIAM, págs. 160181 (1991)
- ^ Karmarkar, NK y Kamath, AP, Un enfoque continuo para derivar límites superiores en problemas de maximización cuadrática con restricciones de enteros, Avances recientes en optimización global, págs. 125140, Princeton University Press (1992).
- ^ 26. Karmarkar, NK, Thakur, SA, Un enfoque de punto interior para un problema de optimización de tensor con aplicación a límites superiores en problemas de optimización cuadrática de enteros, Actas de la segunda conferencia sobre programación de enteros y optimización combinatoria, (mayo de 1992).
- ^ 27. Kamath, A., Karmarkar, NK, un método continuo para calcular límites en problemas de optimización cuadrática de enteros, Journal of Global Optimization (1992).
- ^ Karmarkar, NK, Más allá de la convexidad: nuevas perspectivas en la optimización computacional. Springer Lecture Notes in Computer Science LNCS 6457, diciembre de 2010
- ^ Vanderbei, RJ; Lagarias, JC (1990). "Resultado de la convergencia de II Dikin para el algoritmo de escalado afín". Desarrollos matemáticos derivados de la programación lineal (Brunswick, ME, 1988) . Matemáticas contemporáneas. 114 . Providence, RI: Sociedad Matemática Estadounidense. págs. 109-119. doi : 10.1090 / conm / 114/1097868 . Señor 1097868 .
- ^ Robert J. Vanderbei ; Meketon, Marc; Freedman, Barry (1986). "Una modificación del algoritmo de programación lineal de Karmarkar" (PDF) . Algoritmica . 1 (1–4): 395–407. doi : 10.1007 / BF01840454 .
- ^ Algoritmo Karmarkar , IBM Research , consultado el 1 de junio de 2016
- ^ Sinha LP, Freedman, BA, Karmarkar, NK, Putcha, A. y Ramakrishnan KG, Planificación de redes en el extranjero, Actas del tercer simposio internacional de planificación de redes, NETWORKS '86, Tarpon Springs, Florida (junio de 1986).
- ^ Kolata, Gina (12 de marzo de 1989). "IDEAS & TENDENCIAS; A los matemáticos les preocupan las afirmaciones sobre sus recetas" . The New York Times .
- ^ Varias publicaciones de Matthew Saltzman, Universidad de Clemson
- ^ Gill, Philip E .; Murray, Walter; Saunders, Michael A .; Tomlin, JA; Wright, Margaret H. (1986). "Sobre los métodos de barrera de Newton proyectados para la programación lineal y una equivalencia al método proyectivo de Karmarkar". Programación matemática . 36 (2): 183–209. doi : 10.1007 / BF02592025 .
- ^ a b Andrew Chin (2009). "Sobre abstracción y equivalencia en la doctrina de patentes de software: una respuesta a Bessen, Meurer y Klemens" (PDF) . Revista de Derecho de la Propiedad Intelectual . 16 : 214-223.
- ^ Mark A. Paley (1995). "La patente de Karmarkar: por qué el Congreso debería" abrir la puerta "a los algoritmos como materia patentable". 22 Computadora L. Rep.7
- ^ Margaret H. Wright (2004). "La revolución del punto interior en la optimización: historia, desarrollos recientes y consecuencias duraderas" (PDF) . Boletín de la American Mathematical Society . 42 : 39–56. doi : 10.1090 / S0273-0979-04-01040-7 .
- ^ Marc S. Meketon; YC Cheng; DJ Houck; JMLiu; L. Slutsman; Robert J. Vanderbei ; P. Wang (1989). "El sistema AT&T KORBX". Revista técnica de AT&T . 68 (3): 7-19. doi : 10.1002 / j.1538-7305.1989.tb00315.x .
- ^ Lowenstein, Roger (15 de agosto de 1988). "AT&T comercializa un solucionador de problemas, basado en el hallazgo de un genio de las matemáticas, por $ 8,9 millones" (PDF) . Wall Street Journal .
- ^ Markoff, John (13 de agosto de 1988). "Big AT&T. Computadora para complejidades" .
- ^ "Military es el primer cliente anunciado de AT&T Software" . AP Noticias . Consultado el 11 de junio de 2019 .
- ^ Kennington, JL (1989). "Uso de KORBX para aplicaciones de transporte aéreo militar". Actas de la 28ª Conferencia IEEE sobre Decisión y Control . págs. 1603–1605. doi : 10.1109 / CDC.1989.70419 .
- ^ "今 野 浩: カ ー マ ー カ ー 特許 と ソ フ ト ウ ェ ア - 数学 は 特許 に な る か (Konno Hiroshi: La patente y el software de Kamarkar - ¿Las matemáticas se han vuelto patentables?)" . FFII . Archivado desde el original el 27 de junio de 2008 . Consultado el 27 de junio de 2008 .
- ^ 409 Estados Unidos 63 (1972). El caso se refería a un algoritmo para convertir números decimales codificados en binario en binario puro.
- ^ 450 Estados Unidos 175 (1981).
- ↑ 450 US en 191. Ver también Parker v. Flook , 437 US 584, 585 (1978) ("el descubrimiento de una fórmula matemática nueva y útil no puede ser patentado").
- ^ 566 US __, 132 S. Ct. 1289 (2012).
- ^ Acuerdo Alice Corp. contra CLS Bank Int'l , 573 US __, 134 S. Ct. 2347 (2014).