资源描述：
《an algorithm for set cover problem 》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、EuropeanJournalofOperationalResearch31(1987)85-93North-HollandAnalgorithmforsetcoveringproblemJ.E.BEASLEYDepartmentofManagementScience,ImperialCollege,LondonSW72BX,EnglandAbstract:Inthispaperwepresentanalgorithmforthesetcoveringproblemthatcombinesproblemreducti
2、ontestswithdualascent,subgradientoptimisationandlinearprogramming.Computationalresultsarepresentedforproblemsinvolvingupto400rowsand4000columns.Keywords:Setcovering,optimisation1.Introductionfieldssuchasairlinecrewscheduling[1,13,14],locationofemergencyfaciliti
3、es[16,19],routingInthispaperweconsiderthesetcoveringprob-problems[ll],assemblylinebalancing[17]andlem(SCP)whichistheproblemofcoveringtheinformationretrieval[7].Otherapplicationareasrowsofam-row,n-column,zero-onematrix(aij)aregivenin[4].byasubsetofthecolumnsatmi
4、nimumcost.ChristofidesandKorman[6]presentedacom-Formallytheproblemcanbedefinedasfollows:putationalsurveyofanumberofdifferentmeth-LetodsfortheSCPandreportedthesolutionofunicost(cj=1,j=1,...,n)problemsinvolvingxj=1ifcolumnj(costcj)isinthesolution,upto35rowsand107
5、5columns(density20%).=0otherwise,NoteherethatthedensityofaSCPistheper-centageofonesinthe(aij)matrix.thentheprogramisEtcheberry[8]presentedanalgorithmbaseduponlagrangeanrelaxationofasubsetoftheminimise,~~CjXj)coveringconstraints(equation(2))withsubgradi-entoptim
6、isationbeingusedtodecidethelagrangesubjectto,$raijXj>,1,i=1,...,m,(2)multipliers.Hereportedthesolutionofunicostproblemsinvolvingupto50rowsand100col-umns(densitiesfrom6%to.25%).xjE(O>l>>j=l,**-,n.(3)Paixao[15]presentedanalgorithmbaseduponEquation(2)ensuresthatea
7、chrowiscoveredbydecompositionandstatespacerelaxationandre-atleastonecolumnandequation(3)isthein-portedthesolutionofproblemsinvolvingup’totegralityconstraint.Iftheinequalitiesinequation400rowsand4000columns(density2%).(2)arereplacedbyequalitiestheresultingprob-B
8、alasandHo[3]reportedthatareasonablelemiscalledthesetpartitioningproblem(SPP).lowerboundfortheSCPcouldbefoundbyadualBoththeSCPandtheSPParewell-knownascentproceduretogetherwit
