A programação linear inteira (0-1) é aquela em que as variáveis de decisão (x e y) podem assumir somente os valores 0 e 1. Considere que a função objetivo também pode assumir somente 0 ou 1.

Desta forma, para x igual a zero e para x igual a 1, todas as possibilidades de valores que a variável de decisão y deve assumir, são, respectivamente,