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 metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00330559
Contributor : Eric Bourreau <>
Submitted on : Monday, September 30, 2013 - 3:25:59 PM
Last modification on : Friday, July 26, 2019 - 11:58:03 AM
Long-term archiving on: Tuesday, December 31, 2013 - 2:20:25 AM

File

tvbp_benoist.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

565

Files downloads

387