New Reformulations for the Conflict Resolution Problem in the Scheduling of Television Commercials
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.
|Date of creation:||Sep 2015|
|Contact details of provider:|| Postal: Trumpington Street, Cambridge, CB2 1AG|
Phone: +44 (0) 1223 339 700
Fax: +44 (0) 1223 339 701
Web page: http://www.jbs.cam.ac.uk
More information through EDIRC
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Victor F. Araman & Ioana Popescu, 2010. "Media Revenue Management with Audience Uncertainty: Balancing Upfront and Spot Market Sales," Manufacturing & Service Operations Management, INFORMS, vol. 12(2), pages 190-212, December.
- Andreas Ernst & Houyuan Jiang & Mohan Krishnamoorthy, 2006. "Exact Solutions to Task Allocation Problems," Management Science, INFORMS, vol. 52(10), pages 1634-1646, October.
When requesting a correction, please mention this item's handle: RePEc:jbs:wpaper:201503. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Ruth Newman)
If references are entirely missing, you can add them using this form.