Models For The Conflict Resolution Problem In The Scheduling Of TV Commercials

We consider the conflict-resolution problem arising in the allocation of commercial advertisements to television program breaks. Given a set of commercials and a set of program breaks, the problem is to assign each commercial to (at most) one break, so that a total measure of the conflicts among commercials assigned to the same break is minimized. In fact, the conflict-resolution problem arises from several competition-avoidance requirements typically issued by advertisers. We introduce new integer programming formulations of the problem, and we report on computational results for several small- to large-sized instances, in order to evaluate performance of the proposed models.