View of Placement and global routing of VLSI macro-Cell layouts using genetic algorithms

Bibliography

[1] Stuart E. Dreyfuss, \An Appraisal of Some Shortest-Path Algo-

rithms," Journal of the Operations Rese arch Society of Americ a,

Vol. 17, pp. 395-412, 1969.

[2] Henrik Esbensen,\ComputingNear-Optimal SolutionstotheSteiner

ProbleminaGraphUsingaGenetic Algorithm,"Technical Report,

Daimi PB-468, AarhusUniversity, Feb. 1994.

[3] HenrikEsbensen, Pinaki Mazumder, \AGeneticAlgorithmfor the

Steiner ProbleminaGraph," Proc eedings of the Europe an Design

and Test Conferenc e, pp. 402-406, 1994.

[4] D. E. Goldberg, Genetic Al gorithms in Se arch, Optimization, and

Machine Le arning, Addison-Wesley, 1989.

[5] John H. Holland,Adaptionin Natural and Articial Systems, Univer-

sityof MichiganPress, AnnArbor, MI., 1975.

[6] E. L. Lawler, Combinatorial Optimization: Networks and Matroids,

Holt, RinehartandWinston, NewYork, 1976.

[7] Y. Nishizaki,M. Igusa,A. Sangiovanni-Vincentelli,\Mercury: ANew

Approachto Macro-cell Global Routing," Procee dings of the IFIP

10/WG10.5 International Conferenc e on VLSI, Munich, 1989.

[8] Carl Sechen, VLSI Pl ac ement and Gl ob al Routing Using Simul ate d

Anne aling, KluwerAcademicPublishers, Boston, 1988.

[9] G. F. Sullivan, \ApproximationAlgorithms for Steiner TreeProb-

lems,"Technical Report 249, Dept. of Computer Science, YaleUni-

versity, 1982.

[10] R. Venkateswaran, P. Mazumder, \RoutingAlgorithmsinSemicon-

ductorCircuitDesign,"Inpreparation.

densitiesandupdatingchanneldensitiesdynamicallywouldhencereduce

runtimesignicantly. Anotherapproachisto implementaparallelversion

oftherouter. Duetotheinherentparallelismofany GA, ahighspeedup

canbeexpectedonanyMIMDarchitecture[4].

D.5 Conclusion and Future Work

Inthis paper anovel approachtoglobal routingof macro-cell layouts

based ongeneticalgorithmshasbeenpresented. Theperformanceof the

routeriscomparedto thatofTimberWolfMConMCNCbenchmarks. Ex-

perimental resultsshowsthat thequalityof completedlayoutsimproves

whenusingthe GA-basedrouter insteadof TimberWolfMC, assuming

thatthequality ofthegiven placementissuciently high. Therouter is

inferiortoTimberWolfMCwithrespecttoruntime, butmajor improve-

ments are possible. Sincethe workpresentedhere is arst approach

toglobal routingbasedongeneticalgorithms, future improvements of

thelayout qualityobtainablearealsoverylikely. Weconcludethat the

geneticalgorithmiswell suitedasthebasicalgorithmof aglobal router.

rmedthisassumption. Thetopologyoftheroutinggraphof ami33-2-M

isunalteredthroughouttheprocessandtheperformanceoftheGA-based

routerisnowsuperiortothatofTimberWolfMC.Very similarresultsare

observedforami49-M:Theroutinggraph topologyissignicantlyaltered

duringthelayoutprocess. Theplacementof ami49-2-Misobtainedthe

samewayas ami33-2-M, andtheperformanceof theGA-basedrouter

improvessignicantlyonthisexample.

Thesignicantroutinggraph alterationsforsomeproblemsareacon-

sequenceof rather poor initial placements. It is not clear how better

placementswouldaecttherelativeperformanceof thetworouters. As

placementquality increases, therelativeeectof eliminatingawirefrom

the longest pathinapolar graphincreases, indicatingapotential ad-

vantagefor theGA-basedrouter. Ontheotherhand, agoodplacement

containslessrouting, suggestingthattheperformancegapwould benar-

rowed.

For thetest examplesconsideredhere, mostroutingchannels onthe

longestpathsarecompactedtotheirminimumwidthsbythecompactor,

cf. thesecondassumptiondiscussedinSectionD.3.1. However, inmost

cases atleast onechannel onthelongestpaths arestill wider thannec-

essary. Hence, theareaestimation performedtendstounderestimatethe

nal area. However, thisassumptionappearstobefairlyreasonable.

D.4.4 Runtime

Onaveragetherouterrequiresabout22, 12and 130minutestorouteex-

amples basedonxerox, ami33andami49, respectively. TimberWolfMC

spends about 30seconds for examples basedonxeroxandami33, and

about5minutesforami49-basedexamples. Hence, theGA-basedrouter

is clearlyinferiortoTimberWolfMCwithrespecttoruntime. Thetotal

layout generationprocess performedbyMosaico(i.e. excludingplace-

ment) requiresabout15minutesforexamplesbasedon xeroxand ami33,

andabout anhour for ami49-basedexamples, whenTimberWolfMCis

used. Hence, theuseof theGA-basedrouter increasesthelayoutgener-

ationtimebyafactorof twoorthree.

However, theruntimeofthecurrentimplementationcan beimproved

signicantlyinanumber of ways. The vast majority of the runtime

is spendcomputingchannel densities. Whenestimatingthe areaof a

solution, all densitiesarerecomputed whethertheroutinginachannel is

100(GA-result=TW-result01). Hence, anegativevalueindicates are-

ductioninpercent obtainedbythe GA-basedrouter, whileapositive

valueindicates apercentageoverheadas comparedtoTimberWolfMC.

DespitetheinherentproblemsofthiskindofcomparisondiscussedinSec-

tionD.4.2, itisclearthat ingeneral theGA-basedglobal router obtains

thebestlayoutqualityfortheprobleminstancesconsidered.

Problem Solution A

tot A

r oute WL

xerox-M

best 01:9 04: 7 +0: 0

avg 01: 4 03: 5 +0: 8

ami33-M best 03: 2 05: 1 03: 2

avg +1: 6 +2: 5 00: 2

ami33-2-M best 03: 0 04: 7 01: 5

avg 01: 1 01: 7 00: 2

ami49-M best 01: 9 03: 3 01: 5

avg 00: 5 00: 8 +0: 3

ami49-2-M

best 04: 2 07: 3 04: 0

avg 03: 7 06: 3 02: 9

TableD.2: Rel ative improvements obtaine d by the GA-b ase d router. b est

and avg. is b est and average of the ve runs performe d.

Inspectionof the generatedlayouts reveals interestinginformation

regardingthe twomajor assumptions underlying the areaestimation,

discussedinSectionD.3.1. Theplacement of xerox-Mis adjustedonly

slightly duringcompaction, andtheroutinggraphtopologyisunaltered.

For this example, theGA-basedrouter obtains anaveragereductionof

3.5% of theroutingareawhichcomesatthepriceof a0.8%increasein

totalwirelength. However,forami33-M, theGA-basedrouteron average

obtainslarger layoutsthanTimberWolfMC. Inthis casetheplacement,

andhencethe routinggraphtopology, is signicantlymodiedbythe

compactor. Asaconsequence, thefunctionminimizedbytheGA-based

router inits secondphase correlates verypoorly tothe actual layout

generated, whichinevitablyleads toapoor result. Tocounteract this

phenomenon, anewplacementami33-2-Mwas producedbyrippingup

all routinginthecompletedlayoutof ami33-MgeneratedusingTimber-

WolfMC. Sincetheplacementthusobtainedistheresult of compaction

andcompletionofallrouting, itwill probably only besubjected tominor

in Octtools. ami33-2-Mandami49-2-Mareotherplacementsofami33-M

andami49-M, respectively. Thegenerationof theseplacements arede-

scribedinSectionD.4.3.

D.4.2 Method

Twofactorsmakesitdiculttodeviceasequenceofexperimentsprovid-

inganabsolutefair performancecomparisonof thetwoglobal routers.

Firstly,globalroutingisjustoneofasequenceofheavilyinteracting steps

neededtogenerateacompletelayout. Hence, when consideringaspecic

result, itmaybeinuencedbyapatternofinteractionswithothertools,

which accidentally favoursoneoftherouters. Secondly, theoptimization

strategiesusedbythetworoutersarenotidentical. Asdescribedearlier,

theGA-basedrouterexplicitlyattemptstominimizeareaandsecondar-

ilywirelength. WhileTimberWolfMCalsogeneratestheshortestpossible

routesinphaseone, areaisnotanexplicitcomponentoftheoptimization

criterionusedinthesecondphase. Instead, TimberWolfMCselects the

shortestpossibleroutes subjecttochannel capacityconstraints.

Thechosenstrategyfor experiments areas follows: For eachof the

placedexamples listedinTableD.1, Mosaicowas executedtogenerate

acompletelayout, usingeither TimberWolfMCor theGA-basedrouter

for theglobal routingtask. Hence, all other steps of thelayout process

areperformedbythesametools.

Mosaico wasexecutedvetimesforeachexampleusingtheGA-based

global router inorder tocapturethevariationscausedbythestochastic

natureoftheappliedalgorithms. Thesamesetofparametersareusedfor

all programexecutions,i.e., noproblemspecictuningisperformed. For

eachnet, atmostR = 30alternativeroutes aregenerated. Theparame-

ters of theGAusedinphaseoneareas givenin[3]. ThephasetwoGA

isexecutedwith populationsizeM =40, stop criteriaS =100,mutation

probabilityp

mut

=2: 52 10 04

andinversionprobabilityp

inv

=0: 1. There

isnovariationof resultswhenapplyingTimberWolfMC.

D.4.3 LayoutQuality

Table D.2 summarizes the impact onthe completedlayouts of using

theGA-basedrouterinsteadof TimberWolfMC. A

tot

denotestotal area,

A

