Worldlex Wiki algorithme de Karmarkar, introduit par Narendra Karmarkar en 1984, permet de résoudre les problèmes de programmation linéaire . Il fut le premier algorithme relativement efficace à résoudre ces problèmes en temps polynomial . La méthode de l'ellipsoïde , bien que également polynomiale, s'est avérée inefficace en pratique.
En désignant par le nombre de variables, m le nombre de contraintes d'inégalité et le nombre de bits d'entrée de l'algorithme, l'algorithme de Karmarkar nécessite des opérations sur des nombres à n chiffres, contre autant pour l'algorithme de l'ellipsoïde. Dans les problèmes « carrés », lorsque m est en O( n ), l'algorithme de Karmarkar nécessite des opérations sur des nombres à n chiffres, contre autant pour l'algorithme de l'ellipsoïde. La complexité temporelle de l'algorithme de Karmarkar est donc de O(n²) en utilisant la multiplication basée sur la FFT (voir la notation grand O ).
L'algorithme de Karmarkar appartient à la classe des méthodes de points intérieurs : l'estimation courante de la solution ne suit pas la frontière de l' ensemble admissible comme dans la méthode du simplexe , mais se déplace à l'intérieur de la région admissible, améliorant l'approximation de la solution optimale d'une fraction définie à chaque itération et convergeant vers une solution optimale avec des données rationnelles.
maximiser la mise à l'échelle affine , une variante de l'algorithme de Karmarkar utilisant des transformations affines là où Karmarkar employait des transformations projectives . Ils se sont rendu compte quatre ans plus tard qu'ils avaient redécouvert un algorithme publié par le mathématicien soviétique Il.I. Dikin en 1967. La méthode de mise à l'échelle affine peut être décrite succinctement comme suit. Bien qu'applicable aux problèmes de petite taille, ce n'est pas un algorithme polynomial.Entrée : A, b, c, , critère d'arrêt , γ .faire tant que le critère d'arrêt n'est pas satisfait , si alors retourner non borné fin si fin faire- " ← " désigne une affectation . Par exemple, " largest ← item " signifie que la valeur de largest change pour la valeur de item .
- La fonction « return » termine l'algorithme et renvoie la valeur suivante.
Exemple
Considérons le programme linéaire suivant : il comporte 2 variables et 11 contraintes associées à différentes valeurs de . La figure illustre chaque itération de l'algorithme par des points rouges. Les contraintes sont représentées par des lignes bleues.
Controverse de brevets
Au moment où il inventa l'algorithme, Karmarkar travaillait chez IBM comme chercheur postdoctoral au laboratoire de recherche IBM de San Jose, en Californie. Le 11 août 1983, il donna un séminaire à l'université de Stanford pour expliquer l'algorithme, son affiliation étant encore mentionnée comme étant IBM. À l'automne 1983, Karmarkar commença à travailler chez AT&T et soumit son article au symposium ACM sur la théorie du calcul (STOC) de 1984 (qui s'est tenu du 30 avril au 2 mai 1984), indiquant AT&T Bell Laboratories comme son affiliation. Après avoir appliqué l'algorithme à l'optimisation du réseau téléphonique d'AT&T, l'entreprise réalisa que son invention pouvait avoir une importance pratique. En avril 1985, AT&T déposa rapidement une demande de brevet pour son algorithme.
Le brevet a alimenté la controverse persistante sur la question des brevets logiciels . Cette situation a inquiété de nombreux mathématiciens, comme Ronald Rivest (lui-même titulaire du brevet de l' algorithme RSA ), qui estimait que la recherche devait reposer sur le principe de la liberté des algorithmes. Avant même la délivrance du brevet, l'existence d' antériorités applicables avait déjà été soulevée. Des mathématiciens spécialisés en analyse numérique , dont fonction barrière logarithmique , moyennant un choix judicieux des paramètres. Le juriste Andrew Chin considère que l'argument de Gill était erroné, dans la mesure où la méthode décrite ne constitue pas un « algorithme », puisqu'elle requiert des choix de paramètres qui ne découlent pas de la logique interne de la méthode, mais s'appuient sur des indications externes, essentiellement issues de l'algorithme de Karmarkar. De plus, les contributions de Karmarkar sont loin d'être évidentes au regard de tous les travaux antérieurs, notamment ceux de Fiacco-McCormick, Gill et d'autres cités par Saltzman. Le brevet a été accordé en reconnaissance de l'originalité essentielle des travaux de Karmarkar, sous vectoriel multiprocesseur spécifiquement destiné à exécuter l'algorithme de Karmarkar, baptisant la combinaison matérielle et logicielle résultante KORBX , et l'a commercialisé au prix de 8,9 millions de dollars américains . Son premier client fut le Pentagone .
Les opposants aux brevets logiciels ont également fait valoir que ces brevets avaient ruiné les cycles d'interaction positifs qui caractérisaient auparavant la relation entre les chercheurs en programmation linéaire et l'industrie, et qu'ils avaient notamment isolé Karmarkar lui-même du réseau de chercheurs en mathématiques de son domaine.
Le brevet lui-même a expiré en avril 2006, et l'algorithme est actuellement dans le domaine public .
La Cour suprême des États-Unis a statué que les mathématiques ne peuvent être brevetées dans l'affaire c. Benson [ Dans cette affaire, la Cour a d'abord examiné la possibilité de breveter les algorithmes informatiques et a conclu que non, car le système des brevets ne protège pas les idées et les abstractions similaires. Dans l'affaire Diamond c. Diehr [ la Cour suprême a déclaré : « Une formule mathématique en tant que telle ne bénéficie pas de la protection de notre droit des brevets, et ce principe ne saurait être contourné en tentant de limiter l'utilisation de la formule à un environnement technologique particulier. » Dans l' affaire Mayo Collaborative Services c. Prometheus Labs., Inc. [ la Cour suprême a précisé que « la simple mise en œuvre d'un principe mathématique sur une machine physique, à savoir un ordinateur, ne constitue pas une application brevetable de ce principe. »
Applications
L'algorithme de Karmarkar a été utilisé par l'armée américaine pour la planification logistique pendant la guerre du Golfe .
- Adler, Ilan ; Karmarkar, Narendra; Resende, Mauricio GC ; Veiga, Geraldo (1989). « Implémentation de l’algorithme de Karmarkar pour la programmation linéaire ». Mathematical Programming . 44 ( 1– 3) : 297– 335. doi : 10.1007/bf01587095 . S2CID 12851754 .
- Narendra Karmarkar (1984). " Un nouvel algorithme en temps polynomial pour la programmation linéaire ", Combinatorica , Vol 4 , n° 4, p. 373 – 395.