Beschreibung:
<jats:title>Abstract</jats:title><jats:p>Given two graphs <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/itor12265-math-0001.png" xlink:title="urn:x-wiley:09696016:media:itor12265:itor12265-math-0001" /> and <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/itor12265-math-0002.png" xlink:title="urn:x-wiley:09696016:media:itor12265:itor12265-math-0002" /> over the same set of vertices and given a set of colors <jats:italic>C</jats:italic>, the “impact on <jats:italic>H</jats:italic>” of a coloring <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/itor12265-math-0003.png" xlink:title="urn:x-wiley:09696016:media:itor12265:itor12265-math-0003" /> of <jats:italic>G</jats:italic>, denoted <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/itor12265-math-0004.png" xlink:title="urn:x-wiley:09696016:media:itor12265:itor12265-math-0004" />, is the number of edges <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/itor12265-math-0005.png" xlink:title="urn:x-wiley:09696016:media:itor12265:itor12265-math-0005" /> such that <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/itor12265-math-0006.png" xlink:title="urn:x-wiley:09696016:media:itor12265:itor12265-math-0006" />. In this setting, the “maximum‐impact coloring” problem asks for a proper coloring of <jats:italic>G</jats:italic> maximizing the impact <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/itor12265-math-0007.png" xlink:title="urn:x-wiley:09696016:media:itor12265:itor12265-math-0007" /> on <jats:italic>H</jats:italic>. This problem naturally arises in the assignment of classrooms to courses, where it is desirable—but not mandatory—to assign lectures from the same course to the same classroom. Since the maximum‐impact coloring problem is NP‐hard, we propose in this work an integer programming based approach for tackling this problem. To this end, we present an integer programming formulation and study the associated polytope. We provide several families of valid inequalities, and we study under which conditions these inequalities define facets of the associated polytope. Finally, we show computational evidence over real‐life instances suggesting that some of these families may be useful in a cutting‐plane environment.</jats:p>