| Article ID: | iaor20084450 |
| Country: | Netherlands |
| Volume: | 176 |
| Issue: | 3 |
| Start Page Number: | 1371 |
| End Page Number: | 1386 |
| Publication Date: | Feb 2007 |
| Journal: | European Journal of Operational Research |
| Authors: | Rottembourg Benot, Benoist Thierry, Bourreau Eric |
| Keywords: | combinatorial optimization, programming: constraints |
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.