The TV-Break Packing Problem

Thierry Benoist, Eric Bourreau and Benoit Rottembourg
European Journal of Operational Research
Volume 176, Issue 3 , 1 February 2007, Pages 1371-1386
http://dx.doi.org/10.1016/j.ejor.2005.09.027

CMスポットをいくつかのパッケージに分割する問題．
フランスの衛星放送では，CMスポットをいくつか集めてパッケージとして広告主に販売するらしい．
その分割の仕方にはいろいろ制約があるようで，そこが問題を難しくしてる．
その問題を整数計画問題としてモデル化し，NP困難性の証明と (厳密解法とは限らない) 様々な解法を提案している．