Binäärioptimointi

Binäärioptimointi, tunnettu myös nimellä binäärinen optimointi tai dikotominen optimointi, on optimointialgoritmien ala, joka käsittelee ongelmia, joissa päätösmuuttujat voivat saada vain kaksi arvoa, tyypillisesti 0 ja 1. Tämä tarkoittaa, että jokainen muuttuja edustaa kyllä/ei-tyyppistä valintaa tai kahden vaihtoehdon välistä eroa. Vaikka binäärioptimointiongelmat voivat vaikuttaa yksinkertaisilta, ne muodostavat perustan monille monimutkaisille ja käytännönläheisille ongelmille.

Binäärioptimoinnin ongelmat ilmestyvät monilla eri aloilla, kuten logistiikassa (esim. reittien optimointi, varastonhallinta), resurssien allokoinnissa, aikataulutuksessa ja portfolion valinnassa. Esimerkiksi, jos yritys harkitsee useiden uusien tehtaiden avaamista, jokaisen potentiaalisen tehtaan avaamispäätös voidaan mallintaa binäärisenä muuttujana: 1 jos tehdas avataan, 0 jos ei. Tavoitteena on yleensä maksimoida voitto tai minimoida kustannukset useiden rajoitusten, kuten budjetin tai resurssien saatavuuden, puitteissa.

Binäärioptimointiongelmia voidaan ratkaista erilaisilla algoritmeilla. Yksinkertaisimmissa tapauksissa, joissa on vain muutama muuttuja, voidaan käyttää brute force -menetelmää, jossa kaikki mahdolliset kombinaatiot käydään läpi. Monimutkaisemmissa ongelmissa, joissa muuttujien määrä on suuri, tarvitaan tehokkaampia menetelmiä. Näitä ovat muun muassa branch and bound -algoritmit, branch and cut -algoritmit sekä erilaiset heuristiikat ja metaheuristiikat, kuten geneettiset algoritmit tai simuloidut hehkutukset. Monet näistä menetelmistä perustuvat lineaarisesti tai epälineaarisesti konvekseihin optimointimenetelmiin, jotka on muokattu käsittelemään binäärisiä rajoituksia.