We consider the multilevel paradigm and its potential to aid the solution of combinatorial optimisation problems. The multilevel paradigm is a simple one, which at its most basic involves recursive coarsening to create a hierarchy of approximations to the
MultilevelRe nement
forCombinatorialOptimisationProblems
ChrisWalshaw
ComputingandMathematicalSciences,UniversityofGreenwich,
OldRoyalNavalCollege,Greenwich,London,SE109LS,UK.
Email:C.Walshaw@gre.ac.uk;URL:doc.guandang.net
MathematicsResearchReport:01/IM/73
June21,2001
Abstract
Weconsiderthemultilevelparadigmanditspotentialtoaidthesolutionofcombinatorialoptimisationproblems.Themultilevelparadigmisasimpleone,whichatitsmostbasicinvolvesrecursivecoarseningtocreateahierarchyofapproximationstotheoriginalproblem.Aninitialsolutionisfound(sometimesfortheoriginalproblem,sometimesatthecoarsestlevel)andtheniterativelyre nedateachlevel.Asageneralsolutionstrategythemultilevelprocedurehasbeeninuseformanyyearsandhasbeenappliedtomanyproblemareas(mostnotablymultigrid).However,withtheexceptionofthegraphpartitioningproblem,multileveltechniqueshavenotbeenwidelyappliedtocombinatorialoptimisationproblems.Inthispaperweaddresstheissueofmultilevelre nementforsuchproblemsand,withtheaidofexamplesandresultsingraphpartitioning,graphcolouringandthetravellingsalesmanproblem,makeacaseforitsuseasameta-heuristic.Theresultsprovidecompellingevidencethat,althoughthemultilevelframeworkcannotbeconsideredasapanaceaforcombinatorialproblems,itcanprovideausefuladditiontothecombinatorialoptimisationtoolkit.Wealsogiveapossibleexplanationfortheunderlyingprocessandextractsomegenericguidelinesforitsfutureuseonothercombinatorialproblems.
Keywords:MultilevelRe nement;CombinatorialOptimisation;Meta-heuristic;GraphPartitioning;TravellingSalesman;GraphColouring.
1Introduction
Inthispaperweconsiderthemultilevelparadigmanditspotentialtoaidthesolutionofcombinatorialoptimisationproblems.Themultilevelparadigmisasimpleone,whichatitsmostbasicinvolvesrecursivecoarseningtocreateahierarchyofapproximationstotheoriginalproblem.Aninitialsolutionisfound(sometimesfortheoriginalproblem,sometimesatthecoarsestlevel)andtheniterativelyre nedateachlevel.Projectionoperatorscantransferthesolutionfromoneleveltoanother.
Asageneralsolutionstrategythemultilevelprocedurehasbeeninuseformanyyearsandhasbeenap-pliedtomanyproblemareas(forexamplemultigridtechniquescanbeviewedasaprimeexampleofthemultilevelparadigm).Surveypaperssuchas[55]attesttoitsef cacy.However,withtheexceptionofthegraphpartitioningproblem,multileveltechniqueshavenotbeenwidelyappliedtocombinatorialoptimi-sationproblemsandinthispaperweconsidertheirpotentialbene ts.Inparticularweareinterestedinthebroadclassofdiscretesystems,witha nitebutusuallyexponentialnumberofstates,inwhichthe
1
Multilevel Refinement fo... 暂无评价 30页 免费 Multilevel Refinement fo..... To characterise combinatorial optimisation problems that are solvable by GREEDY...
Multilevel Refinement fo... 暂无评价 30页 免费 Multilevel Refinement fo..... Hybrid stan Identifying and managing combinatorial optimisation sub-problems in...
Multilevel Refinement fo... 暂无评价 30页 免费 Multilevel Refinement fo..... Hybrid stan Identifying and managing combinatorial optimisation sub-problems in...
(2005) DVRP: a hard dynamic combinatorial optimisation problem tackled 833 Or, I.: Traveling salesman-type combinatorial optimization problems and their ...
Combinatorial Optimisati... 暂无评价 7页 免费...Formal Approaches for Caching Strategies Optimisation...efficiently computer multilevel memory [1, 6, 8]...
Combinatorial Optimisati... 暂无评价 7页 免费...Formal Approaches for Caching Strategies Optimisation...efficiently computer multilevel memory [1, 6, 8]...
热门文档