Lineaarinen kokonaislukuoptimointi haaraudu ja rajoita -algoritmilla
Kaatrasalo, Valtteri (2019)
2019
Tekniikan ja luonnontieteiden TkK tutkinto-ohjelma
Tekniikan ja luonnontieteiden tiedekunta - Faculty of Engineering and Natural Sciences
This publication is copyrighted. Only for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2019-08-26
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-201908222990
https://urn.fi/URN:NBN:fi:tuni-201908222990
Tiivistelmä
Matemaattisessa optimoinnissa on tavoitteena löytää ongelmaan paras ratkaisu sallittujen ratkaisujen joukosta. Käytännössä tämä tehdään minimoimalla tai maksimoimalla tavoitefunktiota, joka mallintaa optimoitavaa asiaa. Lineaarisessa optimointiongelmassa tavoitefunktio ja rajoitefunktiot, jotka muodostavat sallittujen ratkaisujen, ovat affiineja. Jos lisäksi jotkin ongelman muuttujista saavat olla ainoastaan kokonaislukuarvoisia, niin on kyseessä lineaarinen kokonaislukuoptimointiongelma.
Lineaariseen optimointiin on olemassa tehokkaita algoritmeja, jotka ratkaisevat nopeasti laajojakin ongelmia hyödyntämällä ongelman lineaarisuudesta seuraavia matemaattisia ominaisuuksia. Muuttujien kokonaislukuvaatimukset estävät samojen ominaisuuksien hyödyntämisen lineaarisessa kokonaislukuoptimoinnissa. Myöskään raakaan laskentavoimaan pohjautuvat menetelmät eivät ole kelvollisia, sillä mahdollisten ratkaisujen määrä kasvaa ekspotentiaalisessa suhteessa ongelman muuttujien lukumäärään.
Sekä yllä mainittujen ongelmien takia, että lineaarisessa optimoinnissa saavutetun menestyksen ansiosta, lineaariseen kokonaislukuoptimointiin kehitetyt algoritmit perustuvat pitkälti lineaariseen optimointiin. Lineaarisessa kokonaislukuoptimoinnissa käytettävien algoritmien ideana on hetkellisesti poistaa muuttujien kokonaislukuvaatimukset, jolloin saatu ongelma on tavallinen lineaarinen optimointiongelma, joka osataan tehokkaasti ratkaista. Jos päädytään ratkaisuun, jossa kaikki kokonaislukurajoitteet täyttyvät, niin saatu ratkaisu on myös lineaarisen kokonaislukuoptimointiongelman optimiratkaisu. Jos tällaista ratkaisua ei saada, niin algoritmit lisäävät lineaariseen kokonaislukuoptimointiongelmaan uusia erityisrajoitteita, jotka poistavat ongelman käyvästä joukosta vähintään saadun jatkuvan tapauksen optimiratkaisun, mutta samalla takaavat, että alkuperäinen kokonaislukuvaatimukset täyttävä optimiratkaisu on yhä käypä. Tätä prosessia toistetaan, kunnes saadaan ratkaisu, joka täyttää kokonaislukuvaatimukset.
Lineaarisessa kokonaislukuoptimoinnissa käytetyt algoritmit eroavat toisissaan siinä, millaisia erikoisrajoitteita ongelmaan lisätään. Tässä työssä käydään läpi haaraudu ja rajoita -algoritmi, joka on pohjalla nykyään suositussa haaraudu ja leikkaa -algoritmissa
Lineaariseen optimointiin on olemassa tehokkaita algoritmeja, jotka ratkaisevat nopeasti laajojakin ongelmia hyödyntämällä ongelman lineaarisuudesta seuraavia matemaattisia ominaisuuksia. Muuttujien kokonaislukuvaatimukset estävät samojen ominaisuuksien hyödyntämisen lineaarisessa kokonaislukuoptimoinnissa. Myöskään raakaan laskentavoimaan pohjautuvat menetelmät eivät ole kelvollisia, sillä mahdollisten ratkaisujen määrä kasvaa ekspotentiaalisessa suhteessa ongelman muuttujien lukumäärään.
Sekä yllä mainittujen ongelmien takia, että lineaarisessa optimoinnissa saavutetun menestyksen ansiosta, lineaariseen kokonaislukuoptimointiin kehitetyt algoritmit perustuvat pitkälti lineaariseen optimointiin. Lineaarisessa kokonaislukuoptimoinnissa käytettävien algoritmien ideana on hetkellisesti poistaa muuttujien kokonaislukuvaatimukset, jolloin saatu ongelma on tavallinen lineaarinen optimointiongelma, joka osataan tehokkaasti ratkaista. Jos päädytään ratkaisuun, jossa kaikki kokonaislukurajoitteet täyttyvät, niin saatu ratkaisu on myös lineaarisen kokonaislukuoptimointiongelman optimiratkaisu. Jos tällaista ratkaisua ei saada, niin algoritmit lisäävät lineaariseen kokonaislukuoptimointiongelmaan uusia erityisrajoitteita, jotka poistavat ongelman käyvästä joukosta vähintään saadun jatkuvan tapauksen optimiratkaisun, mutta samalla takaavat, että alkuperäinen kokonaislukuvaatimukset täyttävä optimiratkaisu on yhä käypä. Tätä prosessia toistetaan, kunnes saadaan ratkaisu, joka täyttää kokonaislukuvaatimukset.
Lineaarisessa kokonaislukuoptimoinnissa käytetyt algoritmit eroavat toisissaan siinä, millaisia erikoisrajoitteita ongelmaan lisätään. Tässä työssä käydään läpi haaraudu ja rajoita -algoritmi, joka on pohjalla nykyään suositussa haaraudu ja leikkaa -algoritmissa