Facet-generating procedures for the maximum-impact coloring polytope

Abstract

Given two graphs G = (V, EG) and H = (V, EH) over the same set of vertices and given a set of colors C, the impact on H of a coloring c : V → C of G, denoted I(c), is the number of edges ij ∈ EH such that c(i) = c(j). In this setting, the maximum-impact coloring problem asks for a proper coloring c of G maximizing the impact I(c) on H. This problem naturally arises in the context of classroom allocation to courses, where it is desirable –but not mandatory– to assign lectures from the same course to the same classroom. In a previous work we identified several families of facet-inducing inequalities for a natural integer programming formulation of this problem. Most of these families were based on similar ideas, leading us to explore whether they can be expressed within a unified framework. In this work we tackle this issue, by presenting two procedures that construct valid inequalities from existing inequalities, based on extending individual colors to sets of colors and on extending edges of G to cliques in G, respectively. If the original inequality defines a facet and additional technical hypotheses are satisfied, then the obtained inequality also defines a facet. We show that these procedures can explain most of the inequalities presented in a previous work, we present a generic separation algorithm based on these procedures, and we report computational experiments showing that this approach is effective.