A polyhedral study of the maximum-impact coloring problem on hypergraphs

Abstract

Given a graph G = (V,E) and a hypergraph H = (V,F) over the same set of vertices, and a finite color set C, the maximum-impact coloring problem on hypergraphs asks for a C-coloring of G maximizing the number of hyperedges of H whose vertices are assigned the same color. This problem arises in the context of classroom assignment to courses, in which we need to assign a classroom to each lecture and we wish to assign the same classroom to all lectures from the same course. Since imposing this last concern as a constraint may be too restrictive, we seek to maximize the number of courses such that all of its lectures are assigned to the same classroom. In this work we present an integer programming formulation for this NP-hard problem and we explore the associated polytope. We present three families of facetinducing inequalities, and we report computational experiments suggesting that the dynamic addition of these inequalities within a branch and cut environment may be effective in practice.