Abstract :
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.
