INAUGURAL-DISSERTATION zurErlangungderDoktorwürdeder Naturwissenschaftlich-MathematischenGesamtfakultät derRuprecht-Karls-UniversitätHeidelberg vorgelegtvon Diplom–MathematikerinHannaSeitz,geborenePeters ausCastrop-Rauxel TagdermündlichenPrüfung:.April Contributions to the Minimum Linear Arrangement Problem Gutachter: Prof.Dr.GerhardReinelt Prof.Dr.Dr.h.c.HansGeorgBock Zusammenfassung DasMinimumLinearArrangementProblem(MinLA)bestehtdarin,füreinengewich- teten Graphen eine lineare Anordnung der Knoten zu bestimmen, welche die ge- wichteteSummederKantenlängenminimiert.DievorliegendeArbeituntersuchtden NutzeneinerneuenModelierungimRahmeneinesBranch-and-Cut-and-PriceAlgo- rithmuszuroptimalenLösungdesMinLA.DenKernderModellierungbildenbinäre Variablend ,diegenaudanndenWert1haben,wenndieKnoteniund jinderPer- ijk mutationdieDistanzkhaben.WirpräsentierenangepassteFormulierungenfürdicht- und dünnbesetzte Graphen und erläutern die Realisierung eines Branch-and-Cut- and-Price Algoritmus’. Desweiteren werden die verschiedenen Varianten des Algo- rithmus’diskutiertundevaluiert.ZumStudiumdertheoretischenAspektedesMinLA leistenwireinenBeitragmitderCharakterisierungeinerRelaxierungdeszugehörigen Polyeders. Abstract TheMinimumLinearArrangementproblem(MinLA)consistsinfindinganordering of the nodes of a weighted graph, such that the sum of the weighted edge lengths is minimized. We report on the usefulness of a new model within a branch-and-cut- and-pricealgorithmforsolvingMinLAproblemstooptimality.Thekeyideaistoin- troducebinaryvariablesd ,thatareequalto1ifnodesiand jhavedistancekinthe ijk permutation.Wepresentformulationsforcompleteandforsparsegraphsandexplain the realization of a branch-and-cut-and-price algorithm. Furthermore, its different settingsarediscussedandevaluated. Tothestudyofthetheoreticalaspectsconcern- ingtheMinLA,wecontributeacharacterizationofarelaxationofthecorresponding polyeder. v vii AboveallIwanttothankProf.G.Reineltwhoallowedmetobalanceresearchand teaching,averyinterestingcombination.Furthermore,hewasmysoundingboard whenneededandgavemeinvaluableadvice. ThanksareduealsotoProf.G.Bockforwritingthereportandbeingveryflexiblein adaptingtothetightschedule. MarcusOswaldwasthebestteacherimaginableforon–the–job–training. Furthermore,Iamtrulythankfulforhiscountlesssuggestionsandunfailingclear explanations. IamverygreatfultohavehadThorstenBonatoasmycolleague.Hewasalways willingtolistencarefullyandtirelessinhelpingmetofindanswers. CaraCocking,MarkusSpethandPeiWangprovidedaveryrelaxedatmospherein theoffice.Thanksforbeingsuchniceco-workers. IamtrulythankfulforthementoringofDirkO.Theis.Workingwithhimwas tremendouslyinspiringandencouraging.Iappreciatedhiscompetenceandfeedback aswellashisneverendingenthusiasm.Itmadeagreatdifferenceduringallthese years. ToCatherineProux–Wielandahuge"thankyou"fortheexcellentmanagementofall administrativetasks.Hercaringdelightfulnaturecreatesaverypleasantworking atmosphere. ThanksalsotoGeorgiosNikolisandAdrianDempwolffforkeepingthecomputer systemrunning.Theirattentiontoeverydetailmadeworkingapleasure. WithoutthepresenceofKarinTenschertoursociallifewouldhavebeenmuchless exciting.Thanksforbeinginterested,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. FortheproofreadingpartsofmythesisIthankThorstenBonato,ElsbethDuke, SarahMaidstone,MarcusOswald,RobertSchwarz,ChristophSchwitzer,Markus Speth,DirkO.Theis,andStefanWiesberg.Nevertheless,Itakefullresponsibilityfor anyerrorsthatmayremain. Overalltheseyearsmyfamilyandalotoffriendsinfluencedmeenormouslybytheir encouragementandsupport.Iamtrulyindebtedtoallminorandmajor contributions. LastbutnotleastmyheartfeltthanksgotomyparentsHeikeandFriedhelmPeters towhomIamendebtedthemost.