Rajoitusohjelmointi

Rajoitusohjelmointi, tunnettu myösConstraint programming (CP), on ohjelmointiparadigma, jossa ongelma esitetään muuttujien ja niiden arvojoukkojen rajoituksina sen sijaan, että annetaan yksilöllinen vaiheittainen ratkaisu. Tämän lähestymistavan tavoitteena on löytää kaikki tai osa ratkaisuja, jotka täyttävät annetut rajoitteet ja mahdollisesti optimoida jokin tavoitefunktio.

Perusperiaatteet ja malli. CP-ongelma koostuu finitely väljistä muuttujista, joille määritellään aikaisiksi mahdolliset arvot (domiinia). Muuttujien välillä on rajoitteita, jotka määrittelevät sallittujen arvojen yhdistelmät. Rajoitteiden lähettäminen tai propagointi pienentää arvojoukkoja niin, että ratkaisut etsitään usein hakuprosessin avulla, kuten backtracking- tai heuristiikkaperusteisella tutkimuksella. Joskus voidaan asettaa tavoitteellisia optimoitavia funktioita, jolloin CP yhdistetään optimointiin.

Käyttövälineet ja tekniikat. Tuloksellisia CP-työkaluja ovat korkean tason mallinnuskielet kuten MiniZinc sekä lukuisat solversit kuten Gecode, Choco, ja OR-Tools. CP tukee yleiskäyttäytyviä ns. global-konstraintteja, kuten alldifferent tai cumulative, jotka helpottavat monimutkaisten suhteiden ilmaisua. CP-lähestymistapaa käytetään usein yhdessä muiden tekniikoiden kanssa, kuten SAT- ja ILP-menetelmien kanssa, riippuen ongelman luonteesta.

Sovellukset. Rajoitusohjelmointia sovelletaan laajasti ajoitukseen ja resurssien hallintaan, tuotantoprosesseihin, työnkulku- ja tehtäväsuunnitteluun, koulutustaulutukseen sekä reittisuunnitteluun ja logistiikkaan. Sen etuja ovat selkeä, korkean tason malli ja kyky käsitellä monimutkaisia, loogisia rajoitteita, mutta haasteena voi olla laajojen tai erittäin yhdistettyjen ongelmien suorituskyky sekä oikean muodon löytö.

Historia ja asema. CP kehittyi 1980-luvulla CSP- ja rajoitteiden propagoinnin ympärille; siitä on kehittynyt vankka teoreettinen perusta ja käytännön työkalukokoelma. Nykyisin CP on osa monipuolisia optimointi- ja suunnittelutyökaluja, tarjoten joustavan ratkaisun monimutkaisille määrityksille ilman tiukkaa, vaiheittaista ohjelmointia.