Täisarvprogrammeerimine

Täisarvprogrammeerimine (Integer Programming) on matemaatilise optimeerimise haru, mis tegeleb piirangutega optimaalse lahenduse leidmisega, kus kõik või osa muutujatest peavad olema täisarvud. See erineb tavalisest lineaarsest programmeerimisest, kus muutujad võivad olla mis tahes reaalarvud. Täisarvude nõue muudab probleemi oluliselt keerulisemaks, kuna see muudab lahendusruumi diskreetseks.

Probleemid, kus muutujad peavad olema täisarvud, tekivad sageli loomulikes olukordades. Näiteks, kui otsustatakse, kas investeerida mingisse projekti või mitte, on tegemist binaarse muutujaga (0 või 1). Samuti, kui loendatakse objekte, nagu näiteks toodetud autode arv, peavad muutujad olema mittenegatiivsed täisarvud.

Täisarvprogrammeerimise probleemid on üldjuhul NP-raskusastmega, mis tähendab, et nende lahendamiseks sobivaid tõhusaid algoritme, mis töötaksid kõigi sisendite puhul eksponentsiaalsest ajast sõltumatult, ei ole tuntud. Siiski on välja töötatud mitmeid meetodeid nende probleemide lahendamiseks. Levinud tehnikate hulka kuuluvad haru ja piir (branch and bound), lõike tasapinna meetodid (cutting plane methods) ja heuristikad.

Täisarvprogrammeerimist kasutatakse laialdaselt erinevates valdkondades, sealhulgas logistikas (nt marsruutide optimeerimine), tootmises (nt ressursiplaneerimine), rahanduses (nt portfelli optimeerimine) ja tehisintellektis. Selle võimsus seisneb reaalse maailma diskreetsete otsuste modelleerimise ja optimeerimise võimaldamises.