route

denotesroutingarea, i.e., thepart of thetotal areanot occupied

formaring. Apart of the ringis thenselectedat randomandre-

versed. More specically, twopoints x;y 2 f0; 1; : : : ; N 0 1g; x 6= y ,

are selectedat random. The operator thendenes the newordering

0

as 2

0

((x +i)modN)=((y 0i ) modN) if 0i (y 0x)modN

and 0

((x +i )modN)=((x +i )modN)otherwise,i =0; 1; : : : ; N01.

D. 4 Experi mental Resul ts

Therouter has beenimplementedintheCprogramminglanguage, and

all experiments are performedonaSunSparcIPXworkstation. The

router is interfacedwiththe macro-cell layout systemMosaico, which

is apart of the Octtools CADframeworkdevelopedat Universityof

California,Berkeley. Thisintegrationallowsforcomparisonoftherouters

performancetothatofTimberWolfMC[8], astateoftheartglobalrouter

alsointerfacedtoMosaico.

D.4.1 Test Examples

Threeof theMCNCmacro-cell benchmarks, xerox, ami33andami49,

wereusedfortheexperiments. However, duetoapurelytechnical prob-

lem, itbecamenecessarytoremoveall pads fromtheseexamplesbefore

usingthem 3

. Themodiedbenchmarksarereferencedusing a '-M'sux.

Problem

#cells #nets #terms.

xerox-M 10 203 696

ami33-M 33 85 442

ami33-2-M 33 85 442

ami49-M

49 390 913

ami49-2-M

49 390 913

TableD.1: Probl emcharacteristics.

Table D.1lists the maincharacteristics of thetest examples. The

numberof nets andthenumber of terminals listedaretotals, i.e., they

includethefewtrivial nets. xerox-M, ami33-Mandami49-Mareplaced

byPuppy, aplacementtool basedonsimulatedannealing, alsoincluded

2

Thedenitionof 0

reliesonthemathematical denitionof modulo,inwhichtheremainder

is always non-negative.

3

Inourversionof Octtools(5.2)thechannel denitionprogramAtlas cannothandlethepad

ThepopulationP =f p

0

; p

1

; : : : ; p

M01

g isthensortedlexicographically

usingareaas most signicant criterionandwirelengthas asecondary

criterion. Assumethat P is sortedindecreasingorder withrespect to

thisordering. ThetnessF ofp

i

isthencomputedasF(p

i

)=2i =(M01)

for i =0; 1; : : : ; M0 1. This scheme, calledranking, assures constant

varianceof tness throughout the optimizationprocess. Rankingis a

goodapproachfor controllingthe speedof convergence, includingthe

avoidanceof prematureconvergence.

D.3.2.3 CrossoverOperator

Giventwoparentindividuals and, thecrossover operator generates

twoospring, and . Theparent individuals arenot alteredbythe

operator. Inthefollowing, a(second)subscriptspecieswhichindividual

themarkedpropertyisapartof. Crossoverconsistsof twosteps:

1) Oneof theparents, say , is chosenat random, andacopy of is

made. is thenreorderedsothat it becomeshomologousto, that is,

=

.

2)Theospringaregiven thesameorderingastheirparents:

= =

. Standard 1-pointcrossoveristhen performed[5]: Acrossover-pointx

isselectedatrandominf0; 1; : : : ; N 02g . Theselectedroutesof isthen

denedbyq

(k );

=q

(k);

if k x andq

(k);

=q

(k);

otherwise, where

=

. Similarly, theselectedroutes of is denedbyq

(k);

=q

(k);

if k x andq

(k);

=q

(k);

otherwise.

D.3.2.4 Mutation and InversionOperators

Themutationoperatorisverysimple. Itgoesthrough theN tuplesofthe

givenindividual and randomlyselectsanotherrouteforthek'th netwith

probabilityp

mut (r

k

0 1), where p

mut

is asmall userdenedprobability.

This schemeiscalledpointwisemutation.

As mentionedinSectionD.3.2.1agivenglobal routingsolutioncan

berepresentedbyseveral equivalentindividualsbecauseof theindepen-

denceof theordering. However, thetness of ospringproducedby

crossover depends onthespecicorderings of thegivenparent individ-

uals. The purpose of inversionis tooptimizethe performance of the

crossover operator. Withagivenprobabilityp

i nv

, the inversionoper-

ator alters theordering of agivenindividual. Toobtainauniform

cess. Routineeval uate describedinSectionD.3.2.2computesthetness

of eachof thegivenindividuals, whileb estOf nds theindividual with

thehighesttness. Oneexecutionoftheouter\repeat"loopcorresponds

tothesimulationof onegeneration. Throughout thesimulation, M is

keptconstant. Wekeep trackof thebestindividual s everseen. Routine

stopCriteria terminates thesimulationwhennoimprovement has been

observedfor S consecutivegenerations. Eachgenerationis initiatedby

theformation of asetofospringP

N

ofsizeM. Thetwomatesp

1 and p

2

areselectedindependentlyofeachother, andeachmateisselectedwitha

probabilityproportional toitstness. Thecrossover routinedescribedin

Section D.3.2.3generatestwoospringc

1 andc

2

. Routinere duc e returns

theMttestofthegivenindividuals,therebykeepingthepopulationsize

constant. Thegeneticoperatorsformutationandinversionarediscussed

inSectionD.3.2.4. Routineoptimize(s )performssimplehill-climbingby

executingasequenceofmutationsons , eachofwhichimprovesthetness

of s . Theoutput of thealgorithmisthenthesolutions .

D.3.2.1 Representation

Aglobal routingsolutionisrepresentedbyspecifyingfor eachnetwhich

ofitspossibleroutesisused. Morespecically, assumeaxednumbering

0; 1; : : : ; N 01of thenets, let :f 0; 1; : : : ; N 01g 7! f0; 1; : : : ; N 01g

beabijectionanddenotebyr

k

R thenumber of routes generatedin

phaseonefor thek 'thnet. Anindividual isthenasetof N tuples:

f((0); q

(0)

); ((1); q

(1)

); : : : ; ((N 01); q

(N01) )g

where1q

k r

k

forall k =0; 1; : : : ; N01. Forexample,thetuple(3,7)

speciesthat the3rdnet uses its7'throute. Themapping denesan

orderingofthenets, thepurposeofwhichisexplainedinSectionD.3.2.4.

Notethat theroutingsolutionspeciedbyanindividual is independent

of .

D.3.2.2 Denitionof Fitness

GivenapopulationP, theroutineeval uate of Fig. D.5computesthet-

nessofeachindividualasfollows. Foreachindividualp 2 P, itsestimated

areais computedas describedinSectionD.3.1andits estimatedtotal

wirelengthiscomputedas thesumof thelengthof theroutes specied

Thealgorithmmaintains apopul ation of individual s, eachof which

correspondstoaspecicsolution. Ameasureof tness denesthequal-

ityof anindividual. Startingwithsome set of individuals, aprocess

of evolutionis simulated. The maincomponents of this process are

crossover, whichmimics propagation, andmutation, whichmimics the

randomchanges occurringinnature. After anumber of generations,

highlytindividualswill emergecorrespondingtogoodsolutionstothe

givenoptimizationproblem. AgoodintroductiontoGAsisgivenin[4].

generate(P

C );

evaluate(P

C );

s =bestOf(P

C );

repeatuntil stopCriteria():

P

N

=;;

repeatM= 2times:

selectp

1 2 P

C , p

2 2 P

C

;

crossover(p

1

; p

2

; c

1

; c

2 );

P

N

=P

N

