solving combinatorial optimization problems via reformulation and

《solving combinatorial optimization problems via reformulation and》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、SolvingCombinatorialOptimizationProblemsviaReformulationandAdaptiveMemoryMetaheuristicsbyGaryA.KochenbergerSchoolofBusiness,UniversityofColoradoatDenverGary.Kochenberger@cudenver.eduFredGloverSchoolofBusiness,UniversityofColoradoatBoulderFred.Glover@Colorado.eduBahramAlidaeeHearinCenterforEnterp

2、riseScience,UniversityofMississippiBalidaee@bus.olemiss.eduCesarRegoHearinCenterforEnterpriseScience,UniversityofMississippiCrego@bus.olemiss.eduABSTRACTMetaheuristics—generalsearchprocedureswhoseprinciplesallowthemtoescapethetrapoflocaloptimalityusingheuristicdesigns—havebeensuccessfullyemploye

3、dtoaddressavarietyofimportantoptimizationproblemsoverthepastfewyears.Particulargainshavebeenachievedinobtaininghighqualitysolutionstoproblemsthatclassicalexactmethods(whichguaranteeconvergence)havefoundtoocomplextohandleeffectively.Typicallyametaheuristicmethodiscraftedtosuittheparticularcharact

4、eristicsoftheproblemathand,exploitingtotheextentpossiblethestructureavailabletoenableafruitfulandefficientsearchprocess.Analternativetothisproblemspecificsolutionapproachisamoregeneralmethodologythatrecastsagivenproblemintoacommonmodelingformat,permittingsolutionstobederivedbyacommon,ratherthant

5、ailor-made,heuristicmethod.Theoptimizationfolklorestronglyemphasizestheunproductiveconsequencesofconvertingproblemsfromaspecificclasstoamoregeneralrepresentation,sincethe“domain-specificstructure”oftheoriginalsettingthenbecomesinvisibleandcannotbeexploitedbyamethodforthemoregeneralproblemreprese

6、ntation.Nevertheless,thereisastrongmotivationtoattemptsuchaconversioninmanyapplicationstoavoidthenecessitytodevelopanewmethodforeachnewclass.Wedemonstratetheexistenceofageneralproblemrepresentationthatfrequentlyovercomesthelimitationcommonlyascribedtosuchmodels.Contrarytoexpectation,whenaspecial

7、lystructuredproblemistranslatedintothisgeneralform,itoftendoesnotbecomemuchhardertosolve,andsometimesbecomeseveneasiertosolveprovidedtherighttypeofsolutionapproachisapplied.ThemodelwiththisappealingpropertyistheQuadraticUnco