New Formulations for the Conflict Resolution Problem in the Scheduling of Television Commercials
New Formulations for the Conflict Resolution Problem in the Scheduling of Television Commercials
复制标题
电视广告排期中冲突解决问题的新表述
DOI：
--
复制
发表时间：
2016
影响因子：
2.7
通讯作者：
Giovanna Miglionico
中科院分区：
文献类型：
--
作者：
G. Giallombardo;Houyuan Jiang;Giovanna Miglionico
我们考虑了在电视节目插播中分配商业广告时出现的冲突解决问题。由于广告商发布了避免竞争的要求，广播公司的目标是将任何一对宣传高度冲突产品的广告分配到不同的插播时段。因此，问题包括在受时间容量限制的情况下将广告分配给休息时间，目的是最大化分配给不同休息时间的广告之间的冲突的总度量。由于现有的改写方法很难用精确的方法求解，我们引入了三种新的有效的(混合)整数规划改写。我们的计算研究基于两组测试问题，一组来自文献，另一组是我们生成的。数值结果表明，与现有的重构法和有效的启发式方法相比，所提出的重构法在解质量和计算时间方面具有良好的性能。我们还提供了理论证据来证明为什么我们的一些新的重新配方应该比现有的重新配方更好。
We consider the conflict-resolution problem arising in the allocation of commercial advertisements to television program breaks. Due to 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 reformulation can hardly be solved via exact methods, we introduce three new and efficient (mixed-)integer programming reformulations of the problem. Our computational study is based on two sets of test problems, one from the literature and another that we generate. Numerical results show the excellent performance of the proposed reformulations in terms of solution quality and computation times, when compared against an existing reformulation and an effective heuristic approach. We also provide theoretical evidences to demonstrate why some of our new reformulations should outperform the existing reformulation.