Extended anddiscretizedformulationsforthemaximumcliqueproblem

The maximumclique(MC)problemhaslongbeenconcentratingtheattentionofmanyresearchers withinthecombinatorialoptimizationcommunity. Most formulationsproposedintheliteraturefortheMCproblemwereadaptedfromthemaximum independentset(MIS)problem,whichisknowntobeequivalenttotheMC.Infact,independentsets can beeasilymodelledwithinthenaturalvariablesspace. In thepresentpaperweproposenewformulationsfortheMCproblem,usingadditionalandextra indexedvariables,leadingtoextendedanddiscretizedformulations.Thenumberofvariablesand constraintsofthenewmodelsdependontherangeofvariationofanintervalcontainingtheclique number(o) ofthegraph.Therefore,tightlowerandupperboundsfor o may stronglybenefitthe dimensionofthenewmodels. ComputationalresultshavebeenconductedonsomeDIMACSbenchmarkandbiologicalinstances. Theseresultsindicatethat,amongsparsegraphs,thelinearprogrammingrelaxationofthediscretized formulationsmayproducestrongerupperboundsthantheknownmodels,beingfastertofindan optimumcliquewhenembeddedintothebranch-and-bound.Furthermore,thenewmodelscanbe used toaddressotherrelatedproblems,namelytofindamaximumsize k-plex,oramaximumsize componentinvolvingtwooverlappingcliques.