IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v64y2016i4p838-848.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Giovanni Giallombardo & Houyuan Jiang & Giovanna Miglionico, 2016. "New Formulations for the Conflict Resolution Problem in the Scheduling of Television Commercials," Operations Research, INFORMS, vol. 64(4), pages 838-848, August.
    • Handle: RePEc:inm:oropre:v:64:y:2016:i:4:p:838-848
    DOI: 10.1287/opre.2016.1496
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2016.1496
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2016.1496?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Srinivas Bollapragada & Hong Cheng & Mary Phillips & Marc Garbiras & Michael Scholes & Tim Gibbs & Mark Humphreville, 2002. "NBC's Optimization Systems Increase Revenues and Productivity," Interfaces, INFORMS, vol. 32(1), pages 47-60, February.
    2. 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.
    3. Srinivas Bollapragada & Marc Garbiras, 2004. "Scheduling Commercials on Broadcast Television," Operations Research, INFORMS, vol. 52(3), pages 337-345, June.
    4. Andreas Ernst & Houyuan Jiang & Mohan Krishnamoorthy, 2006. "Exact Solutions to Task Allocation Problems," Management Science, INFORMS, vol. 52(10), pages 1634-1646, October.
    5. Daya Ram Gaur & Ramesh Krishnamurti & Rajeev Kohli, 2009. "Conflict Resolution in the Scheduling of Television Commercials," Operations Research, INFORMS, vol. 57(5), pages 1098-1105, October.
    6. Bissan Ghaddar & Miguel Anjos & Frauke Liers, 2011. "A branch-and-cut algorithm based on semidefinite programming for the minimum k-partition problem," Annals of Operations Research, Springer, vol. 188(1), pages 155-174, August.
    7. Srinivas K. Reddy & Jay E. Aronson & Antonie Stam, 1998. "SPOT: Scheduling Programs Optimally for Television," Management Science, INFORMS, vol. 44(1), pages 83-102, January.
    8. M J Brusco, 2008. "Scheduling advertising slots for television," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(10), pages 1363-1372, October.
    9. Srinivas Bollapragada & Michael R. Bussieck & Suman Mallik, 2004. "Scheduling Commercial Videotapes in Broadcast Television," Operations Research, INFORMS, vol. 52(5), pages 679-689, October.
    10. Xinhui Zhang, 2006. "Mathematical models for the television advertising allocation problem," International Journal of Operational Research, Inderscience Enterprises Ltd, vol. 1(3), pages 302-322.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Shinjini Pandey & Goutam Dutta & Harit Joshi, 2017. "Survey on Revenue Management in Media and Broadcasting," Interfaces, INFORMS, vol. 47(3), pages 195-213, June.
    2. José Antonio Carbajal & Wes Chaar, 2017. "Turner Optimizes the Allocation of Audience Deficiency Units," Interfaces, INFORMS, vol. 47(6), pages 518-536, December.
    3. José Antonio Carbajal & Peter Williams & Andreea Popescu & Wes Chaar, 2019. "Turner Blazes a Trail for Audience Targeting on Television with Operations Research and Advanced Analytics," Interfaces, INFORMS, vol. 49(1), pages 64-89, January.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. José Antonio Carbajal & Wes Chaar, 2017. "Turner Optimizes the Allocation of Audience Deficiency Units," Interfaces, INFORMS, vol. 47(6), pages 518-536, December.
    2. Shinjini Pandey & Goutam Dutta & Harit Joshi, 2017. "Survey on Revenue Management in Media and Broadcasting," Interfaces, INFORMS, vol. 47(3), pages 195-213, June.
    3. José Antonio Carbajal & Peter Williams & Andreea Popescu & Wes Chaar, 2019. "Turner Blazes a Trail for Audience Targeting on Television with Operations Research and Advanced Analytics," Interfaces, INFORMS, vol. 49(1), pages 64-89, January.
    4. Giovanni Giallombardo & Giovanna Miglionico & Houyuan Jiang, 2015. "New Reformulations for the Conflict Resolution Problem in the Scheduling of Television Commercials," Working Papers 2015/03, Cambridge Judge Business School, University of Cambridge.
    5. John Turner & Alan Scheller-Wolf & Sridhar Tayur, 2011. "OR PRACTICE---Scheduling of Dynamic In-Game Advertising," Operations Research, INFORMS, vol. 59(1), pages 1-16, February.
    6. Sylvia Hristakeva & Julie Holland Mortimer, 2023. "Price Dispersion and Legacy Discounts in the National Television Advertising Market," Marketing Science, INFORMS, vol. 42(6), pages 1162-1183, November.
    7. Daya Ram Gaur & Ramesh Krishnamurti & Rajeev Kohli, 2009. "Conflict Resolution in the Scheduling of Television Commercials," Operations Research, INFORMS, vol. 57(5), pages 1098-1105, October.
    8. Shi, Yang & Zhao, Ying, 2019. "Modeling Advertisers' Willingness to Pay in TV Commercial Slot Auctions," Journal of Interactive Marketing, Elsevier, vol. 48(C), pages 120-133.
    9. Saravanan Venkatachalam & Fion Wong & Emrah Uyar & Stan Ward & Amit Aggarwal, 2015. "Media Company Uses Analytics to Schedule Radio Advertisement Spots," Interfaces, INFORMS, vol. 45(6), pages 485-500, December.
    10. Albert Corominas & Alberto García-Villoria & Rafael Pastor, 2013. "Metaheuristic algorithms hybridised with variable neighbourhood search for solving the response time variability problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 21(2), pages 296-312, July.
    11. Srinivas Bollapragada & Marc Garbiras, 2004. "Scheduling Commercials on Broadcast Television," Operations Research, INFORMS, vol. 52(3), pages 337-345, June.
    12. Guohua Wan & Xiangtong Qi, 2010. "Scheduling with variable time slot costs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(2), pages 159-171, March.
    13. Shen, Yuelin, 2018. "Pricing contracts and planning stochastic resources in brand display advertising," Omega, Elsevier, vol. 81(C), pages 183-194.
    14. M J Brusco, 2008. "Scheduling advertising slots for television," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(10), pages 1363-1372, October.
    15. Corominas, Albert & Kubiak, Wieslaw & Pastor, Rafael, 2010. "Mathematical programming modeling of the Response Time Variability Problem," European Journal of Operational Research, Elsevier, vol. 200(2), pages 347-357, January.
    16. García-Villoria, Alberto & Salhi, Said & Corominas, Albert & Pastor, Rafael, 2011. "Hyper-heuristic approaches for the response time variability problem," European Journal of Operational Research, Elsevier, vol. 211(1), pages 160-169, May.
    17. Dana G. Popescu & Pascale Crama, 2016. "Ad Revenue Optimization in Live Broadcasting," Management Science, INFORMS, vol. 62(4), pages 1145-1164, April.
    18. 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.
    19. García-Villoria, Alberto & Pastor, Rafael, 2010. "Solving the response time variability problem by means of a genetic algorithm," European Journal of Operational Research, Elsevier, vol. 202(2), pages 320-327, April.
    20. Yiting Xing & Ling Li & Zhuming Bi & Marzena Wilamowska‐Korsak & Li Zhang, 2013. "Operations Research (OR) in Service Industries: A Comprehensive Review," Systems Research and Behavioral Science, Wiley Blackwell, vol. 30(3), pages 300-353, May.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:64:y:2016:i:4:p:838-848. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.