binäärioptimointiongelmat

Binäärioptimointiongelmat ovat optimointiongelmia, joissa kaikki päätösmuuttujat voivat saada vain kaksi arvoa, tyypillisesti 0 tai 1. Nämä ongelmat ovat yleisiä monilla aloilla, kuten operaatiotutkimuksessa, tietojenkäsittelytieteessä ja taloustieteessä.

Tällaisten ongelmien yleinen muoto on löytää vektori x, joka minimoi tai maksimoi objektiivifunktion f(x), samalla kun tietyt rajoitusehdot g(x) täyttyvät. Tässä tapauksessa jokainen x_i-komponentti voi olla vain 0 tai 1.

Binäärioptimointiongelmat voivat olla laskennallisesti erittäin vaikeita. Vaikka muuttujien määrä olisi pieni, mahdollisten ratkaisujen lukumäärä kasvaa eksponentiaalisesti (2^n, missä n on muuttujien määrä). Tämä tekee täydellisen ratkaisun löytämisestä brute force -menetelmällä mahdotonta suurille ongelmille.

Näiden ongelmien ratkaisemiseksi on kehitetty useita algoritmeja. Näitä ovat esimerkiksi haaramis- ja rajoitusmenetelmät (branch and bound), heuristiset menetelmät kuten geneettiset algoritmit ja simuloidut hehkutukset, sekä lineaarisen ja kokonaislukuoptimoinnin tekniikat. Monet käytännön ongelmat, kuten reppurepputehtävä, käänteinen kauppamatkustajan ongelma ja resurssienallokointi, voidaan muotoilla binäärioptimointiongelmiksi.