Abstract
Denne afhandling omhandler Dantzig-Wolfe dekomponering af heltalsproblemer med specielt
henblik på at tilføje snit i det dekomponerede problem. Dantzig-Wolfe dekomponering benyttes
ofte på heltalsproblemer (de originale problemer) med strukturelle egenskaber, der gør, at de
med fordel kan opdeles i mindre dele (delproblemer), hvis løsninger samles i et master problem.
For at løse master problemet kan man benytte kolonnegenering på den lineære relaksering.
Ved kolonnegenering tilføjes løsninger fra delproblemerne (udtrykt som kolonner) undervejs i
løsningsprocessen indtil ingen kolonner kan forbedre den lineære løsning af master problemet.
På denne måde benyttes kun en brøkdel af de eksponentielt mange mulige kolonner (vari-
able) i master problemet. Løsningen til den lineære relaksering benyttes som grænseværdi i
en branch-and-bound algoritme til at finde en heltalsløsning.
Et snit er en lovlig ulighed til problemet, som bortskærer en fraktional løsning. Dvs. en
løsning til den lineære relaksering bortskæres uden at bortskære en heltalsløsninger. Når s-
nit benyttes sammen med kolonnegenering kaldes det en branch-and-cut-and-price algoritme.
Når et snit tilføjes i master problemet skal den duale omkostning fra snittene medtages i
omkostningsberegningerne for de generede kolonner. Hvis et snit kan opskrives som en linear
kombination af variable i det originale problem er dette ligetil, da kun omkostningen for de
enkelte variable i delproblemerne ændrer sig. Det skal dog nævnes, at selvom kun omkostnin-
gen ændrer sig kan delproblemerne godt skifte karakter. Dette bemærkes især, hvis specielt
designede algoritmer benyttes til løsning af delproblemerne. Snit udledt fra det originale prob-
lem benyttes ofte i branch-and-cut-and-price algoritmer, derimod er det mindre velstuderet
at benytte snit defineret direkte på variable i master problemet. En af udfordringerne er, at
omkostningsberegningerne for nye kolonner bliver mere komplekse, da det muligvis ikke er
muligt at udtrykke den duale omkostning på snittet ved alene at ændre på omkostningen af
variablerne i delproblemet. I denne ph.d. afhandling vises det, hvorledes et snit defineret på
master problem variable kan beskrives i det originale problem.
Det videnskabelige hovedbidrag præsenteres i fire artikler. Den første artikel omhandler
brug af subset-row uligheder, som er en delmængde af den generelle familie af Chvátal-Gomory snit, i ruteplanlægningsproblemet med tidsvinduer (eng.: the vehicle routing problem with
time windows). I denne artikel beskrives hvorledes snittene på master problemet kan imple-
menteres i den dynamiske programmeringsalgoritme til delproblemet på en effektiv måde.
Resultaterne er meget lovende, og med de nye snit var det muligt at nde optimale lsninger
til adskillige hidtil uløste problemer. I den anden artikel bygges videre på dette resultat,
og teorien udvides således, at alle Chvátal-Gomory rang-1 snit kan tilføjes til ruteplanlægn-
ingsproblemet med tidsvinduer. Resultaterne er ikke nær så imponerende som i den forrige
artikel, men det vises, at det er muligt at finde særdeles gode grænseværdier ved tilføjelsen
af denne familie af snit.
I den tredje artikel betragtes klike (eng.: clique) uligheder, som er et kombinatorisk snit
til master problemet for ruteplanlægningsproblemet med tidsvinduer. I tråd med arbejdet i
de forrige artikler, beskrives i denne artikel hvorledes klike ulighederne kan behandles i al-
goritmen for delproblemet. Eksperimentelle resultater indikerer, at der er en gevinst mht.
grænseværdien, men at hastigheden på algoritmen forringes i de
fleste tilfælde. I den afsluttende fjerde artikel præsenteres en generel ramme for brug af snit i branch-and-cut-and-price algoritmer. Med rammen beskrives hvorledes snit i det originale og master problemet er for-
bundet, og specielt vises det, at snit defineret på variable i master problemet kan beskrives
ved at betragte et udvidet originalt problem. Artiklen giver en beskrivelse og en indsigt til snit
i branch-and-cut-and-price algoritmer, som forhåbentlig kan føre til mere forskning indenfor
dette område.
Udover hovedbidraget er der medtaget yderligere tre artikler som er udarbejdet under
ph.d.-forløbet. Den første artiklen præsenterer en snitalgoritme for det ressourcebegrænsede
korteste vej problem, der ofte ses som delproblem ved dekomponering. Algoritmen er i bestemte
tilfælde klart overlegen i forhold til klassiske algoritmer baseret på dynamisk programmer-
ing. Den anden artikel præsenterer en kolonnegenereringsalgoritme til et beskyttelsessys-
tem indenfor rutning af telekommunikation i et fibernetværk. Det ønskes at identificere
primær- og backup-veje således at alt båndbredde er under den bedste beskyttelse. En kolon-
negenereringsmodel, hvor en kolonne denerer parret beståaende af en primær- og en backup-
vej, bliver beskrevet, og udførte tests viser, at dette beskyttelsessystemet er yderst effektivt.
Den tredje artikel omhandler indkomststyring i liner shipping virksomheder, hvori omfordeling
af containere behandles. Da verden er delt i eksport/import zoner (fx. fra Asien til Europa) er
omfordelingen af containere et reelt problem, da kapaciteten på skibene ellers er misvisende.
Der præsenteres en kolonnegenereringsmodel, hvor en kolonne er en plan for transport af et
produkt fra en forsyningshavn til en efterspørgselshavn. Ved brug af denne algoritme er det
muligt at lse problemer af et langt større omfang end hidtil.
henblik på at tilføje snit i det dekomponerede problem. Dantzig-Wolfe dekomponering benyttes
ofte på heltalsproblemer (de originale problemer) med strukturelle egenskaber, der gør, at de
med fordel kan opdeles i mindre dele (delproblemer), hvis løsninger samles i et master problem.
For at løse master problemet kan man benytte kolonnegenering på den lineære relaksering.
Ved kolonnegenering tilføjes løsninger fra delproblemerne (udtrykt som kolonner) undervejs i
løsningsprocessen indtil ingen kolonner kan forbedre den lineære løsning af master problemet.
På denne måde benyttes kun en brøkdel af de eksponentielt mange mulige kolonner (vari-
able) i master problemet. Løsningen til den lineære relaksering benyttes som grænseværdi i
en branch-and-bound algoritme til at finde en heltalsløsning.
Et snit er en lovlig ulighed til problemet, som bortskærer en fraktional løsning. Dvs. en
løsning til den lineære relaksering bortskæres uden at bortskære en heltalsløsninger. Når s-
nit benyttes sammen med kolonnegenering kaldes det en branch-and-cut-and-price algoritme.
Når et snit tilføjes i master problemet skal den duale omkostning fra snittene medtages i
omkostningsberegningerne for de generede kolonner. Hvis et snit kan opskrives som en linear
kombination af variable i det originale problem er dette ligetil, da kun omkostningen for de
enkelte variable i delproblemerne ændrer sig. Det skal dog nævnes, at selvom kun omkostnin-
gen ændrer sig kan delproblemerne godt skifte karakter. Dette bemærkes især, hvis specielt
designede algoritmer benyttes til løsning af delproblemerne. Snit udledt fra det originale prob-
lem benyttes ofte i branch-and-cut-and-price algoritmer, derimod er det mindre velstuderet
at benytte snit defineret direkte på variable i master problemet. En af udfordringerne er, at
omkostningsberegningerne for nye kolonner bliver mere komplekse, da det muligvis ikke er
muligt at udtrykke den duale omkostning på snittet ved alene at ændre på omkostningen af
variablerne i delproblemet. I denne ph.d. afhandling vises det, hvorledes et snit defineret på
master problem variable kan beskrives i det originale problem.
Det videnskabelige hovedbidrag præsenteres i fire artikler. Den første artikel omhandler
brug af subset-row uligheder, som er en delmængde af den generelle familie af Chvátal-Gomory snit, i ruteplanlægningsproblemet med tidsvinduer (eng.: the vehicle routing problem with
time windows). I denne artikel beskrives hvorledes snittene på master problemet kan imple-
menteres i den dynamiske programmeringsalgoritme til delproblemet på en effektiv måde.
Resultaterne er meget lovende, og med de nye snit var det muligt at nde optimale lsninger
til adskillige hidtil uløste problemer. I den anden artikel bygges videre på dette resultat,
og teorien udvides således, at alle Chvátal-Gomory rang-1 snit kan tilføjes til ruteplanlægn-
ingsproblemet med tidsvinduer. Resultaterne er ikke nær så imponerende som i den forrige
artikel, men det vises, at det er muligt at finde særdeles gode grænseværdier ved tilføjelsen
af denne familie af snit.
I den tredje artikel betragtes klike (eng.: clique) uligheder, som er et kombinatorisk snit
til master problemet for ruteplanlægningsproblemet med tidsvinduer. I tråd med arbejdet i
de forrige artikler, beskrives i denne artikel hvorledes klike ulighederne kan behandles i al-
goritmen for delproblemet. Eksperimentelle resultater indikerer, at der er en gevinst mht.
grænseværdien, men at hastigheden på algoritmen forringes i de
fleste tilfælde. I den afsluttende fjerde artikel præsenteres en generel ramme for brug af snit i branch-and-cut-and-price algoritmer. Med rammen beskrives hvorledes snit i det originale og master problemet er for-
bundet, og specielt vises det, at snit defineret på variable i master problemet kan beskrives
ved at betragte et udvidet originalt problem. Artiklen giver en beskrivelse og en indsigt til snit
i branch-and-cut-and-price algoritmer, som forhåbentlig kan føre til mere forskning indenfor
dette område.
Udover hovedbidraget er der medtaget yderligere tre artikler som er udarbejdet under
ph.d.-forløbet. Den første artiklen præsenterer en snitalgoritme for det ressourcebegrænsede
korteste vej problem, der ofte ses som delproblem ved dekomponering. Algoritmen er i bestemte
tilfælde klart overlegen i forhold til klassiske algoritmer baseret på dynamisk programmer-
ing. Den anden artikel præsenterer en kolonnegenereringsalgoritme til et beskyttelsessys-
tem indenfor rutning af telekommunikation i et fibernetværk. Det ønskes at identificere
primær- og backup-veje således at alt båndbredde er under den bedste beskyttelse. En kolon-
negenereringsmodel, hvor en kolonne denerer parret beståaende af en primær- og en backup-
vej, bliver beskrevet, og udførte tests viser, at dette beskyttelsessystemet er yderst effektivt.
Den tredje artikel omhandler indkomststyring i liner shipping virksomheder, hvori omfordeling
af containere behandles. Da verden er delt i eksport/import zoner (fx. fra Asien til Europa) er
omfordelingen af containere et reelt problem, da kapaciteten på skibene ellers er misvisende.
Der præsenteres en kolonnegenereringsmodel, hvor en kolonne er en plan for transport af et
produkt fra en forsyningshavn til en efterspørgselshavn. Ved brug af denne algoritme er det
muligt at lse problemer af et langt større omfang end hidtil.
Originalsprog | Engelsk |
---|
Udgivelsessted | København |
---|---|
Forlag | Department of Computer Science, University of Copenhagen |
Antal sider | 198 |
Status | Udgivet - 2008 |