[f c

1

; c

2 g;

end;

evaluate(P

C [ P

N );

P

C

=reduce(P

C [ P

N );

8p 2 P

C

: possiblymutate(p);

8 p 2 P

C

: possiblyinvert(p);

evaluate(P

C );

s =bestOf(P

C

[ fs g);

end;

optimize(s );

output s ;

FigureD.5: Outl ine of phase two.

Fig. D.5outlinesthephasetwoalgorithm. Initially, thecurrent pop-

ulationP

C

of sizeM =jP

C

j consists of M0 1randomlygeneratedin-

dividuals andasingleindividual consistingof theshortest routefound

for eachnet. Seedingthepopulationwiththis relativelygoodsolution

of thelongest pathinHPGthenestimatesthehorizontal lengthof the

layout. ByconstructingVPGinasimilar way, theareaisestimatedas

theproduct of thelongestpathinHPGtimesthelongestpathinVPG.

In[7] thecostof anedgeinthepolargraphsisarather simplefunc-

tionof thenumberof netspresentinthecorrespondingroutingchannel.

However, if m nets arepresentinachannel, thechannel densitycanbe

anynumberbetween0andm, assumingthat twometal layersareavail-

ablefor routingandthat eachlayer is usedexclusivelyfor routingina

specicdirection. Therefore, toobtain amoreaccurateareaestimate,we

computetheexact channel densityfor eachedgeintheroutinggraph.

Thisis possiblesincetheroutinginphaseonewasperformedusingac-

curatepositions fortheterminals of eachnet, cf. SectionD.2. Thecost

of anedgeinthepolargraphsisthenproportional tothedensityof the

correspondingchannel.

Several factors aects the accuracyof theareaestimate. The two

most important has todowiththe subsequent compaction/spacingof

thelayout:

1)Ifthecompactoralterstheplacementtotheextentwherethetopol-

ogyof theroutinggraphischanged, thepolargraphs arealsochanged.

Hence, the qualityof the areaestimatedecreases signicantlyor may

evenbecomemeaningless. Inother words, agoodinitial placement is

requiredsothat thecompactor will onlyperformminor adjustments of

thecell positions. Thissituationreects thewell-knownstrongmutual

dependencyof theplacementandglobal routingtasks.

2) It is implicitlyassumedthat thecompactor generates alayout in

whichnoroutingchannelonalongestpath ofapolargraph iswiderthan

needed. Otherwise, theareawill beunderestimated.

ThepracticalconsequencesoftheseassumptionsareaddressedinSec-

tionD.4.3.

D.3.2 AreaandWirelengthOptimization

Theconceptof geneticalgorithms, introducedbyJohnHolland[5], uti-

lizesthenotionof thenatural evolutionprocess. Innature, theindivid-

uals constitutingapopulationadapt totheenvironment inwhichthey

live. Thettestindividualshavethehighestprobabilityof survival and

tend toincreasein numbers, whilethelesstindividualstendtodieout.

This survival -of-the-ttest Darwinianprincipleis thebasicideabehind

considersfewer distinct solutionsandisslower thantheGA. Therefore,

theGAisusedforeverynetwithmorethantwoterminals

1

.

D. 3 Phase Two of the Router

Theareaestimateisof coursecrucial tothephasetwoalgorithm, andis

discussedinSectionD.3.1. Adetaileddescriptionof theGAperforming

theoptimizationthenfollowsinSectionD.3.2.

D.3.1 AreaEstimation

Asin[7,10] theareaestimationisbasedontheformationofpolargraphs

as illustratedinFigD.4. Foragivenplacementandroutinggraph, two

polargraphsareconstructed, ahorizontal (HPG)andavertical (VPG).

Letusstartbyconsidering HPG.TheverticesofHPGconsistsofavertex

for eachcell plustwoadditional vertices, asourceandasink. Eachedge

inHPGcorrespondstoaverticaledgeintheroutinggraphandisdirected

fromthesourcetowardsthesink.

source, HPG

source, VPG sink, VPG

sink, HPG

FigureD.4: Pol ar graphs for are a estimation.

Assumethat eachedge (v; w) has acost whichcorresponds tothe

spacingneededbetweencellsv andw toperformtherouting. Further-

more, assigntoeachpathfromsourcetosinkaxedcost whichis the

sumofthehorizontallengthofallcellsvisitedonthepath. Thetotal cost

1

Toobtainas manydistinct solutions as possible, theGAdoes not use the reductionof the

D.2.1 Two-terminal nets

For eachnet withtwoterminals, analgorithmduetoLawler [6] is used

tocomputetheshortest, second-shortest, third-shortest, etc. routeuntil

amaximumof R routes are foundor nomore routes exists. Lawlers

algorithmis exact but alsoquiteexpensive, requiringtimeO(Rn

3

) for

onenet, wheren isthenumberof verticesintheroutinggraph.

AnearlieralgorithmbyDreyfuss[1]mayatrstseemmoreattractive.

ItgeneratestheR shortestroutesfromadesignatedvertextoeachofthe

otherverticesintimeO (Rn logn). However, loopsareallowedin apath,

asopposedtoLawlersalgorithm, andif twopaths donotvisitthesame

verticesinthesameorder theyareconsidereddistinct. Onecouldthen

simply generateroutesuntil R looplessrouteswereobtained, which were

alsodistinct inthesensethat their sets of edgesaredistinct. However,

experimentshaveshownthatthisstrategyisnotfeasibleinpracticedue

tothenumberof routesthenrequired.

D.2.2 Netswithat least threeterminals

AtmostR distinctroutesaregeneratedforeachnethavingthreeormore

terminals usingaGAfor the SPG. For adetaileddescriptionof that

algorithmthereaderisreferredto[2, 3]. Therearetwomainadvantages

of usingthatalgorithminthiscontext. Firstly, itgenerateshigh-quality

solutions. In [2] theGAistested on graphswithupto2,500verticesand

isfoundtobewithin 1%fromtheglobal optimumsolutionin morethan

92 %ofallruns. Theroutinggraphofa macro-cellplacementwithC cells

will haveless than3C vertices. It is thereforemost likelythat theGA

will ndtheshortestexistingroutefor everynetinanyreasonablysized

macro-cell layout. Thesecondadvantageof theGAis that it provides

anumber of distinctsolutionsinasinglerun. Theproblemof Mercury

andTimberWolfMCthatonlyonerouteisgeneratedfornetswithmany

terminalsisthus eliminated.

Fornetswithfewterminals, say6-7orless, exhaustivesearchforthe

shortestroutewill oftenbefeasible. UsinganalgorithmbySullivan[9]

optimumcanbefoundbyexhaustingasearchspaceconsistingof

k

X

i =0 0

@ n

i 1

A

points, wherek =min(t02; n) andt is thenumber of terminals of the

FigureD.2: Addition of terminal vertic es (shade d) for a net with thre e

terminal s (marke d with crosses).

Fig.D.3outlinesphaseone. Anetistrivial ifall itsterminalsarepro-

jectedontothesameedgeof theroutinggraph. Althoughseveral routes

canstill begeneratedfor atrivial net, it will rarelybeadvantageous.

Hence, global routingisskippedforsuchnets.

generateroutinggraph

foreachnon-trivial netdo:

addverticestograph

if 2-terminal net :

applyLawlersalgorithm

else

applyaGAforSPG

end

removeverticesfromgraph

end

FigureD.3: Outl ine of phase one.

TheSPGis ingeneral NP-complete. However, if onlytwovertices

aretobeconnected, SPGreduces toashortest pathproblem, whichis

handledbyanalgorithmof Lawlerdiscussed inSectionD.2.1. Netswith

computingacorrespondingpathintheroutinggraph.

Aquitedetaileddescriptionof howtogeneratetheroutinggraphfor

agivenplacement is givenin[7]. Roughlyspeaking, eachedgeof the

graphcorrespondstoaroutingchannel andeachvertexcorresponds to

theintersectionof twochannels. AnexampleisshowninFig. D.1.

FigureD.1: Apl ac ement and the c orresponding routing graph.

Beforendingroutesfor agivennet, verticesrepresentingthetermi-

nalsof thenet areaddedtotheroutinggraphat appropriatelocations.

Findingtheshortestrouteforthenetisthen equivalentofndingamin-

imumcost subtreeinthegraphwhichspans all of theaddedterminal

vertices, assumingthat thecostof anedgeisdenedasitslength. This

problemis knownas theSteiner ProbleminaGraph(SPG). Whena

nethasbeentreated, itsterminal verticesareremovedfromtherouting

graphbeforeconsideringthenextnet, therebysignicantlyreducingthe

sizeof theSPGinstancestobesolved.

Foreachterminal thelocationofthecorrespondingterminal vertexis

determinedbyaperpendicular projectionof theterminal ontotheedge

representingtheappropriateroutingchannel, as illustratedinFig. D.2.

This is incontrast tothe strategyusedine.g. [7]. Here vertices are

addedonlyat thecenter of routingchannels andeachterminal is then

assignedtotheclosestvertex. Thisschememayresultinsomenetshaving

identical setsof terminal vertices, inwhichcasesomecomputations can

beavoided. Ontheother hand, our schemeprovides amore accurate

estimateofthewirelengthandalsoallowsamoreaccurateareaestimate

asdiscussedinSectionD.3.1.

D. 1 Introducti on

Awell-knownstrategyfor global routingof macro-cell layouts consists

of twophases [10]. Inthe rst phase, anumber of alternativeroutes

aregeneratedfor eachnet. Thenets aretreatedindependentlyoneat

atime, andtheobjectiveis tominimizethelengthof eachnet. Inthe

secondphase, aspecicrouteisselectedforeachnet, subjecttochannel

capacityconstraints, andsothatsomeoverall criterion, typically areaor

total interconnectlength,isminimized. Amainadvantageofthisrouting

strategyisitsindependenceof anetordering.

Mercury[7] and TimberWolfMC[8] arestateof theartglobal routers

for macro-cell layouts, andbothare basedonthe two-phasestrategy.

For nets withasmall number of terminals, theserouters generate up

to 10020alternativeroutes for eachnet. However, due to the time

complexity oftheappliedalgorithms, onlyasinglerouteisgeneratedfor

nets havingmorethan50 11terminals. As notedin[8] this limits the

overall qualityobtainable.

Inthis paper anewglobal router is presentedwhichminimizesarea

andsecondarily, total interconnect length. Whilealsobeingbasedon

thetwo-phasestrategy, thisrouterdierssignicantlyfrompreviousap-

proachesintwoways:

1)Each phaseisbasedonageneticalgorithm(GA). TheGAusedin

phaseoneprovidesseveralhigh-qualityroutesforeachnetindependently

of its numberof terminals. Inthesecondphaseanother GAminimizes

thedual optimizationcriterionbyappropriately selectingaspecicroute

for eachnet.

2)Theestimatesof areaandtotal interconnectlengthusedthrough-

out the optimizationprocess arecalculatedveryaccurately. The area

estimateisbased on computation ofchannel densitiesand thewirelength

estimateisbasedonexactpinlocations.

Experimental results shows that thelayout qualityobtainedbythe

router comparesfavourablytothatof TimberWolfMC.

D. 2 Phase One of the Router

Beforetheglobal routingprocess itself is initiatedarectilinear routing

graph isextractedfromthegivenplacement. Routingisthenperformed

Appendix D

AMacro-Cell Global Router Based

onTwoGenetic Algorithms

This paper is publishedas H. Esbensen, \AMacro-Cell Global Router

BasedonTwoGeneticAlgorithms,"Proc. of The European Design Au-

tomation Conferenc e, pp. 428-433, Sept. 1994.

Abstract

Thispaperpresentsanovelapproachtoglobal routingofmacro-cell lay-

outs. Ageneticalgorithmgenerates several short routes for eachnet.

Another geneticalgorithmthenselectsaroutefor eachnet whilemini-

mizingareaand secondarily interconnectlength. Exactchannel densities

areusedfor areaestimation. The layout qualityobtainedonMCNC

benchmarkscomparesfavourablytothat of TimberWolfMC.

[27] H. Takahashi, A. Matsuyama, \AnApproximateSolutionfor the

Steiner ProbleminGraphs", Mathematic a Japonic a, Vol. 24, No. 6,

