Skip to Main content Skip to Navigation
Journal articles

The TV-Break Packing Problem

Thierry Benoist 1 Eric Bourreau 2 Benoît Rottembourg 1 
2 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download
Contributor : Eric Bourreau Connect in order to contact the contributor
Submitted on : Monday, September 30, 2013 - 3:25:59 PM
Last modification on : Tuesday, September 6, 2022 - 4:55:00 PM
Long-term archiving on: : Tuesday, December 31, 2013 - 2:20:25 AM


Files produced by the author(s)




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



Record views


Files downloads