yhdistelmäoptimointiongelmissa

Yhdistelmäoptimointiongelmissa tarkastellaan joukkoa valintoja, joiden perusteella pyritään löytämään paras mahdollinen ratkaisu annetun kriteeristön mukaisesti. Nämä ongelmat ilmenevät monilla eri aloilla, kuten logistiikassa, resurssien allokoinnissa ja aikataulutuksessa. Tavoitteena on tyypillisesti maksimoida tai minimoida jokin objektiivinen funktio, esimerkiksi voitto tai kustannus, samalla kun noudatetaan tiettyjä rajoitteita.

Yhdistelmäoptimointiongelmat voivat olla luonteeltaan hyvin erilaisia. Esimerkiksi matkustavan kauppiaan ongelma pyrkii löytämään lyhimmän reitin, joka käy läpi kaikki ennalta määrätyt kaupungit ja palaa takaisin lähtöpisteeseen. Toinen esimerkki on repputehtävä, jossa pyritään valitsemaan joukosta esineitä ne, joiden yhteispaino ei ylitä tiettyä rajaa ja joiden yhteisarvo on mahdollisimman suuri.

Näiden ongelmien ratkaiseminen voi olla laskennallisesti erittäin vaativaa, erityisesti kun vaihtoehtojen määrä kasvaa. Jotkin ongelmat ovat NP-vaikeita, mikä tarkoittaa, että tunnettujen tehokkaiden ratkaisualgoritmien puuttumisen vuoksi niiden ratkaiseminen voi kestää eksponentiaalisen ajan ongelman koon funktiona. Tämän vuoksi käytetään usein heuristiikkoja tai likimääräismenetelmiä löytämään riittävän hyviä ratkaisuja kohtuullisessa ajassa.