pp. 573-577, 1980.

[28] R. Venkateswaran, P. Mazumder, \RoutingAlgorithmsinSemicon-

ductorCircuitDesign,"Inpreparation, 1993.

[29] Darrell Whitley, \The Genitor AlgorithmandSelectionPressure:

WhyRank-BasedAllocationof Reproductive Trials is Best,"Pro-

c e e dings of the 3th International Conferenc e on Genetic Al gorithms,

pp. 116-121, 1989.

[30] PawelWinter, \SteinerProbleminNetworks: ASurvey,"Networks,

Vol. 17, pp. 129-167, 1987.

[31] Pawel Winter, J. MacGregor Smith, \Path-DistanceHeuristics for

theSteiner ProbleminUndirectedNetworks,"Al gorithmic a, Vol. 7,

pp. 309-327, 1992.

[13] S. L. Hakami, \Steiner's problemingraphs andits implications,"

Networks, Vol. 1, pp. 113-133, 1971.

[14] M. Hanan, \OnSteiner'sProblemwith RectilinearDistance," SIAM

Journal of Appl ie d Mathematics, Vol. 14, No. 2, pp. 255-265, 1966.

[15] J. Hesser, R. Manner, O. Stucky, \Optimizationof Steiner Trees

usingGeneticAlgorithms,"Proce edings of the 3th International Con-

ferenc e on Genetic Al gorithms, pp. 231-236, 1989.

[16] JohnH. Holland, Adaption in Natural and Articial Systems, Uni-

versityof MichiganPress, AnnArbor, MI., 1975.

[17] Bryant A. Julstrom, \AGenetic Algorithmfor the Rectilinear

Steiner Problem," Proc ee dings of the 5th International Conferenc e

on Genetic Al gorithms, pp. 474-480, 1993.

[18] A.Kapsalis,V.J.Rayward-Smith,G.D.Smith, \SolvingtheGraph-

ical SteinerTreeProblemUsingGeneticAlgorithms,"Journal of the

Operational Rese arch Society, Vol. 44, No. 4, pp. 397-406, 1993.

[19] R. M. Karp, \Reducibility among Combinatorial Problems," In

R. E. Miller, J. W. Thatcher (Eds.), Compl exity of Computer Com-

putations, PlenumPress, NewYork, pp. 85-103, 1972.

[20] L. Kou, G. Markowsky, L. Berman, \AFast Algorithmfor Steiner

Trees,"Acta Informatic a, Vol. 15, pp. 141-145, 1981.

[21] E. L. Lawler, Combinatorial Optimization: Networks and Matroids,

Holt, RinehartandWinston, NewYork, 1976.

[22] J.vanLeeuwen,\GraphAlgorithms," in: J.vanLeeuwen,ed.,Hand-

b ook of The oretic al Computer Scienc e, Vol. A: Al gorithms and Com-

pl exity, Elsevier, Amsterdam, 1990.

[23] A.Lucena, J.E.Beasley,\AbranchandcutalgorithmfortheSteiner

problemingraphs,"workingpaper, TheManagementSchool, Impe-

rial College, England, July1992.

[24] J. Plesnik, \AboundfortheSteinertreeproblemingraphs,"Math.

Sl ovac a, Vol. 31, pp. 155-163, 1981.

[25] V. J. Rayward-Smith, A. Clare, \On nding Steiner vertices,"

Networks, Vol. 16, pp. 283-294, 1986.

[26] M. L. Shore, L. R. Foulds, P. B. Gibbons, \Analgorithmfor the

Bibliography

[1] A. V. Aho, J. E. Hopcroft, J. D. Ullman, Data Structures and Al go-

rithms, Addison-Wesley, Reading, Mass, 1983.

[2] Y. P. Aneja, \An Integer Linear Programming Approach to the

SteinerProbleminGraphs,"Networks, Vol. 10, pp. 167-178, 1980.

[3] J. E. Beasley, \AnSST-BasedAlgorithmfor theSteiner Problemin

Graphs,"Networks, Vol. 19, pp. 1-16, 1989.

[4] J. E. Beasley, \OR-Library: distributing test problems by elec-

tronic mail,"Journal of the Operational Rese arch Society, Vol. 41,

pp. 1069-1072, 1990.

[5] Sunil Chopra, EdgarR. Gorres, M. R. Rao, \SolvingtheSteinerTree

ProblemonaGraphUsingBranchandCut,"Operations Rese arch

Society of Americ a Journal of Computing, Vol. 4, No. 3, pp. 320-335,

1992.

[6] R. Dionne, M. Florian, \ExactandApproximateAlgorithmsforOp-

timal NetworkDesign,"Networks, Vol. 9, pp. 37-59, 1979.

[7] K. A. Dowsland, \Hill-climbingsimulatedannealingandtheSteiner

problemingraphs,"Eng. Opt., Vol. 17, pp. 91-107, 1991.

[8] S. E. Dreyfuss, R. A. Wagner, \The Steiner problemingraphs,"

Networks, Vol. 1, pp. 195-207, 1971.

[9] C. W. Duin, A. Volgenant, \ReductionTestsfortheSteinerProblem

inGraphs,"Networks, Vol. 19, pp. 549-567, 1989.

[10] L. R. Foulds, V. J. Rayward-Smith, \Steiner problems ingraphs:

algorithmsandapplications,"Eng. Opt. Vol. 7, pp. 7-16, 1983.

[11] M. R. Garey, D. S. Johnson, \The Rectilinear Steiner TreeProb-

lemisNP-complete," SIAMJournal of Appl ie d Mathematics, Vol. 32,

No. 4, pp. 826-834, 1977.

[12] D. E. Goldberg, Genetic Al gorithms in Se arch, Optimization, and

Cost CPU-time (secs)

Graph C

opt C

sph 1C

sph C

g a 1C

ga

T

bc1 T

bc2 T

sph T

ga

E-1 111 111 0 111 0 1,150 1,394 7,334 7,395

E-2 214 216 0.93 216 0.93 6,251 1,993 7,355 7,444

E-3 4,013 4,060 1.17 4,013 0 26,468 15,782 50,004 9,449

E-4

5,101 5,113 0.24 5,102 0.02 46,008 1,660 29,921 7,763

E-5

8,128 8,134 0.07 8,128 0 12,564 411 9,318 7,474

E-6 73 76 4.11 73 0 678 - 10,060 10,148

E-7 145 149 2.76 145 0 27,124 - 10,306 10,458

E-8

2,640 2,690 1.89 2,646 0.23 118,618 - 50,013 12,896

E-9 3,604 3,671 1.86 3,611 0.19 24,528 - 50,014 14,933

E-10 5,600 5,624 0.43 5,600 0 39,261 - 50,014 12,976

E-11

34 34 0 34 0 1,901 - 14,472 14,559

E-12 67 68 1.49 68 1.49 7,200 - 14,497 14,588

E-13

1,280 1,317 2.89 1,289 0.70 207,059 - 50,003 21,787

E-14

1,732 1,767 2.02 1,736 0.23 29,263 - 50,030 23,022

E-15 2,784 2,795 0.40 2,784 0 7,666 - 50,020 18,424

E-16 15 15 0 15 0 179 - 14,425 14,586

E-17

25 25 0 25 0 36,040 - 14,458 14,619

E-18 572 625 9.27 583 1.92 - - 50,017 29,105

E-19 758 802 5.80 766 1.06 6,372 - 50,037 27,319

E-20

1,342 1,357 1.12 1,342 0 272 - 50,055 25,107

TableC.12: Comparison of sol ution qual ity and CPU-time for the graphs

in cl ass E.

Graph

T

bc1

T

bc2 T

sph T

av g T

D-1 476 200 486 523 8

D-2 284 148 488 537 13

D-3

2,290 106 785 650 39

D-4 3,529 41 689 554 21

D-5 811 37 522 504 8

D-6

2,340 4,148 687 788 44

D-7

100 1,037 681 795 29

D-8 6,985 17,858 13,237 2,101 381

D-9 4,630 16,458 29,354 2,744 624

D-10 1,312 1,678 14,780 1,100 169

D-11 1,374 24,609 949 1,070 59

D-12

305 5,843 961 1,085 20

D-13

1,864 91,718 15,187 2,357 245

D-14 3,538 61,335 41,237 2,601 393

D-15 1,410 16,889 24,828 1,302 102

D-16 871 9,721 956 1,047 21

D-17 6,965 147,598 950 1,068 26

D-18 245,192 227,841 31,015 2,536 491

D-19

878 304,380 50,003 3,441 580

D-20 47 1,276 50,010 2,638 658

TableC.10: Comparisonof CPU-time (se c onds) for the graphs incl ass D.

Problemsize Reducedsize

Graph

n m jEj n m jEj

E-1 2,500 5 3,125 680 5 1,286

E-2

2,500 10 3,125 710 9 1,328

E-3

2,500 417 3,125 637 199 1,233

E-4 2,500 625 3,125 435 164 964

E-5 2,500 1,250 3,125 222 108 649

E-6 2,500 5 5,000 1,845 5 4,318

E-7 2,500 10 5,000 1,891 10 4,372

E-8

2,500 417 5,000 1,723 286 4,193

E-9

2,500 625 5,000 1,608 358 4,069

E-10 2,500 1,250 5,000 1,046 366 3,388

E-11 2,500 5 12,500 2,498 5 12,093

E-12

2,500 10 12,500 2,500 10 12,123

E-13 2,500 417 12,500 2,341 321 11,760

E-14 2,500 625 12,500 2,139 388 11,325

E-15

2,500 1,250 12,500 1,461 443 8,514

E-16 2,500 5 62,500 2,500 5 29,332

E-17

2,500 10 62,500 2,500 10 29,090

E-18

2,500 417 62,500 2,429 355 28,437

E-19 2,500 625 62,500 2,351 485 27,779

E-20 2,500 1,250 62,500 1,988 758 24,423

