Problemi cjelobrojnog linearnog programiranja nastaju kada se pokušava riješiti linearni sustav uz specificiranje da sve nepoznate varijable moraju biti cijeli brojevi ili cijeli brojevi. Linearni sustavi su skupovi jednadžbi koje opisuju situaciju za koju programer pokušava pronaći rješenje. Obično se sastoje od jedne jednadžbe koja se mora maksimizirati ili minimizirati i jedne ili više ograničavajućih jednadžbi koje postavljaju ograničenja na nepoznate varijable. Da bi sustav bio linearan, svako ograničenje mora biti linearna jednadžba; to jest, ne smije sadržavati instance nepoznate varijable s eksponentima većim od jedan.
Redovni linearni sustavi mogu se lako riješiti pomoću računala. Program može identificirati rješenje tako da pronađe derivaciju i postavi je jednakom nuli. Zatim može provjeriti je li točka maksimum ili minimum provjeravanjem njenog neposrednog susjedstva na funkciji. Sve dok je derivacija definirana u svakoj točki duž funkcije, računalo ima samo ograničen broj mogućih rješenja za provjeru.
Linearno programiranje postaje cjelobrojno linearno programiranje uz dodatak cjelobrojnog ograničenja. To znači da problem ostaje isti, ali odgovor se mora sastojati od cjelobrojnih vrijednosti za nepoznate vrijednosti: moraju biti cijeli brojevi. Ponekad to znači da će rješenje biti suboptimalno u usporedbi sa slučajem u kojem su razlomci dopušteni; međutim, on odražava stvarni svijet, u kojem predmeti često dolaze u diskretnim, nedjeljivim jedinicama. To čini cjelobrojno linearno programiranje važnim za poslovne aplikacije, budući da tvrtke žele maksimizirati profit što je više moguće, ali ne mogu odlučiti prodati djelić proizvoda.
Jednom kada su cjelobrojna ograničenja postavljena, problem rješavanja linearnog sustava je NP-potpun. To znači da je vrijeme koje je potrebno računalu da riješi sustav neodređeno. Uz cjelobrojna ograničenja, računala ne mogu koristiti alat derivacije jer nema jamstva da će nulta točka derivacije pasti na cijeli broj. Rješenje će biti cijeli broj s najvećom ili najnižom vrijednošću od svih cijelih brojeva, tako da bi ih računalo moralo sve provjeriti – proces koji bi mogao potrajati beskonačno vrijeme.
Programeri su razvili heuristiku, ili metode rješavanja problema, kako bi se nosili sa složenošću ovih problema. Jedna od metoda rješavanja problema cjelobrojnog linearnog programiranja je algoritam grananja i ograničenja, u kojem računalo rješava niz problema povezanih s izvornim kako bi suzilo raspoloživi raspon vrijednosti na jedno rješenje. Međutim, za složene probleme to može potrajati.