Algoritmo de Karmakar

https://commons.wikimedia.org/wiki/File:Narendra_Karmarkar.jpg

Ideado en su forma arquetípica por el matemático indio Narendra Karmakar, el algoritmo que lleva su nombre ofrece un procedimiento para la resolución de problemas de programación lineal. Cuando en estos problemas se maneja multitud de variables y condiciones de restricción, es común recurrir al auxilio de computadoras para su resolución.

El método simplex, ideado por el estadounidense George Dantzig, supuso la aparición de un algoritmo que sirvió de base a un programa informático, gracias al cual se redujo de forma considerable el tiempo de resolución de los problemas. No obstante sus ventajas, el método simplex es de naturaleza exponencial, lo que implica que el tiempo de trabajo que precisa crece exponencialmente, según el tamaño del problema que se ha de resolver. Por ello, muchos matemáticos acometieron la tarea de diseñar algoritmos de tipo polinómico que manejarían un crecimiento del tiempo de resolución potencial, mucho más asequible que el exponencial.

Un primer intento en esa dirección apareció en 1979 y se debió al ruso I. G. Kachian, quien presentó un método de tipo polinómico, llamado elipsoidal, con el que pretendía dar una respuesta al problema de la reducción del tiempo de resolución. Este método, que despertó amplias expectativas, demostró escasa eficacia en la práctica excepto para algunos problemas concretos.

En 1984, Narendra Karmarkar, en los AT&T Bell Laboratories, diseñó otra clase de algoritmo polinómico en el que el movimiento para optimizar la función objetivo no se hacía a lo largo de aristas del poliedro determinado por las restricciones, tal como se actuaba en el método simplex, sino desplazándose por el interior del mismo. Acogido con cierto escepticismo, dada la experiencia anterior del método elipsoidal, pronto se comprobó su eficacia cuando se aplicó al problema de construir conexiones telefónicas.

Así, en la década de 1980, los Laboratorios Bell acometieron la tarea de diseñar una red de conexiones telefónicas entre ciudades estadounidenses tal que las llamadas interurbanas pasaran por ciudades intermedias. El problema manejaba unas 800.000 variables y fue resuelto en unas diez horas mediante el algoritmo de Karmakar incorporado a un programa informático. Cálculos prudentes cifraban en semanas el tiempo que hubiera sido necesario por aplicación del método simplex.

A pesar de todo, el método simplex se sigue explicando en las aulas matemáticas y se aplica en problemas de complejidad no excesivamente elevada, campo en el que da muy buenos resultados.