Problemsize Reducedsize

Graph n m jEj n m jEj

D-1

1,000 5 1,250 274 5 510

D-2

1,000 10 1,250 285 10 523

D-3 1,000 167 1,250 224 67 441

D-4 1,000 250 1,250 159 66 339

D-5 1,000 500 1,250 97 48 246

D-6 1,000 5 2,000 761 5 1,741

D-7 1,000 10 2,000 754 10 1,735

D-8

1,000 167 2,000 731 124 1,708

D-9 1,000 250 2,000 654 155 1,613

D-10

1,000 500 2,000 418 146 1,317

D-11

1,000 5 5,000 993 5 4,674

D-12 1,000 10 5,000 1,000 10 4,671

D-13 1,000 167 5,000 922 122 4,433

D-14 1,000 250 5,000 853 160 4,173

D-15 1,000 500 5,000 550 157 2,925

D-16

1,000 5 25,000 1,000 5 10,595

D-17

1,000 10 25,000 999 9 10,531

D-18 1,000 167 25,000 978 145 10,140

D-19 1,000 250 25,000 938 193 9,676

D-20

1,000 500 25,000 814 324 8,907

TableC.8: The cl ass Dgraphs b efore and after re ductions.

Graph C

o pt C

sph 1C

sph C

best C

avg C

w o r st C

1C

avg 1C

wo rst N

ga

D-1

106 106 0 106 106 106 0 0 0 0

D-2 220 220 0 220 220 220 0 0 0 0

D-3 1,565 1,570 0.32 1,565 1,565 1,565 0 0 0 0

D-4

1,935 1,940 0.26 1,935 1,935 1,935 0 0 0 0

D-5 3,250 3,254 0.12 3,250 3,250 3,250 0 0 0 0

D-6 67 71 5.97 67 67.1 68 0.3 0.15 1.49 1

D-7 103 103 0 103 103 103 0 0 0 0

D-8 1,072 1,095 2.15 1,072 1,072.7 1,074 0.6 0.07 0.19 6

D-9 1,448 1,471 1.59 1,448 1,448.4 1,450 0.7 0.03 0.14 3

D-10

2,110 2,120 0.47 2,110 2,110 2,110 0 0 0 0

D-11

29 29 0 29 29 29 0 0 0 0

D-12 42 42 0 42 42 42 0 0 0 0

D-13 500 514 2.80 500 500.6 502 0.7 0.12 0.40 5

D-14 667 675 1.20 668 669.7 671 0.9 0.40 0.60 10

D-15 1,116 1,121 0.45 1,116 1,116 1,116 0 0 0 0

D-16

13 13 0 13 13 13 0 0 0 0

D-17

23 23 0 23 23 23 0 0 0 0

D-18 223 239 7.17 226 227.7 230 1.2 2.11 3.14 10

D-19 310 335 8.06 312 313.3 315 0.9 1.06 1.61 10

D-20

537 539 0.37 537 537 537 0 0 0 0

Graph C

o pt C

sph 1C

sph C

best C

avg C

wo rst C

1C

avg 1C

wo rst N

ga

C-1 85 85 0 85 85 85 0 0 0 0

C-2

144 144 0 144 144 144 0 0 0 0

C-3

754 757 0.40 754 754.2 755 0.4 0.03 0.13 2

C-4 1,079 1,081 0.19 1,079 1,079.1 1,080 0.3 0.01 0.09 1

C-5 1,579 1,579 0 1,579 1,579 1,579 0 0 0 0

C-6 55 55 0 55 55 55 0 0 0 0

C-7 102 102 0 102 102 102 0 0 0 0

C-8

509 512 0.59 509 509 509 0 0 0 0

C-9

707 714 0.99 707 707.4 708 0.5 0.06 0.14 4

C-10 1,093 1,098 0.46 1,093 1,093 1,093 0 0 0 0

C-11 32 32 0 32 32 32 0 0 0 0

C-12

46 46 0 46 46 46 0 0 0 0

C-13 258 263 1.94 258 259.7 260 0.6 0.66 0.78 9

C-14 323 327 1.24 323 323.4 324 0.5 0.12 0.31 4

C-15

556 558 0.36 556 556 556 0 0 0 0

C-16 11 11 0 11 11.7 12 0.5 6.36 9.09 7

C-17

18 18 0 18 18 18 0 0 0 0

C-18

113 121 7.08 113 114.3 115 0.8 1.15 1.77 8

C-19 146 155 6.16 146 147 148 0.4 0.68 1.37 9

C-20 267 267 0 267 267 267 0 0 0 0

TableC.6: Comparison of sol ution qual ity for the graphs in cl ass C.

Graph T

bc1 T

bc2 T

sph T

avg T

C-1

27 25 61 79 6

C-2 812 45 61 79 3

C-3 543 25 72 104 19

C-4

510 23 75 83 10

C-5 474 5 61 63 0

C-6 49 561 83 130 11

C-7

83 522 86 153 24

C-8

674 1,106 260 263 39

C-9 1,866 5,813 966 425 93

C-10 246 32 544 181 49

C-11 333 2,769 119 187 20

C-12 120 1,175 119 224 19

C-13

9,170 9,895 646 544 91

C-14

212 1,150 1,316 547 130

C-15 211 913 1,544 262 56

C-16 10 877 119 180 22

C-17

98 14,557 119 203 26

C-18 45,848 20,726 873 563 102

C-19 117 1,689 3,050 601 136

C-20

15 225 11,374 334 57

Graph T

bc2 T

sph T

avg T

B-1

0.1 0.1 0.1 0.0

B-2 0.1 0.1 0.2 0.0

B-3

0.1 0.1 0.1 0.0

B-4 0.6 0.1 1.2 0.6

B-5 1.9 0.1 0.7 0.2

B-6

0.6 0.1 0.7 0.1

B-7 0.2 0.2 0.5 0.1

B-8 0.1 0.2 0.5 0.1

B-9

0.1 0.2 0.2 0.0

B-10

3.1 0.3 1.7 0.5

B-11 1.4 0.3 1.4 0.6

B-12 0.6 0.3 0.6 0.1

B-13 0.7 0.4 1.4 0.4

B-14 1.2 0.5 0.9 0.3

B-15

0.3 0.5 0.8 0.1

B-16

18.4 0.6 4.4 1.9

B-17 3.3 0.6 2.3 0.6

B-18 1.0 0.6 1.5 0.3

TableC.4: Comparisonof CPU-time (se c onds) for the graphs in cl ass B.

Problemsize Reducedsize

Graph

n m jEj n m jEj

C-1 500 5 625 145 5 263

C-2 500 10 625 130 8 239

C-3

500 83 625 120 35 232

C-4 500 125 625 109 38 221

C-5 500 250 625 37 17 91

C-6

500 5 1,000 369 5 847

C-7

500 10 1,000 382 9 869

C-8 500 83 1,000 336 54 818

C-9 500 125 1,000 349 78 832

C-10 500 250 1,000 213 76 624

C-11 500 5 2,500 499 5 2,184

C-12

500 10 2,500 498 9 2,236

C-13

500 83 2,500 463 65 2,108

C-14 500 125 2,500 427 81 1,961

C-15 500 250 2,500 299 92 1,471

C-16

500 5 12,500 500 5 4,740

C-17 500 10 12,500 499 9 4,698

C-18 500 83 12,500 486 70 4,668

C-19

500 125 12,500 473 98 4,490

C-20 500 250 12,500 386 143 3,850

C. 7 Computati onal Resul ts

Problemsize Reducedsize

Graph

n m jEj n m jEj

B-1 50 9 63 1 1 0

B-2

50 13 63 7 4 12

B-3 50 25 63 1 1 0

B-4

50 9 100 34 7 72

B-5

50 13 100 35 10 76

B-6 50 25 100 25 10 60

B-7 75 13 94 16 6 26

B-8 75 19 94 16 7 25

B-9 75 38 94 1 1 0

B-10 75 13 150 50 10 115

B-11

75 19 150 47 8 108

B-12 75 38 150 31 11 74

B-13 100 17 125 28 9 47

B-14

100 25 125 22 8 42

B-15 100 50 125 16 9 28

B-16 100 17 200 63 9 148

B-17

100 25 200 51 12 113

B-18 100 50 200 35 12 84

TableC.2: The cl ass Bgraphs b efore and after re ductions.

Graph C

o pt C

sph 1C

sph C

best C

avg C

wo rst C

1C

avg 1C

wo rst N

ga

B-1 82 82 0 82 82 82 0 0 0 0

B-2 83 83 0 83 83 83 0 0 0 0

B-3

138 138 0 138 138 138 0 0 0 0

B-4 59 59 0 59 59 59 0 0 0 0

B-5 61 61 0 61 61 61 0 0 0 0

B-6

122 122 0 122 122 122 0 0 0 0

B-7

111 111 0 111 111 111 0 0 0 0

B-8 104 104 0 104 104 104 0 0 0 0

B-9 220 220 0 220 220 220 0 0 0 0

B-10 86 86 0 86 86 86 0 0 0 0

B-11 88 88 0 88 88 88 0 0 0 0

B-12

174 174 0 174 174 174 0 0 0 0

B-13

165 168 1.82 165 165 165 0 0 0 0

B-14 235 235 0 235 235 235 0 0 0 0

B-15

318 318 0 318 318 318 0 0 0 0

B-16 127 127 0 127 127 127 0 0 0 0

B-17 131 131 0 131 131 131 0 0 0 0

B-18 218 218 0 218 218 218 0 0 0 0

C. 6 Concl usi on

InthispaperanewGeneticAlgorithm(GA)for theSteinerProblemin

aGraph(SPG)hasbeen presented. Themain ideabehind thealgorithm

istheapplication oftheDistanceNetworkHeuristicforinterpretationof

bitstrings specifyingselectedSteiner vertices. This schemeensures that

everybitstringcorrespondstoavalidsolutionandeliminatestheneedfor

