Near-optimalsolutionsforthegeneralizedmax-controlledsetproblem$

In thisworkwedealwithsandwichgraphs G=(V,E) andpresentthenotionofvertices f-controlledbya subset MDV. Weintroducethegeneralizedmax-controlledsetproblem(GMCSP),whereminimum gaps(definedbyfunction f) andpositiveweightsareassociatedtoeachvertexof V. Inthiscase,the objectiveistofindasandwichgraph G in ordertomaximizethesumoftheweightsassociatedtoall vertices f-controlledby M. Wepresenta 12 approximationalgorithmfortheGMCSPandanew procedureforfindingfeasiblesolutionsbasedonalinearrelaxation.Thesesolutionsarethenusedas startingpointinalocalsearchprocedure(TabuSearchwithPathRelinking)lookingforsolutionsof betterquality.Finally,wepresentsomecomputationalresultsandcompareourheuristicswiththe optimumsolutionvalueobtainedforsomeinstancesoftheproblem.