A polyhedral study of the maximum impact coloring problem in hypergraphs

Abstract

Given a graph G and a hypergraph H over the same set of vertices and given a set C of colors, the maximum impact coloring problem in hypergraphs asks for a C-coloring of G maximizing the number of hyperedges of H all of whose vertices are assigned the same color. This problem arises in the context of room allocation to courses. The graph G represents the conflicts between sessions, and the hyperdges of H represent sets of sessions from he same course, and it is desirable to assign these sessions to the same room.

In this work we start a polyhedral study of an integer programming formulation for this problem. Two integer programming models are proposed and their performance is evaluated in practice, concluding that one of them has much better performance. The convex hull of its feasible solutions is studied, characterizing its dimension and identifying several families of facet-inducing inequalities.