penaltyterms inthecost measure, therebyavoidingpotential problems

of assigningasuitablecostvaluetoanincompleteorinvalidsolution.

Theperformanceof thealgorithmhasbeentestedonrandomgraphs

withupto2,500vertices and62,500edges. The experimental results

shows that inmorethan92%of all executionstheGAnds asolution

whichis within1%fromtheglobal optimum. This performancecom-

paresfavorablywithoneoftheverybestdeterministicheuristicsforSPG

aswellaswithanearlierGAbyKapsalisetal. Performanceisalsocom-

paredtothat of branch-and-cutalgorithms byLucenaandBeasleyand

by Chopraetal. Whiletheruntimesofthesealgorithmsvariesextremely

andprevents thesolutionof someof theprobleminstances considered,

theGAiscapableof generatinganear-optimal solutionfor all problems

withinamoderateamountof time.

Wethereforeconcludethefollowing: Incaseswhereagloballyoptimal

solutionisabsolutelyrequired, thesizeof thegivenproblemis not too

bigandruntimeisnotimportant, oneof thebranch-and-cut algorithms

arepreferable. Ontheotherhand, ifanear-optimal solution issucient,

or theproblemis verylargeor amoderateruntimelimitis needed, the

GApresentedhereisthebestchoiceof thepossibilitiesconsidered.

Acknowl edgement

Theauthor wishes tothankPinaki Mazumder, Universityof Michigan,

whosupervisedthis workinits initial phasewhenthe author was at

Universityof Michigan. AlsothankstoJensClausenandPawel Winter,

CopenhagenUniversity,forpointing outpossibleimprovementsofanear-

lierversionofthealgorithmandforsuggesting asuitablestrategyforper-

formanceevaluation. Finallythanksto PeterMller-Nielsen,OleCaprani

andHolger Orup, Aarhus University, for several useful discussions and

0.42 0.44 0.46 0.48 0.5 0.52 0.54 0.56 0.58

0 50 100 150 200 250 300 350 400

Percentage new individuals

Generation

FigureC.10: Perc entage of newindividual s inthe popul ationas a function

of generation numb er.

C. 5 Future Work

Theworkpresentedherecanbecontinuedinatleastthreedirections:

1) Performanceimprovement: As discussedinSectionC.3themain

ideaof theGApresentedistheapplicationof theDNHforinterpretation

of bitstrings. Incontrast, thegeneticoperators for crossover, mutation

andinversionare all standard. Theyare characterizedbybeingvery

simpleandblindinthesensethat theydonot utilizeknowledgeof the

applicationdomaininanyway. Thesameistrueforthehill-climber. One

frequentlyusedwayof improvingtheperformanceof aGAis toapply

moreadvancedgeneticoperatorsand/oroperatorsexploitingapplication

specicknowledge[12]. Itisthereforelikelythat theperformanceof the

GApresentedherecan befurtherimprovedbyapplyingsuchtechniques.

2) Other graphtypes: Anobviousweaknessof thetest-suiteusedin

thisworkisthatallgraphsaresparseandrandomlygenerated. Itremains

tobeseenhowtheGAperformsone.g. densegraphs, rectilineargraphs,

non-randomgraphsarisinginreal-worldapplications, etc.

3)Contributionstoperformance: Toobtainadetailed understanding

of thereasonsforthesuccessof thealgorithmit wouldbeinterestingto

investigatehowthevarious components of thealgorithmcontributeto

theoverallperformance. Whatistheindividualeecton solutionquality

andruntimecausedbye.g. thedecodingstrategy, theinversionoperator,

However, theusedstopcriteriareects apriorityof solutionqualityas

beingmoreimportantthanruntime.

Fig. C.9shows for eachgenerationthe standarddeviationof cost

inthe population. Fromavalueof 19.2ingeneration0, thestandard

deviationdecreaseswithin10generationstoabout2.0andthenstaysat

that level throughout theoptimizationprocess.

0 2 4 6 8 10 12 14 16 18 20

0 50 100 150 200 250 300 350 400

Standard deviation

Generation

FigureC.9: Standard deviation of c ost as a function of generation num-

b er.

AsdescribedinSectionC.3.1each generationisinitiatedbythegen-

erationof Mospringindividuals. Fromthetotal of2Mindividualsthe

bestMindividualsarethenkeptasmembersofthenewpopulationwhile

therestarediscarded. Fig.C.10 showsforeachgenerationthepercentage

of individualsin thenewlycreated populationwhich hasjustemerged as

results of crossover. The percentageof newlygeneratedindividuals is

verystablearound50. Theimportantthingtonoteisthat thefraction

of newindividuals donot decreasewithtimebut is constant alsointo

the latephaseof the process. Inother words, throughout the process

half theindividualsgeneratedbythecrossoveroperatorarebetter than

someother individual alreadyinthepopulation. This conrms therole

of crossoverasthemostimportantof thegeneticoperators.

believethatthemain reason fortheperformancegap betweenGA-KRSS

andtheGApresentedhereisthedierentdecodingstrategyandconse-

quently, thedierentcostevaluationstrategy.

C.4.6 Typical Behavior

Theprogress of the typical optimizationprocess is illustratedbyFig-

uresC.8, C.9andC.10, whichstemsfromasampleexecutionof theGA

withgraphD-15as input. It shouldbeemphasizedthat althoughthe

graphs stems fromaspecic singlerun, the picture theygive is very

typical.

1110 1120 1130 1140 1150 1160 1170 1180 1190 1200

0 50 100 150 200 250 300 350 400

Cost

Generation

Average Best

FigureC.8: Cost of average and b est individual as functions of generation

numb er.

For eachgeneration, thetopgraphof Fig. C.8indicatestheaverage

costof theindividualsinthepopulationat that time, whilethebottom

graphindicates the cost of the current best individual. Initially, the

averagecostis1,197andthebestis1,156. Theglobal optimumof 1,116

is obtainedrst timeingeneration203, andthe algorithmterminates

after 358generations. Notethat improvement is veryrapidduringthe

rst part of the process. Thenit levels out andfurther improvement

isobtainedonlyslowly. As mentionedinSectionC.3.1thebestas well

as the average cost are parts of the stopcriteria. If onlythe cost of

the best solutionwere considered, the process wouldhaveterminated

AsproblemsizeincreasesthroughtheclassesB,C, DandEtheabove

observationsbecomeincreasinglypronounced. IfonlyclassBgraphsare

considered, itisdiculttomakeanydistinctionsregardingperformance

of thealgorithms. Theseexamplesappearstobetoosimple.

C.4.5 ComparisonwithKapsalis Algorithm

Inthis SectiontheGAbyKapsalis, Rayward-SmithandSmith[18] is

denotedGA-KRSS. AsmentionedinSectionC.1GA-KRSSdiersfrom

theGApresentedhereinanumberofways. Amongotherthings, neither

aninversionoperatornorahill-climberisappliedinGA-KRSS. However,

themost signicant dierencesconcerns thedecoder andthecost com-

putation. InGA-KRSSagenotypeis abitstringof lengthn inwhich

thei 'thbitindicatesif thei 'thvertexispartof thephenotypetree. To

assurethat everytreespans W eachgenotypeis xor'edwiththexed

stringspecifyingW. Hence,theencodingisverysimilartoourencoding.

However, the interpretationof agenotypeis verydierent. Assumea

genotypespecies thevertexset Z, W Z V. Thecorresponding

graphisthencomputedas thesubgraphG

Z

of G inducedbyZ. Ingen-

eral G

Z

isnot connected. Assumeitconsistsof k 1components. The

costofasolutionisdenedasthesumofthecostofaminimumspanning

treeforeachcomponentplusapenaltytermwhichgrowslinearlywith k .

Computational resultsaregivenonlyfortheclassBgraphs fromthe

OR-Library. The solutionqualityobtainedfor eachgraphis reported

as thebest result of veruns. For eachgraphsome parameter setting

of GA-KRSShas beenfoundwithwhichthe global optimumis found

inveruns. However, the parameter settingvaries withtheproblems

given. Whenxingtheparametersettingforall graphs, GA-KRSSnds

theglobaloptimuminapproximately70 %ofallrunsandtheworstresult

generatedis7.3%abovetheglobal optimum.

All experiments withGA-KRSSare runonaApple MacIIfx. No

total runtimesaregiven. Insteadthetimespenduntil thebest solution

foundappearsrsttime, referredtoasLastImprovementTime(LIT), is

measured. Itisnotclearexactlywhichstopcriteriaisused, i.e.,howlong

thealgorithmtakestoterminatebeyondLIT. For manyof thegraphs,

theaverageLITis intherangefrom200to2,000secs. Thereis atime

limitof 4,000secs. foracompleteexecution.

GA-KRSSisclearlyinferiortoeachoftheotheralgorithmsconsidered

For theclassEexamples, SPH-I nds optimumfor 4of the20graphs,

whiletheGAndstheoptimumfor11ofthesegraphs. 1C

w orst

1C

sph

holdsforall butonegraphinclassesB, CandD, andinclassEwehave

1C

g a

1C

sph

forallgraphs. Inotherwords,withasingleexceptioneven

theworst results generatedbytheGAareequal toor better thanthe

resultgeneratedbySPH-I.Furthermore,forthegraphswherebothSPH-I

andtheaverageexecutionof theGAfails tondtheglobal optimum,

theexpectedrelativeerror ratio1C

avg

of the GAis oftenanorder of

magnitudebetterthantheerror ratio1C

sph

of SPH-I.

ErrorRatio

Algorithm =0% < 0.5% < 1.0%

SPH-I

48.7 66.7 70.5

GA 77.1 86.7 92.6

TableC.1: Summary of sol ution qual ities obtaine d by the GAand SPH-I.

TableC.1summarizesthesolutionqualitiesobtainedbytheGAand

theSPH-I. Thesegures arebasedontheresults of all 600executions

