Sveikųjų skaičių linijinio programavimo problemos kyla bandant išspręsti tiesines sistemas, kartu nurodant, kad visi nežinomi kintamieji turi būti sveikieji arba sveikieji skaičiai. Tiesinės sistemos yra lygčių rinkiniai, apibūdinantys situaciją, kuriai programuotojas bando rasti sprendimą. Paprastai juos sudaro viena lygtis, kuri turi būti padidinta arba sumažinta, ir viena ar daugiau ribojančių lygčių, kurios apriboja nežinomus kintamuosius. Kad sistema būtų tiesinė, kiekvienas apribojimas turi būti tiesinė lygtis; tai yra, jame neturi būti nežinomo kintamojo, kurio rodikliai yra didesni nei vienas, atvejų.
Įprastas tiesines sistemas galima nesunkiai išspręsti kompiuteriu. Programa gali identifikuoti sprendimą radusi išvestinę ir nustatydama ją lygią nuliui. Tada jis gali patikrinti, ar taškas yra maksimalus ar minimumas, patikrindamas jo artimiausią funkciją. Kol išvestinė apibrėžiama kiekviename funkcijos taške, kompiuteris gali patikrinti tik ribotą skaičių galimų sprendimų.
Linijinis programavimas tampa sveikųjų skaičių linijiniu programavimu, pridedant sveikųjų skaičių apribojimą. Tai reiškia, kad problema išlieka ta pati, tačiau atsakymas turi būti sudarytas iš sveikųjų skaičių reikšmės nežinomoms reikšmėms: jos turi būti sveikieji skaičiai. Kartais tai reiškia, kad sprendimas bus neoptimalus, palyginti su tuo atveju, kai leidžiamos trupmenos; tačiau tai atspindi realų pasaulį, kuriame daiktai dažnai būna atskiri, nedalomi vienetai. Dėl to sveikųjų skaičių linijinis programavimas yra svarbus verslo programoms, nes įmonės nori maksimaliai padidinti pelną, bet negali pasirinkti parduoti dalies produkto.
Įvedus sveikųjų skaičių apribojimus, tiesinės sistemos sprendimo problema yra NP baigta. Tai reiškia, kad laikas, reikalingas kompiuteriui išspręsti sistemą, yra neapibrėžtas. Taikant sveikųjų skaičių apribojimus, kompiuteriai negali naudoti išvestinės priemonės, nes nėra garantijos, kad išvestinės nulinis taškas pateks į sveikąjį skaičių. Sprendimas bus sveikasis skaičius, kurio reikšmė didžiausia arba mažiausia iš visų sveikųjų skaičių, todėl kompiuteris turės juos visus patikrinti – procesas gali užtrukti be galo daug.
Programuotojai sukūrė euristiką arba problemų sprendimo metodus, kad susidorotų su šių problemų sudėtingumu. Vienas iš sveikųjų skaičių tiesinio programavimo problemų sprendimo būdų yra šakinis ir susietas algoritmas, kai kompiuteris išsprendžia daugybę problemų, susijusių su pradiniu, kad susiaurintų turimą reikšmių diapazoną iki vieno sprendimo. Tačiau sudėtingų problemų atveju tai gali užtrukti ilgai.