Sarakepolvi - Column generation

Sarakkeiden luonti tai viivästetty sarakkeiden luonti on tehokas algoritmi suurten lineaaristen ohjelmien ratkaisemiseen .

Ydinajatuksena on, että monet lineaariset ohjelmat ovat liian suuria ottaakseen kaikki muuttujat nimenomaisesti huomioon. Lähtökohtana on, että suurin osa muuttujista ei ole perusasetuksia ja että niiden arvo on nolla optimaalisessa ratkaisussa. Tämän vuoksi vain muuttujien osajoukko on otettava teoriassa huomioon ongelman ratkaisemisessa. Sarakkeiden luominen hyödyntää tätä ajatusta vain muuttujien luomiseksi, joilla on potentiaalia parantaa tavoitetoimintoa - eli löytää muuttujia, joilla on negatiiviset alennetut kustannukset (olettaen , että ongelma on minimointiongelma menettämättä yleisyyttä ).

Ratkaistava ongelma on jaettu kahteen ongelmaan: pääongelmaan ja alaongelmaan. Pääongelma on alkuperäinen ongelma, jossa otetaan huomioon vain osa muuttujista. Alaongelma on uusi ongelma, joka on luotu uuden muuttujan tunnistamiseksi. Alaongelman tavoitetoiminto on uuden muuttujan alennettu hinta suhteessa nykyisiin kaksoismuuttujiin, ja rajoitukset edellyttävät, että muuttuja noudattaa luonnossa esiintyviä rajoituksia.

Prosessi toimii seuraavasti. Pääongelma on ratkaistu - tästä ratkaisusta voimme saada kaksoishinnat kullekin pääongelman rajoitukselle. Tätä informaatiota hyödynnetään sitten alaongelman tavoitetoiminnossa. Alaongelma on ratkaistu. Jos alaongelman objektiivinen arvo on negatiivinen, on tunnistettu muuttuja, jolla on negatiiviset alennetut kustannukset. Tämä muuttuja lisätään sitten pääongelmaan ja pääongelma ratkaistaan ​​uudelleen. Pääongelman uudelleen ratkaiseminen tuottaa uuden joukon kaksoisarvoja, ja prosessi toistetaan, kunnes negatiivisia alennettujen kustannusten muuttujia ei tunnisteta. Alaongelma palauttaa ratkaisun, jolla ei ole negatiivisia alennettuja kustannuksia. Voimme päätellä, että pääongelman ratkaisu on optimaalinen.

Monissa tapauksissa tämä antaa mahdollisuuden ratkaista suuria lineaarisia ohjelmia, joita aiemmin pidettiin ratkaisemattomina. Klassinen esimerkki ongelmasta, jossa sitä käytetään menestyksekkäästi, on leikkuuongelma . Yksi erityinen tekniikka lineaarisessa ohjelmoinnissa, joka käyttää tällaista lähestymistapaa, on Dantzig-Wolfe-hajoamisalgoritmi . Lisäksi sarakkeiden luomista on sovellettu moniin ongelmiin, kuten miehistön aikatauluun , ajoneuvon reititykseen ja kapasitoituun p-mediaaniongelmaan .