Kokonaislukuisia lineaarisia ohjelmointiongelmia syntyy, kun yritetään ratkaista lineaarisia järjestelmiä ja määritetään, että kaikkien tuntemattomien muuttujien on oltava kokonaislukuja tai kokonaislukuja. Lineaariset järjestelmät ovat yhtälöryhmiä, jotka kuvaavat tilannetta, johon ohjelmoija yrittää löytää ratkaisun. Ne koostuvat yleensä yhdestä yhtälöstä, joka on maksimoitava tai minimoitava, ja yhdestä tai useammasta rajoittavasta yhtälöstä, joka asettaa rajoituksia tuntemattomille muuttujille. Jotta järjestelmä olisi lineaarinen, jokaisen rajoituksen on oltava lineaarinen yhtälö; eli se ei saa sisältää tuntemattoman muuttujan esiintymiä, joiden eksponentit ovat suurempia kuin yksi.
Tavalliset lineaariset järjestelmät voidaan ratkaista helposti tietokoneen avulla. Ohjelma voi tunnistaa ratkaisun etsimällä johdannaisen ja asettamalla sen nollaksi. Se voi sitten tarkistaa, että piste on maksimi tai minimi, tarkistamalla sen välittömän naapuruston toiminnossa. Niin kauan kuin johdannainen on määritelty toiminnon jokaisessa kohdassa, tietokoneella on vain rajoitettu määrä mahdollisia tarkistettavia ratkaisuja.
Lineaarisesta ohjelmoinnista tulee kokonaislukuinen lineaarinen ohjelmointi, kun siihen lisätään kokonaislukurajoitus. Tämä tarkoittaa, että ongelma pysyy samana, mutta vastauksen on oltava kokonaislukuarvoja tuntemattomille arvoille: niiden on oltava kokonaislukuja. Joskus tämä tarkoittaa, että ratkaisu ei ole optimaalinen verrattuna tapaukseen, jossa jakeet ovat sallittuja; se heijastaa kuitenkin todellista maailmaa, jossa esineet tulevat usein erillisiksi, jakamattomiksi yksiköiksi. Tämä tekee kokonaislukuisesta lineaarisesta ohjelmoinnista tärkeää liiketoimintasovelluksille, koska yritykset haluavat maksimoida voitot mahdollisimman paljon, mutta eivät voi päättää myydä murto -osaa tuotteesta.
Kun kokonaislukurajoitukset on otettu käyttöön, lineaarisen järjestelmän ratkaiseminen on NP-täydellinen. Tämä tarkoittaa, että aika, joka tarvitaan tietokoneelle järjestelmän ratkaisemiseksi, on määrittelemätön. Kokonaislukurajoituksilla tietokoneet eivät voi käyttää johdannaisen työkalua, koska ei ole takeita siitä, että johdannaisen nollapiste laskee kokonaislukuun. Ratkaisu on kokonaisluku, jolla on suurin tai pienin arvo kaikista kokonaisluvuista, joten tietokoneen on tarkistettava ne kaikki – prosessi, joka voi kestää äärettömän paljon aikaa.
Ohjelmoijat ovat kehittäneet heuristiikkaa tai ongelmanratkaisumenetelmiä käsitelläkseen näiden ongelmien monimutkaisuutta. Yksi tapa ratkaista kokonaislukuisia lineaarisia ohjelmointitehtäviä on haara- ja sidottu algoritmi, jossa tietokone ratkaisee sarjan alkuperäiseen liittyviä ongelmia rajatakseen käytettävissä olevan arvoalueen yhteen ratkaisuun. Monimutkaisissa ongelmissa tämä voi kuitenkin kestää kauan.