Constrained Flow Problems for TV  Break Packing


The TV breaks packing problem consists, for a TV channel, in building spot
packages satisfying marketing constraints whilst maximizing the total
selling price. A package is a fixed amount of messages satisfying both
campaign shapes constraints and audience requirement (minimum number of
forecasted spectators). This problem is modelled with a single flow together
with additional covering constraints that make it NP-hard. We compare
several resolution techniques such as linear programming (standard linear
relaxation, lagrangian relaxation) and constraint programming schemes
(standard constraints, global constraint). Finally we present an innovative
way of hybridizing global constraints and local search making use of an
incremental flow algorithm.