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

Giovanni Giallombardo (), Houyuan Jiang () and Giovanna Miglionico ()
Additional contact information
Giovanni Giallombardo: Dipartimento di Ingegneria Informatica, Modellistica, Elettronica e Sistemistica, Università della Calabria, 87036 Rende (CS), Italy
Houyuan Jiang: Judge Business School, University of Cambridge, Cambridge CB2 1AG, United Kingdom
Giovanna Miglionico: Dipartimento di Ingegneria Informatica, Modellistica, Elettronica e Sistemistica, Università della Calabria, 87036 Rende (CS), Italy

Operations Research, 2016, vol. 64, issue 4, 838-848

Abstract: 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.

Keywords: television advertising; conflict resolution problem; integer programming (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2016.1496 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:64:y:2016:i:4:p:838-848

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().