Die Lineare Programmierung (LP) ist ein Teilgebiet der Optimierung, welches sich mit der Lösung von Optimierungsproblemen mit linearen Restriktionen und einer linearen Zielfunktion beschäftigt.
Der bekannteste Algorithmus zur Lösung von LP ist der Simplex-Algorithmus. Dieser liefert für die meisten praktisch relevanten Probleme exakte Lösungen in kurzer Rechenzeit. Theoretisch hat der Simplex-Algorithmus jedoch den Nachteil, dass die Laufzeit exponentiell mit der Problemgröße wachsen kann. Von daher wurden in den achtziger Jahren einige Algorithmen entwickelt, deren Laufzeit polynomial beschränkt ist. Diese haben sich jedoch in der Praxis nicht durchgesetzt, während einige Barrier-Methoden sich auch als praktisch effizient herausgestellt haben.
