The TV-Break Packing Problem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles European Journal of Operational Research Year : 2007

The TV-Break Packing Problem


Instead of selling advertisement spots one by one, some French satellite channels decided in 2002 to modify their commercial offer in order to sell packages of spots. These new general conditions of sale lead to an interesting optimization problem that we named the TV-BREAK PACKING PROBLEM (TVBP). We establish its NP-hardness and study various resolutions approaches including linear programming (LP), Lagrangian relaxation (LR), constraint programming (CP) and local search (LS). Finally we propose a generic CP/LS hybridization scheme (branch and move) whose application to the TVBP obtained the best results in our experiments. Dual upper bounds of the maximal revenue are also computed.
Fichier principal
Vignette du fichier
tvbp_benoist.pdf (500.17 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-00330559 , version 1 (30-09-2013)



Thierry Benoist, Eric Bourreau, Benoît Rottembourg. The TV-Break Packing Problem. European Journal of Operational Research, 2007, 176 (3), pp.1371-1386. ⟨10.1016/j.ejor.2005.09.027⟩. ⟨lirmm-00330559⟩
305 View
470 Download



Gmail Mastodon Facebook X LinkedIn More