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

Hanna Seitz

Sujets

• Mathematics

Informations

• Publié par: ruprecht-karls-universitat_heidelberg
• Publié le: 01 janvier 2010
• Nombre de lectures: 16
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait

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.