Media planning problems for Japanese newspapers considering page space

We formulate media planning problems of newspaper advertisement as a nonlinear knapsack problem and obtain an exact solution. For ad planners, in general, decision support systems are essentials tools. An optimal media planning system, called “optimizer” in industry, plays the central role among them. However there is no guarantee that optimizers always generate truly optimal solution because computational logics equipped in those systems are usually heuristics such as greedy algorithm. In other words, planners have to blindly accept system outputs as optimal ones. We focus on the fact that many media planning optimization problems can be reformulated as problems with separable objective functions subject to a budget constraint, which can be solved by an optimization tool, called “HOPE,” developed by Nakagawa et al.