Contributions to the minimum linear arrangement problem [Elektronische Ressource] / vorgelegt von Hanna Seitz, geb. Peters

De
INAUGURAL-DISSERTATIONzurErlangungderDoktorwürdederNaturwissenschaftlich-MathematischenGesamtfakultätderRuprecht-Karls-UniversitätHeidelbergvorgelegtvonDiplom–MathematikerinHannaSeitz,geborenePetersausCastrop-RauxelTagdermündlichenPrüfung: . AprilContributionstotheMinimumLinearArrangementProblemGutachter: Prof.Dr.GerhardReineltProf.Dr.Dr.h.c.HansGeorgBockZusammenfassungDasMinimumLinearArrangementProblem(MinLA)bestehtdarin,füreinengewich-tetenGrapheneinelineareAnordnungderKnotenzubestimmen,welchediege-wichteteSummederKantenlängenminimiert.DievorliegendeArbeituntersuchtdenNutzeneinerneuenModelierungimRahmeneinesBranch-and-Cut-and-PriceAlgo-rithmuszuroptimalenLösungdesMinLA.DenKernderModellierungbildenbinäreVariablend ,diegenaudanndenWert1haben,wenndieKnoteniund jinderPer-ijkmutationdieDistanzkhaben.WirpräsentierenangepassteFormulierungenfürdicht-unddünnbesetzteGraphenunderläuterndieRealisierungeinesBranch-and-Cut-and-PriceAlgoritmus’. DesweiterenwerdendieverschiedenenVariantendesAlgo-rithmus’diskutiertundevaluiert.ZumStudiumdertheoretischenAspektedesMinLAleistenwireinenBeitragmitderCharakterisierungeinerRelaxierungdeszugehörigenPolyeders.AbstractTh e Minimum Linear Arrangement problem(MinLA)consistsinfindinganorderingofthenodesofaweightedgraph,suchthatthesumoftheweightededgelengthsisminimized. Wereportontheusefulnessofanewmodelwithinabranch-and-cut-and-pricealgorithmforsolvingMinLAproblemstooptimality.
Publié le : vendredi 1 janvier 2010
Lecture(s) : 16
Tags :
Source : D-NB.INFO/1002005167/34
Nombre de pages : 209
Voir plus Voir moins

