Optimal Selection of Different Locations for Billboard Advertisement

Abstract Billboard advertisement optimization has attracted a lot of attention in the recent years. These problems have a wide range of applications in the field of businesses and economics. In this paper, we discuss the optimal selection of the places where the billboard advertisement should be installed. In that sense, given an upper bound for the installation budget and a lower bound for the number of visits for a certain billboard in different locations, we are looking for the optimal whereabouts to set up a billboard. Our approach to solve these kinds of problems is based on the cardinality minimization problems (CMPs). In general, cardinality minimization problem (CMP) is looking for the sparsest solution (i.e., a vector with the maximum number of zeros) to a mathematical program. A special case of the CMP is the problem of finding the sparsest solution to an undetermined linear system of equations, which have found so many applications across various disciplines. Besides, we discuss the problems which include cardinality constraints, i.e, an upper bound for the sparsity of the solution is given and the aim is to minimize the cost or maximize the number of visits for some certain billboards. Keywords: optimization, integer linear programming, cardinality problem, cardinality constraint, advertising.