Problemele de programare liniară cu numere întregi apar atunci când se încearcă rezolvarea sistemelor liniare în timp ce se specifică faptul că toate variabilele necunoscute trebuie să fie numere întregi sau numere întregi. Sistemele liniare sunt seturi de ecuații care descriu o situație pentru care programatorul încearcă să găsească o soluție. Ele constau de obicei dintr-o ecuație care trebuie maximizată sau minimizată și una sau mai multe ecuații restrictive care pun limite pentru variabilele necunoscute. Pentru ca sistemul să fie liniar, fiecare restricție trebuie să fie o ecuație liniară; adică nu trebuie să conțină instanțe ale variabilei necunoscute cu exponenți mai mari de unu.
Sistemele liniare obișnuite pot fi rezolvate cu ușurință folosind un computer. Programul poate identifica o soluție prin găsirea derivatei și setând-o egală cu zero. Apoi poate verifica dacă punctul este maxim sau minim verificând vecinătatea imediată a funcției. Atâta timp cât derivata este definită în fiecare punct de-a lungul funcției, computerul are doar un număr limitat de soluții posibile de verificat.
Programarea liniară devine programare liniară întregă cu adăugarea restricției întregi. Aceasta înseamnă că problema rămâne aceeași, dar răspunsul trebuie să fie format din valori întregi pentru valorile necunoscute: acestea trebuie să fie numere întregi. Uneori, aceasta înseamnă că soluția va fi suboptimă în comparație cu cazul în care sunt permise fracții; reflectă, totuși, lumea reală, în care articolele vin adesea în unități discrete, indivizibile. Acest lucru face ca programarea liniară întregă să fie importantă pentru aplicațiile de afaceri, deoarece firmele doresc să maximizeze profiturile cât mai mult posibil, dar nu pot alege să vândă o parte dintr-un produs.
Odată ce restricțiile întregi sunt aplicate, problema rezolvării sistemului liniar este NP-complet. Aceasta înseamnă că timpul necesar pentru ca un computer să rezolve sistemul este nedeterminat. Cu restricții de numere întregi, computerele nu pot folosi instrumentul derivatei deoarece nu există nicio garanție că punctul zero al derivatei va cădea pe un număr întreg. Soluția va fi numărul întreg cu cea mai mare sau cea mai mică valoare dintre toate numerele întregi, așa că computerul ar trebui să le verifice pe toate – un proces care ar putea dura o perioadă infinită de timp.
Programatorii au dezvoltat euristici, sau metode de rezolvare a problemelor, pentru a face față complexității acestor probleme. O metodă de rezolvare a problemelor de programare liniară cu numere întregi este algoritmul ramificat și legat, în care computerul rezolvă o serie de probleme legate de cea originală pentru a restrânge intervalul disponibil de valori la o singură soluție. Cu toate acestea, pentru probleme complexe, acest lucru poate dura mult timp.