Allocation of advertising budget between multiple channels to support sales in multiple markets

We consider the allocation of a limited marketing budget between multiple channels in order to promote sales at multiple markets. The channels differ in their type, level of targetability (or reach), and costliness. We incorporate the "threshold effect'' from each market in our resource allocation which requires some positive advertising investment in each market before much sales impact can be observed from it. The increased number of channels in recent years with the advent of digital advertising, along with the added complexity created by the threshold effect, necessitates the development of new allocation approaches. In this paper, we formulate the firm's resource allocation decision as a nonlinear and nonseparable knapsack problem. We develop a branch and cut solution method which is enhanced by a heuristic approach. A set of numerical experiments illustrate the performance of our methods and evaluate the usefulness of two rule-of-thumb strategies commonly used in practice.