INAUGURAL-DISSERTATION
zurErlangungderDoktorwürdeder
Naturwissenschaftlich-MathematischenGesamtfakultät
derRuprecht-Karls-UniversitätHeidelberg
vorgelegtvon
Diplom–MathematikerinHannaSeitz,geborenePeters
ausCastrop-Rauxel
TagdermündlichenPrüfung: . AprilContributionstothe
MinimumLinearArrangement
Problem
Gutachter: Prof.Dr.GerhardReinelt
Prof.Dr.Dr.h.c.HansGeorgBockZusammenfassung
DasMinimumLinearArrangementProblem(MinLA)bestehtdarin,füreinengewich-
tetenGrapheneinelineareAnordnungderKnotenzubestimmen,welchediege-
wichteteSummederKantenlängenminimiert.DievorliegendeArbeituntersuchtden
NutzeneinerneuenModelierungimRahmeneinesBranch-and-Cut-and-PriceAlgo-
rithmuszuroptimalenLösungdesMinLA.DenKernderModellierungbildenbinäre
Variablend ,diegenaudanndenWert1haben,wenndieKnoteniund jinderPer-ijk
mutationdieDistanzkhaben.WirpräsentierenangepassteFormulierungenfürdicht-
unddünnbesetzteGraphenunderläuterndieRealisierungeinesBranch-and-Cut-
and-PriceAlgoritmus’. DesweiterenwerdendieverschiedenenVariantendesAlgo-
rithmus’diskutiertundevaluiert.ZumStudiumdertheoretischenAspektedesMinLA
leistenwireinenBeitragmitderCharakterisierungeinerRelaxierungdeszugehörigen
Polyeders.
Abstract
Th e Minimum Linear Arrangement problem(MinLA)consistsinfindinganordering
ofthenodesofaweightedgraph,suchthatthesumoftheweightededgelengthsis
minimized. Wereportontheusefulnessofanewmodelwithinabranch-and-cut-
and-pricealgorithmforsolvingMinLAproblemstooptimality.Th ekeyideaistoin-
troducebinaryvariablesd ,thatareequalto1ifnodesiand jhavedistance kintheijk
permutation.Wepresentformulationsforcompleteandforsparsegraphsandexplain
therealizationofabranch-and-cut-and-pricealgorithm. Furthermore,itsdifferent
settingsarediscussedandevaluated.Tothestudyofthetheoreticalaspectsconcern-
ingtheMinLA,wecontributeacharacterizationofarelaxationofthecorresponding
polyeder.
vvii
AboveallIwanttothankProf.G.Reineltwhoallowedmetobalanceresearchand
teaching,averyinterestingcombination.Furthermore,hewasmysoundingboard
whenneededandgavemeinvaluableadvice.
Th anksareduealsotoProf.G.Bockforwritingthereportandbeingveryflexiblein
adaptingtothetightschedule.MarcusOswaldwasthebestteacherimaginableforon–the–job–training.
Furthermore,Iamtrulythankfulforhiscountlesssuggestionsandunfailingclear
explanations.
IamverygreatfultohavehadTh orstenBonatoasmycolleague.Hewasalways
willingtolistencarefullyandtirelessinhelpingmetofindanswers.
CaraCocking,MarkusSpethandPeiWangprovidedaveryrelaxedatmospherein
theoffice.Th anksforbeingsuchniceco-workers.
IamtrulythankfulforthementoringofDirkO.Th eis.Workingwithhimwas
tremendouslyinspiringandencouraging.Iappreciatedhiscompetenceandfeedback
aswellashisneverendingenthusiasm.Itmadeagreatdifferenceduringallthese
years.
ToCatherineProux–Wielandahuge"thankyou"fortheexcellentmanagementofall
administrativetasks.Hercaringdelightfulnaturecreatesaverypleasantworking
atmosphere.
Th anksalsotoGeorgiosNikolisandAdrianDempwolffforkeepingthecomputer
systemrunning.Th eirattentiontoeverydetailmadeworkingapleasure.
WithoutthepresenceofKarinTenschertoursociallifewouldhavebeenmuchless
exciting.Th anksforbeinginterested,givingemotionalsupportaswellassharing
personalperspectives.
OnnumerousoccasionsIexperiencedgreatcooperationbetweenvariousgroups
andmembersoftheinstitute.InparticularIwanttothankProf.K.Ambos–Spies,
Prof.T.LudwigandProf.B.Paechfortheirpersonalengagement.
Eventhoughandmuchtomyregret,wedidnotspendmuchtimetogether,Iwantto
thankProf.E.Fernandez,Barcelona,forinterestingscientificdiscussions.
IthankProf.A.Letchford,Lancaster(UK),forourinspiringdiscussionsand
exceptionallypleasantteamwork.Ithasbeenagreathonortodoresearchwithhim.
FortheproofreadingpartsofmythesisIthankTh orstenBonato,ElsbethDuke,
SarahMaidstone,MarcusOswald,RobertSchwarz,ChristophSchwitzer,Markus
Speth,DirkO.Th eis,andStefanWiesberg.Nevertheless,Itakefullresponsibilityfor
anyerrorsthatmayremain.
Overalltheseyearsmyfamilyandalotoffriendsinfluencedmeenormouslybytheir
encouragementandsupport.Iamtrulyindebtedtoallminorandmajor
contributions.
LastbutnotleastmyheartfeltthanksgotomyparentsHeikeandFriedhelmPeters
towhomIamendebtedthemost.

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.