Maintaining customer lifetime longevity is a crucial issue for companies. One of the strategies for dealing with this issue is to offer different promotion campaigns. Planning these campaigns creates a problem: Which targeted products in the campaign should be offered to which customers in order to maximise profit? This problem becomes vitally important under the conditions of a limited budget and a lower bound on sales target of each product. It is also remarkable from the operational research perspective because of its NP-hardness. In this study, heuristic approaches to the product targeting problem based on mathematical programming are suggested. The proposed approaches principally determine the products to be included in a campaign using heuristic rules and then distribute these products to the customers optimally. Computational results confirm that these approaches generate superior solutions to the problem in comparison with existing methods in the literature. The effectiveness and efficiency of the approaches are also shown on very large-sized test problems generated in order to verify their potential for practical applications.