I am trying to optimize the programming of multiple TV channels for a given week. For each show (a day, a time and a TV show) it is possible to forecast in advance the number of people that will watch the show. I would like to use these forecasts to provide a programming that maximizes the total number of watchers.
Below is the available information:
- M : the number of different shows
- N : the number of channels
- For each day, the opening time and the closing time of the TV channel
- A list of constraints :
- For each show, the number of times it should be programmed by day and week (minimum, maximum or exact number)
- Some blocked shows (for instance, the channel 1 should broadcast show 1 at 2PM on Wednesday)
- An attendance forecast for each day, time and show
I tried to use a MILP solver for this problem (CBC). I have boolean integer variables for each quadruplet (day, time, show, channel). Unfortunately, I can't get an optimal solution in a reasonable time for M = 30 shows and N = 20 channels, for time gaps of 15 minutes (possible shows at 2:00, 2:15, 2:30 etc.). Getting an approximate solution (2% gap from the optimum) takes more than 30 seconds. For my purpose, I would need an approximate solution in less than 30 seconds.
How should I model the problem and which algorithm would you advise me to use?
