New Formulations for the Conflict Resolution Problem in the Scheduling of Television Commercials

• 成果类型: Article
• 署名作者: Giallombardo, Giovanni; Jiang, Houyuan; Miglionico, Giovanna
• 署名单位: University of Calabria; University of Cambridge
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2016.1496
• 发表日期: 2016
• 页码: 838-848
• 关键词: improved approximation algorithms; max k-cut

摘要

We consider the conflict-resolution problem arising in the allocation of commercial advertisements to television program breaks. Because of the competition-avoidance requirements issued by advertisers, broadcasters aim to allocate any pairs of commercials promoting highly conflicting products to different breaks. Hence, the problem consists of assigning commercials to breaks, subject to time capacity constraints, with the aim of maximizing a total measure of the conflicts among commercials assigned to different breaks. Since the existing formulation can hardly be solved via exact methods, we introduce three new and efficient (mixed-) integer programming formulations of the problem. Our computational study is based on two sets of test problems, one from the literature and another more challenging data set that we generate. Numerical results show the excellent performance of the proposed formulations in terms of solution quality and computation times, when compared against an existing formulation and an effective heuristic approach. In particular, for the existing data set, all three formulations significantly outperform the existing formulation and heuristic, and moreover, for the new data set, our best formulation outperforms the heuristic on 76% of the test examples in terms of solution quality. We also provide theoretical evidence to demonstrate why some of our new formulations should outperform the existing formulation.