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.
Type de document :
Article dans une revue
European Journal of Operational Research, Elsevier, 2007, 176 (3), pp.1371-1386. 〈http://www.lirmm.fr/~bourreau/SOURCES/Bourreau%20EJOR07%20TV%20packing.pdf〉. 〈10.1016/j.ejor.2005.09.027〉
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00330559
Contributeur : Eric Bourreau <>
Soumis le : lundi 30 septembre 2013 - 15:25:59
Dernière modification le : jeudi 24 mai 2018 - 15:59:23
Document(s) archivé(s) le : mardi 31 décembre 2013 - 02:20:25

Fichier

tvbp_benoist.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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. 〈http://www.lirmm.fr/~bourreau/SOURCES/Bourreau%20EJOR07%20TV%20packing.pdf〉. 〈10.1016/j.ejor.2005.09.027〉. 〈lirmm-00330559〉

Partager

Métriques

Consultations de la notice

332

Téléchargements de fichiers

199