Extended and discretized formulations for the maximum clique problem

The maximum clique (MC) problem has long been concentrating the attention of many researchers within the combinatorial optimization community.Most formulations proposed in the literature for the MC problem were adapted from the maximum independent set (MIS) problem, which is known to be equivalent to the MC. In fact, independent sets can be easily modelled within the natural variables space.In the present paper we propose new formulations for the MC problem, using additional and extra indexed variables, leading to extended and discretized formulations. The number of variables and constraints of the new models depend on the range of variation of an interval containing the clique number (ωω) of the graph. Therefore, tight lower and upper bounds for ωω may strongly benefit the dimension of the new models.Computational results have been conducted on some DIMACS benchmark and biological instances. These results indicate that, among sparse graphs, the linear programming relaxation of the discretized formulations may produce stronger upper bounds than the known models, being faster to find an optimum clique when embedded into the branch-and-bound. Furthermore, the new models can be used to address other related problems, namely to find a maximum size k-plex, or a maximum size component involving two overlapping cliques.