En muchos problemas reales no siempre es posible que las variables puedan tomar valores continuos. Así, existen problemas en los cuales las variables solo pueden tomar valores enteros, como por ejemplo cuantos viajes diarios debe realizar cada camión de una determinada empresa, si sus capacidades son distintas, para cubrir una determinada demanda con coste mínimo, en este caso si cada variable representa el número de viajes que debe realizar cada camión, es evidente que solo podrán tomar valores enteros. Incluso existen determinados problemas de decisión en los cuales las variables solo pueden tomar valores uno o cero, por ejemplo si se instala un almacén en determinado lugar la variable tomara valor uno y si no se instala valor cero.

Así pues, los problemas de programación entera, aparecen cuando en los problemas lineales estudiados hasta ahora todas o algunas de las variables solo pueden tomar valores enteros, es decir, se abandona la hipótesis de perfecta divisibilidad de las variables. En un sentido estricto todo problema de programación entera tendría que ser definido como un problema de programación lineal, dado que la función objetivo del problema estará definida únicamente para valores discretos de las variables. En programación entera, se dice que un problema es de programación lineal entera (PLE) si el problema resultante es lineal.