Težave z linearnim celoštevilskim programiranjem se pojavijo, ko poskušamo rešiti linearne sisteme, medtem ko določamo, da morajo biti vse neznane spremenljivke cela ali cela števila. Linearni sistemi so nizi enačb, ki opisujejo situacijo, za katero poskuša programer najti rešitev. Običajno so sestavljeni iz ene enačbe, ki jo je treba povečati ali zmanjšati, in ene ali več omejevalnih enačb, ki omejujejo neznane spremenljivke. Da je sistem linearen, mora biti vsaka omejitev linearna enačba; to pomeni, da ne sme vsebovati nobenih primerkov neznane spremenljivke z eksponenti, večjimi od ena.
Redne linearne sisteme je mogoče enostavno rešiti z uporabo računalnika. Program lahko identificira rešitev tako, da najde izpeljanko in jo nastavi na nič. Nato lahko preveri, ali je točka maksimum ali minimum, tako da preveri njeno neposredno soseščino na funkciji. Dokler je izpeljanka definirana na vsaki točki vzdolž funkcije, ima računalnik le omejeno število možnih rešitev za preverjanje.
Linearno programiranje postane celoštevilsko linearno programiranje z dodatkom omejitve celega števila. To pomeni, da problem ostaja enak, vendar mora odgovor vsebovati cele vrednosti za neznane vrednosti: to morajo biti cela števila. Včasih to pomeni, da bo rešitev podoptimalna v primerjavi s primerom, v katerem so ulomki dovoljeni; vendar odseva resnični svet, v katerem so predmeti pogosto v diskretnih, nedeljivih enotah. Zaradi tega je celoštevilsko linearno programiranje pomembno za poslovne aplikacije, saj želijo podjetja čim bolj povečati dobiček, vendar se ne morejo odločiti za prodajo delčka izdelka.
Ko so celoštevilske omejitve na mestu, je problem reševanja linearnega sistema NP-popoln. To pomeni, da je čas, ki je potreben, da računalnik reši sistem, nedoločen. Z omejitvami celih številk računalniki ne morejo uporabljati orodja izpeljanke, ker ni nobenega zagotovila, da bo ničelna točka izpeljanke padla na celo število. Rešitev bo celo število z najvišjo ali najnižjo vrednostjo od vseh celih števil, zato bi jih moral računalnik vse preveriti – proces, ki bi lahko trajal neskončno dolgo.
Programerji so razvili hevristiko ali metode reševanja problemov za reševanje kompleksnosti teh problemov. Eden od načinov reševanja problemov celoštevilskega linearnega programiranja je algoritem veje in vezave, pri katerem računalnik rešuje vrsto problemov, povezanih z izvirnim, da zoži razpoložljivo območje vrednosti na eno rešitev. Pri kompleksnih težavah pa to lahko traja dolgo.