On identifying dominant cliques

In this paper we present two graph theory-based approaches for identifying dominant cliques with respect to a given set of cliques. As a consequence, the related 0–1 model can be tightened by replacing the initial set of cliques by the new ones. The first approach that we introduce identifies all dominant cliques; the second one identifies a subset of them, but it usually reduces the computing effort. Computational results are reported on some MIPLIB instances, where the original models have been enlarged by appending inequalities identified by a hybrid algorithm of both approaches and a state-of-the-art optimization package is used for problem solving.