La programmazione lineare (LP) è una branca dell'ottimizzazione che si occupa della soluzione di problemi di ottimizzazione con restrizioni lineari e una funzione obiettivo lineare.
L'algoritmo più noto per la risoluzione di LP è l'algoritmo simplex. Questo algoritmo fornisce soluzioni esatte per la maggior parte dei problemi rilevanti dal punto di vista pratico in un breve tempo di calcolo. Dal punto di vista teorico, tuttavia, l'algoritmo simplex ha lo svantaggio che il tempo di esecuzione può crescere esponenzialmente con la dimensione del problema. Per questo motivo, negli anni '80 sono stati sviluppati alcuni algoritmi il cui tempo di esecuzione è polinomialmente limitato. Tuttavia, questi non si sono affermati nella pratica, mentre alcuni metodi a barriera si sono dimostrati efficienti dal punto di vista pratico.