of theGAandall 78executions of SPH-I performedintotal. For each

algorithmTableC.1givestheaccumulatedpercentageofrunswhichgave

aresult withinthestatedrelativeerror fromoptimum. E.g., 66.7%of

all executionsof theSPH-Igavearesultwhichwaslessthan0.5%from

theoptimumsolution. Whencomputingthevalueslisted fortheGAthe

resultsfortheclassEexampleshavebeenweightedbyafactor of 10to

compensatefortheimbalanceinthenumberofexecutionsforeachgraph.

The results regarding runtimes can be summarizedinthree main

points:

TheGAiscapableof ndingahigh-qualitysolutionfor al l graphs

consideredinamoderateamountof time. Thisisnot thecasefor

anyof thetwobranch-and-cutalgorithmsor for SPH-I.

InmostcasestheruntimeoftheGAisverysimilartothatofSPH-I.

InafewcasestheGAissignicantlyfasterthanSPH-I, whilethe

oppositeisneverthecase.

Thevariationof theruntimeof theGAisverysmall comparedto

the variationobservedfor the branch-and-cut algorithms as well

as SPH-I. As aconsequence, the branch-and-cut algorithms are

signicantlyfasterthanboththeGAandSPH-Iforsomeexamples,

TableC.12lists thesolutionqualities obtainedbythe GAandthe

SPH-I together withtheruntimes of all algorithms considered. Dueto

theextensiveruntimesrequiredforthegraphsinthis class, theGAwas

executedonlyoncefor eachexample. C

ga

denotes thecost obtainedby

theGA, 1C

ga

istherelativeerror of thesolutionfoundbytheGAand

thetimespendbyalgorithmisdenotedbyT

ga

. Hence, C

ga andT

ga can

beconsideredestimatesof C

avg

andT

avg

, respectively.

It shouldbenotedthat thelistedvalueof C

opt

for E-18maynot be

theglobal optimum, but accordingtotheinformationinOR-Libraryit

is thebestknownsolutionas foundbyBeasley'salgorithm[3]. Theop-

timumfor this graphwas not foundwithinacpu-limit of 21,600secs

ontheCrayX-MP/48. Chopraetal [5] alsoencounteredproblemswith

E-18. Noruntime is listedfor this graphsincethe algorithmdidnot

terminatewithinacpu-limit of 10days ontheVAX8700[5]. Lucena

and Beasley[23] doesnotreportany resultsforgraphsE-6throughE-20,

andareasonis not given. However, consideringtheprogressionof run-

timefor thegraphs inclasses CandD, it is reasonabletoassumethat

thealgorithmisunabletosolvesomeof theseproblemsinareasonable

amountof time.

SPH-Iexceedsthecpu-timelimitof 50,000secs. for graphsE-3, E-8,

E-9, E-10, E-13, E-14, E-15, E-18, E-19andE-20. Theestimatedtotal

timerequiredbySPH-Iforthesegraphsvariesfrom81,000secs. forE-3

to4: 3 210 7

secs., or morethan16months, for E-20. Comparedtothe

branch-and-cut algorithms andSPH-I theruntimes of theGAarevery

moderateforallgraphswithamaximumruntimeof29,105 secs. forE-18.

For most of thegraphs for whichSPH-I terminateswithinthecpu-time

limit the runtimes of the GAandSPH-I are verysimilar. Regarding

solutionquality, SPH-Indstheglobal optimumfor4of thegraphsand

has aworst relativeerror ratioexceeding9%for E-18. TheGAnds

optimumfor11graphsandhasaworstrelativeerrorratiolessthan2%.

C.4.4.5 Summary of Results

Thissectionsummarizestheexperimentalresultswithrespecttosolution

qualityandruntime. Whencomparingthesolutionqualityobtainedby

theGAtothat obtainedbySPH-I for all graphs inclassesB, CandD

thefollowingcanbeobserved: Of atotal of 58graphs, SPH-I nds the

global optimal solutionfor 34graphs, whiletheGAnds optimum10

vertexdegreeincreases.

OntheclassDgraphsSPH-Indsoptimumfor7of thegraphs, while

theGAndstheoptimumatleastoncefor17graphsandeverytimefor

13graphs. SPH-I has relativeerrors exceeding2%for 5graphs while

that onlyhappens for theGAongraphD-18. For all graphs wehave

C

worst

C

sph

andC

worst

<C

sph

holdsfor13graphs.

Onthis class of problems theruntimes for bothbranch-and-cut al-

gorithms variesbythreeorders of magnitudeandareas highas inthe

200-300,000secs. rangecorrespondingto2-3days of computation. The

runtimeof SPH-I nowalsovaries signicantly. For practical reasons it

becamenecessarytointroduceacpu-timelimit of 50,000secs. for this

algorithmongraphsfromclassesDand E.When SPH-Ididnotcomplete

itscomputationwithin thislimit, itwasterminatedand thebestsolution

foundso farwasused. ThishappenedforgraphsD-19andD-20.Forthese

graphsthetotal timeneededbySPH-Iisestimatedtobe95,000secsand

679,000secs.,respectively. Theseestimatescanbeconsideredtobequite

accuratesincethey arebased on measurementsofthecpu-timespend for

eachpairof verticesx; y 2 V , cf. Fig. C.7, whichisthenscaledwiththe

relativenumber of vertexpairs not yetconsideredat thetimethecpu-

limitis exceeded. Theaverageruntimeof theGAvariesfrom504secs.

for D-5to3,441secs. for D-19, i.e., byafactor of 7. This variation

is small comparedtothevariationof theother algorithms considered.

For graphs D-8, D-9, D-10, D-13, D-14, D-15, D-18, D-19andD-20the

GAisonaverageanorderof magnitudefasterthanSPH-Iwhileforthe

remaininggraphs theruntimesof thesealgorithmsarecomparable.

C.4.4.4 TheE Graphs

ForthegraphsfromclassEtheeectofgraphreductionsfollowsapattern

whichcoincidesperfectlywith thepatternsobservedforclassesCandD.

Evenafter reductions thesearchspacesizes for theclass Egraphs are

enormous. Usingthebound

S(n; m)>

0

@

n 0m

k 1

A

n 0m0k +1

k

!

k

wherek =min(m02; n0m)revealsthatanumberofgraphsinthisclass

hassearch spacesexceeding10

100

points. Especially, thesearch spacefor

E-13exceeds 10

231

points andfor E-18it exceeds 10

242

points. These

However, astheaveragevertexdegreeincreases, theeect of reductions

of types aandb(seeSectionC.3.2) decreases signicantly. Whenm

is small, theeect of reductions of typedis alsoverylimited, as can

be seenbythe results for C-11, C-12, C-16andC-17. The obtained

reductioninsearchspacesizes for theseproblems are negligible. The

eect of reductions of typecincreases withthenumber of edges. For

C-16throughC-20abouttwothirdsof all edgesareeliminated bygraph

reductions, mainlyof typec. However, sincetheGAoperates interms

of shortestpaths, minimumspanningtrees, etc., thenumberof edgesare

not thatimportantfor theperformanceof thealgorithm.

TableC.6showsthattheGAnds theglobal optimumat leastonce

forallexamplesandeverytimefor12ofthegraphs,whileSPH-Indsthe

optimumfor10ofthegraphs. WhenneithertheaverageGArunnorthe

SPH-I nds theglobal optimum, 1C

avg

is oftenanorder of magnitude

better than1C

sph

. This is thecasefor C-3, C-4, C-9, C-14, C-18and

C-19. ForC-18andC-19thesolutionsproducedbySPH-Iareverypoor

witherrorsinthe6 -7 %range. TheresultsforC-16areindirectcontrast

toall other results. WhiletheSPH-Indsoptimum, theGAencounters

severeproblems. In7of10runsitmissestheglobal optimumvalueof 11

andoutputs atreeof cost12. This corresponds toahugerelativeerror

1C

worst

of 9.09%.

InTableC.7andsubsequent tables T

bc1

denotes theruntimeof the

branch-and-cut algorithmbyChopraet al [5]. Dependingontheprob-

lem, theruntimefor bothbranch-and-cut algorithms varies extremely.

Chopra'salgorithmspansfrom10 secs. forC-16 tomorethan45,000secs.

for C-18, whileLucena's algorithmvaries from5secs. for C-5tomore

than20,000secs. for C-18. As aconsequence, thebranch-and-cut al-

gorithms aresignicantlyfaster thanboththeGAandSPH-I for some

graphs andsignicantlyslower for others. Theruntimes of theGAand

theSPH-Iaresimilarfor mostgraphs, althoughtheGAis signicantly

faster for graphsC-15, C-19andC-20. ThetimevariationT

of theGA

isrelativelysmall.

C.4.4.3 TheDGraphs

The eect of graphreductions onthe class Dgraphs shows apattern

similar tothat observedfor theCgraphs, althoughnowthepatternis

evenclearer. Mostgraphs arereducedsignicantly, noteespeciallyD-5.

reducedtothedegenerategraphconsistingofasinglevertexonly, which

means that the optimal solutionis foundsolelyby performing graph

reductions.

TableC.3compares thesolutionqualityobtainedbytheGAtothe

globallyoptimal solutions as well as tothesolutions foundbySPH-I.

C

opt

istheglobaloptimumandC

sph

isthesolutionfound by SPH-I. C

best ,

C

avg

andC

worst

is thebest, averageandworst result producedbythe

GAinthe 10runs, whileC

denotes thestandarddeviationof the10

cost values. 1C

sph

=100(C

sph

=C

opt

01) is therelativeerror inpercent

of thesolutionfoundbySPH-Icomparedtotheoptimumsolution. Sim-

ilarly, 1C

avg

=100(C

avg

=C

opt

01)denotes theaverageerror of thesolu-

tionsfoundbytheGA, and1C

worst

=100(C

worst

=C

opt

01) istheworst

error producedbytheGA. Finally, N

