Kokonaislukuoptimointimenetelmät

Kokonaislukuoptimointimenetelmät ovat matemaattisia tekniikoita, joita käytetään optimointiongelmien ratkaisemiseen, kun ratkaisun muuttujien on oltava kokonaislukuja. Toisin kuin jatkuvassa optimoinnissa, jossa muuttujat voivat saada minkä tahansa reaaliarvon, kokonaislukuoptimoinnissa vaaditaan diskreettejä arvoja. Tämä rajoitus tekee ongelmista yleensä huomattavasti vaikeampia ratkaista.

Yksi yleisimmistä kokonaislukuoptimointimenetelmistä on haarautumis- ja raja-menetelmä (branch and bound). Tämä algoritmi toimii jakamalla alkuperäisen ongelman pienempiin osaprobleemiin ja ratkaisemalla niitä käyttäen hyväksi tilannekohtaista tietoa. Toinen tärkeä menetelmä on leikkaustasomenetelmä (cutting plane method), joka lisää ongelmaan uusia rajoituksia (leikkaustasoja) asteittain, kunnes saavutetaan kokonaislukuratkaisu.

Polyhedraalinen approksimaatio on myös keskeinen käsite. Monet kokonaislukuoptimointiongelmat voidaan muotoilla lineaarisiksi kokonaislukuohjelmiksi, joiden ratkaiseminen liittyy polyedrin kärkien löytämiseen. Tähän liittyvät menetelmät perustuvat usein polyedrin konveksin verhouksen tutkimiseen.

Kokonaislukuoptimointia käytetään laajalti monilla aloilla, kuten operaatiotutkimuksessa, logistiikassa, taloustieteessä ja tietojenkäsittelytieteessä. Tyypillisiä sovelluksia ovat resurssien allokointi, aikataulutusongelmat, reititysongelmat ja portfolion optimointi. Koska kokonaislukuoptimointiongelmat voivat olla NP-vaikeita, käytännön sovelluksissa hyödynnetään usein heuristisia menetelmiä tai kehittyneitä algoritmeja, jotka löytävät hyvän, joskaan eivät välttämättä optimaalisen, ratkaisun kohtuullisessa ajassa.