ga

denotes thenumber of the10

runs whichdidnotndtheglobal optimum. Thisnotationis alsoused

inthefollowingsections.

Ascanbeseen, theGAndstheglobal optimumforall examplesin

everyexecution. SPH-Iperformssimilarly forall graphsexceptB-13, for

whichithasa1.82%overhead.

TableC.4comparestheruntimeoftheGAwiththatofSPH-Iandthe

branch-and-cut algorithmbyLucenaandBeasley[23]. T

bc2

denotes the

runtimeofthelatteralgorithmandT

sph

isthetimeofSPH-I.Theaverage

timespentby theGAisdenotedT

avg

whileT

denotesthestandard devi-

ationof thetimeforthe10runs. Chopraetal [5] givesnocomputational

resultsfor thesegraphs. Itcanbeseenthat all runtimesareverysmall

andwithintheaccuracyofthesemeasurementsitisdiculttodrawany

conclusionsregardingdierencesinspeedforthedierentalgorithms.

Thefactthat all threealgorithmsnds optimal solutions(exceptfor

SPH-I onB-13) inaveryshort timesuggests that theseexamples are

simplytoosmall tofacilitateanydistinctionof performanceof thealgo-

rithms. Forseveralofthegraphsthesearchspacesaftergraph reductions

areindeedverysmallandthelargestsearchspaceisthatofB-17withless

than10 9

points, which isnotthatmuchforacombinatorialoptimization

problem.

C.4.4.2 TheCGraphs

FromTableC.5it canbeseenthat thegraphreductions arealsovery

eectiveonmostgraphsintheCclass. Noteespecially graphC-5which

6

TheGAhasbeenexecuted10timesforeachexampleintheB, Cand

Dclasses. Solutionqualityis thenevaluatedinterms of best, average

andworst results produced. However, duetoruntimerequirementsthe

GAwas onlyexecutedoncefor eachof the examples inclass E. The

parameter settings areM =40, S =50, p

mut

=0: 005andp

i nv

=0: 1.

Thesevaluesareusedfor all executions, i.e., noproblemspecictuning

has beenmade. AsmentionedinSectionC.1xedparametervaluesare

of majorimportancefromapractical pointof view.

The GAas well as SPH-I are implementedinthe C programming

language. For bothalgorithms, examples fromclasses B, CandDare

executedonaSunSparcIPXworkstationhaving32MbRAM. These

examplesrequireatmost10Mbofmemory. FortheclassEexamples,the

memoryrequirementisabout58Mb. Therefore, for theseexamplesthe

GAaswell asSPH-IareexecutedonaDECMips5000-240workstation

having128MbRAM.

Thebranch-and-cut algorithmbyLucenaandBeasley[23] is afur-

ther developmentof thealgorithmpresentedin[3], but insteadof using

aCray, itis nowexecutedonaSunSparc2workstation. Thismachine

is roughlyasfast as theSunSparcIPX, but probablysomewhatslower

than theDECMips5000-240. Chopraetal'salgorithm[5]isexecutedon

aVAX8700whichisatmostasfastastheother machines. Whencom-

paringabsoluteruntimes inSectionC.4.4thereader shouldkeepthese

dierencesregardingtheusedhardwareinmind. However, theruntime

variationscaused bythedierentmachinesareinsignicantcomparedto

thevariationscausedbydierentprobleminstances whenconsideringa

specicalgorithm.

C.4.4 Results

Inthe followingsections the detailedexperimental results for all four

problemclasses are commented. The tables referencedcanbe found

inSectionC.7. Asummaryandconclusionof theresults aregivenin

SectionC.4.4.5.

C.4.4.1 TheB Graphs

TableC.2liststhecharacteristicsof theproblemsinclassBbeforeand

afterthegraphreductionsofSectionC.3.2 areperformed. Thereductions

duetothefact that all distanceshavebeenprecomputed. SinceO (m

2

)

candidate solutiontrees T are computed, the total runtime of SPH-I

becomesO (n 3

+m 4

n).

graphReductions();

c (T

SPH0I

)=1;

8 x; y 2 W; x 6 =y do

T =G

xy

;

Q =W\V

xy

;

whileWnQ6 =; do

ndavertexz 2 Wn Q closesttoavertexinT ;

addtoTashortestpathfromT toz ;

Q=Q[ f z g ;

if c (T )<c (T

SPH0I

)thenT

SPH0I

=T ;

output T

SPH0I

;

FigureC.7: Outl ine of SPH-I.

C.4.3 Experimental Method

TheGAisevaluatedbyfour kindsof comparisons:

Thesolutionqualityobtainediscomparedtotheglobal optimum.

Theabsoluteruntimeis comparedtothat of twodistinctbranch-

and-cutalgorithmsby Lucenaand Beasley[23] and Chopra, Gorres

andRao[5].

Solutionqualityandabsoluteruntimeiscomparedto thatofSPH-I.

ComparisonwiththeGAbyKapsaliset al [18].

Thebranch-and-cutalgorithmsareguaranteedtond theglobalopti-

mum. However,runtimemaybeunacceptableforsomeprobleminstances

ormayevenpreventsomeproblemsfrombeingsolved. It isthereforeof

interesttoinvestigateifanear-optimalsolutioncanbefound foral l prob-

Foragivengraph, thesizeofthesearch spaceS(n; m)tobeexplored

bytheGAis

S(n; m)= k

X

i =0 0

@

n 0m

i 1

A

wherek =min(m02; n0m), sincethisisthenumberofpossibledistinct

choicesoftheSteinervertices. Someoftheprobleminstancesconsidered

representsextremelylargesearchspaces,aswillbeseeninSectionC.4.4.4.

However, as mentionedinSectionC.3.7, thecorrespondingphenotype

spacesaresmaller.

C.4.2 IteratedShortest PathHeuristic(SPH-I)

As mentionedinSectionC.3.4acomparativestudyof thedeterministic

heuristicsSPH, DNHandADHhasbeenmadebyWinterandSmith[31].

Severalvariantsoftheseheuristics,especiallyanumberofrepetitivevari-

ants of SPH, arealsoconsideredinthestudy. TheADHis ingeneral

consideredtobeoneof thebest deterministicheuristics, whichis also

conrmedbytheinvestigationin[31]. However, theresults alsoreveals

thatsomeoftherepetitivevariantsofSPHconsistentlyoutperformADH

withrespect toresult quality. Furthermore, byapplyinginitial graph

reductionstheruntimeof therepetitiveSPHvariantscanbemadecom-

parabletothat of theother heuristics. Oneof thespecicconclusions

in[31]isthatonthelargestrandomgraphsconsidered,therepetitive SPH

variantdenoted SPH-ZZoutperformsall otherheuristics. Therefore, this

heuristichasbeenchosenforcomparisonwiththeGA.

Fig.C.7 outlinesourimplementationofSPH-ZZ,denotedbySPH-I.It

startsbycomputingD(G)andperforminggraphreductionsasdescribed

in Section C.3.2. Forgivenverticesx andy , G

xy

=(V

xy

; E

xy

)denotesthe

subgraphof Gcorrespondingtotheshortest pathbetweenx andy . In

eachiterationof theouter loopatreeT isbuildwhichspansall vertices

inW. T isinitializedwithashortestpathbetween twooftheverticesto

bespanned, andT is thenextendedbyrepeatedadditionof ashortest

pathtoaclosest, not yet connectedvertex. Thisschemeistriedfor all

possibleinitializationsof T , and thealgorithmoutputsthebestsuchtree

obtained.

As describedinSectionC.3.2routinegraphRe ductions requires time

O (n 3

). TheconstructionofeachcandidatesolutionT takestimeO (m

2

n)

sincethe\while"loopis iteratedO (m) times andit takes timeO (mn)

in Step3of thedecodingprocessisalmostalwaysatree, andasaconse-

quence, Step4israrelyexecuted. Therefore, thetruebottleneckof the

algorithmistheMSpTcomputationperformed inStep 2ofthedecoding,

whichrequirestimeO (m

2

).

C. 4 Experi ments

Thissectiondescribestheexperimental methodappliedandtheresults

obtained. Characteristics of the test examples usedare giveninSec-

tionC.4.1. ThedeterministicheuristicSPH-Iusedforcomparisonisde-

scribedinSectionC.4.2andSectionC.4.3describesthechosenmethod

for performingthecomparativeexperiments. Theresults arereported

anddiscussedinSectionC.4.4. As mentionedinSectionC.1anearlier

GAfor SPGhas beendevelopedbyKapsalis et al. andacomparison

tothat algorithmis presentedinSectionC.4.5. Finally, SectionC.4.6

describesthetypical behaviorof theGAduringanoptimization process.

C.4.1 Test Examples

Thealgorithmistested on all 78SPGinstancesfromtheOR-Library[4].

Accordingtotheirsize,thesegraphsaredividedintofourclassesdenoted

byB, C, DandE.All graphsaregeneratedatrandomsubjectonlytothe

connectivityconstraint, that is, thetopologyisrandomandthevertices

tobe spannedare selectedat random. Everyedge cost is arandom

integerintheinterval [1,10]. InclassBeach graphhasn equal to50, 75

or100. Thevalueof miseithern=6, n=4orn=2andtheaveragevertex

degreeiseither 2.5or 4. Sinceall combinationsexists, classBconsists

of 18graphs. ClassesC, DandEconsistsof graphswithn equal to500,

1,000and2,500respectively. mequals 5, 10, n=6, n=4or n=2andthe

averagevertexdegreeis 2.5, 4, 10or 50. Thus, eachof theclassesC, D

andEconsistsof 20graphs.

Oneof themainadvantages of usingthis test-suiteis that it facili-

tates comparisonwiththeglobal optimal solutions. Theglobal optima

wererst computedbyJ. E. Beasleywhodevelopedabranch-and-cut

algorithmwhichwasexecutedonaCrayX-MP/48supercomputer [3].