{'fraction_non_alphanumeric': 0.04657603222557905, 'fraction_numerical': 0.012038817174768837, 'mean_word_length': 4.3663718987963644, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Advertising strategy for profit-maximization: a novel practice on Tmall's online ads manager platforms

Ads manager platform gains popularity among numerous e-commercial vendors/advertisers. It helps advertisers to facilitate the process of displaying their ads to target customers. One of the main challenges faced by advertisers, especially small and medium-sized enterprises, is to configure their advertising strategy properly. An ineffective advertising strategy will bring too many ``just looking'' clicks and, eventually, generate high advertising expenditure unproportionally to the growth of sales. In this paper, we present a novel profit-maximization model for online advertising optimization. The optimization problem is constructed to find optimal set of features to maximize the probability that target customers buy advertising products. We further reformulate the optimization problem to a knapsack problem with changeable parameters, and introduce a self-adjusted algorithm for finding the solution to the problem. Numerical experiment based on statistical data from Tmall show that our proposed method can optimize the advertising strategy given expenditure budget effectively.


Introduction
The market of online shopping has grown significantly in the last decade. This growth has been accompanied by the emergence of online advertising (Goldfarb, 2014). Traditionally, advertisers purchase online display advertising spots by negotiating long-term contracts with publishers. In the last few years, as the development of internet technique, advertisers are able to have a real-time feedback of their online advertising campaigns and address their ads to a specific target (Evans, 2008;Goldfarb and Tucker, 2011). Recently, ads manager platforms, which are more efficient to run online ads, have emerged and the number of e-commercial clients who are willing to post their ads through the platforms continues to grow. Meta's Ads Manager, Alibaba's DMP and Google's ads manager are examples of such platforms. These ads manager platforms typically provide online advertising display opportunities on their own social network platforms or online shopping platforms. For instance, Meta's Ads Manager allows advertisers to run ads on Facebook, Instagram or Messenger. Alibaba's DMP allows e-commercial sellers to advert on Tmall and Taobao.
An ads manager platform is an all-in-one tool for its clients (online advertisers) to create ads, manage when and where they'll run, and track how well their campaigns are performing towards their marketing goals. In the platform, advertisers can define their target customers by setting criteria such as age, interests, geography and so on. Advertisers can set the rules for where their ads are delivered. When customers registered on a web page (e.g., Tmall.com), their information and behaviors, if it is allowed, are collected and they are labelled under different dimensions such as age, location, etc. Based on this information and in conjunction with target criteria defined by advertisers, ads are delivered to those targets. Advertisers can keep track of their advertising strategy results and adjust their strategies in the platform.
As mentioned above, many online platforms provide ads managers tools for their advertiser clients. With these tools, an advertiser can set up an advertising strategy by choosing to deliver ads to the customers with certain features. According to the strategy of the advertiser, the online platform will deliver the ads exclusive to those customers with very specific features. In this situation, a good advertising strategy will lead to a cost-effective marketing result by increasing the rate of return of advertising investment. However, usually it is hard for a small or medium-sized enterprises (SMEs) to configure an efficient advertising strategy with these complex all-in-one tools. More importantly, with a given marketing budget, an inferior advertising strategy will become a catastrophe, especially when these cost-per-click (CPC) or cost-per-thousand-impressions (CPM) ads brought too many "just looking" customers. On the other hand, the customers will be annoyed if they receive too many ads they are less interested in. Therefore, helping advertisers to configure an profit-maximizing advertising strategy will benefit both advertisers themselves and their clients.
In this paper, we propose a novel model to describe the advertising strategy of an advertiser. In the model, customers are defined by different features and attributes. The percentage of a specific feature of customers among all those buying the product is known and event of different features are assumed to be independent. We aim for selecting optimal set of features to maximize the probability of buying products by customers with selected features. The optimization problem is constructed and reformatted analytically for the ease of calculation. We design an efficient algorithm, which is based on greedy algorithm and dynamic programming method, to numerically find the optimal solution to the optimization problem.
Online advertising has been extensively studied in recent literature from different perspectives, such as revenue optimization (see, e.g., Balseiro et al., 2014Balseiro et al., , 2015, algorithms (see, e.g., Miralles-Pechuán et al., 2018) and bidding strategy (see, e.g., Lee et al., 2013;Grigas et al., 2017;Lobos et al., 2018;Liu et al., 2020) . Grigas et al. (2017) and Lobos et al. (2018) developed optimization models for the management of a demand-side platform (DSP) and aim to maximize the platform's profit by choosing optimal real-time bidding (RTB) strategy given constrained budget. The strategy is comprised of the impression type allocation and bidding prices. Lee et al. (2013) presented a RTB strategy that smooth the budget allocation over the time and maximize the conversion performance. Our research differs from these papers in the following three ways. First, we aim to maximize revenue of an advertiser rather than of a platform or publisher. Second, we emphasise an environment without competition so that the price bidding is not incorporated in our model. An advertiser can deliver his/her ads to targets as long as he/she purchases the display slot with a preset price by defining the criteria to target. Third, we focus on one-phase advertising strategy while most papers consider strategy with more than one phases. However, our strategy is adjustable to be multi-periodic while more information is obtained and the parameters in the model is updated.
Our work is also related to the topics in the estimation for click-through-rate (CTR). Many researchers (e.g., Miralles-Pechuán et al., 2018;Liu et al., 2020) aim for optimizing advertising campaigns with the aid of CTR estimation. The prediction and estimation methods for CTR have been well studied. Logistic regression, or generalized linear models have been widely used for CTR prediction based on customers' features (see, e.g., Richardson et al., 2007;Lee et al., 2018) due to its easy implementation. Some other more advanced methods include tensor factorization models (Shan et al., 2014), field-aware factorization machine (Juan et al., 2016), Product-based Neural Network (Qu et al., 2016) and factorization machine supported neural network . In these papers, they focus on the probability of a customer clicking the ad, given the features of the customer; and the optimization models are also based on CTR. In some senses, our model is different from such methods but is similar to those investment models that optimizes the return of investment (ROI).
The contribution of this paper is threefold. First, as far as we know, this is the first paper which focuses on the optimal advertising strategy for online advertisers given accessible information in online ads manager platforms. Previous studies mainly concentrate on the real-time bidding strategy for platforms. There are also some other researchers proposed optimization model based on CTR prediction, which may be difficult for advertisers to obtain related data and implement the method. Second, we provide an innovative algorithm in detail to numerically find the optimal advertising strategies. This will offer a guideline for the advertisers, especially SMEs, to apply our model practically. Third, a numerical experiment with real-world data obtained from an enterprise is conducted to validate our proposed model. The rest of this paper is organized as follows. In Section 2, a model to describe the advertising strategy for an e-commerce seller is proposed. Assumptions are put forward and the model is reformatted in Section 3. A self-adjusting algorithm are proposed to find the optimal advertising strategy numerically in Section 4. Numerical experiments with data of an enterprise on Tmall are analysed in Section 5. Finally, concluding remarks are given in Section 6.

Ads manager platforms
In this subsection, we will briefly describe some key features of ads manager platforms. Figure  1 illustrates the procedure of using ads manager platforms. To run ads on a platform, an advertiser needs to create a new advertising campaign firstly. The advertiser is also required to determine the overall goal of the campaign, the ads placements, a budget, the ad format, etc. Then the advertiser defines the target customers by choosing different impression types of features, which may be classified into: • Consumptions -it measures the shopping activities of customers on the platform. The features in the category can be consumption frequency, nomthly expenditure, purchasing power level, etc; • Interests -it reflects the interests of customers on the platform, based on the products liked or favorited by customer; • Features -it contains customer's demographics, locations and other information provided by customers or estimated by platform; • Preferences -the customer's behavior preference includes features such as browsing preference, frequently used device, shopping preference, etc.
We use the term advertising strategy in this paper to represent the advertiser's choices of impression types of features. The advertiser can choose his advertising strategy depending on historical data such as the distribution of total population by type.  The advertiser would like to know with what kinds of features a potential customer will be more attracted by his/her product. Since the online market is innocent to advertiser's product, the advertiser needs to advertise its product on the ads manager platform for a period of time. For convenience, we call it the trial-run advertisement. In fact, an e-commercial platform will not authorize the e-commerce sellers to use their ads manager platform until their accumulated advertising expenditure on it exceeds a certain amount. In the trial-run advertisement, the product will be delivered to potential customers 1 with all types. After that, the platform, if allowed, will collect feedback data from customers who not merely clicked the ads but already buy the product. Based on the transaction history of customers, the platform can collect and analyze the feature data of the customers who are already bought the product (we call them real customers hereafter), and depict the statistical data of the features of customers. In this circumstance, the advertiser is able to view the insights how the ad performs in the platform. The data he/she can view includes the number of customers who see the ad and the number of customers who click on the ad. The platform also shows how the ad performs across different ages, genders and cities (see figure 2). These data will be updated periodically. After reviews the reports, the advertiser is able to configure and adjust his advertising strategy by using the up-to-date information.
In this paper, we focus on the advertising strategy for the advertiser. The advertiser needs to find a subset of types of customers who can reach his/her ads by using the information of customer's features and attributes. Given the constrained advertising budget, the advertiser aims for finding the optimal advertising strategy to maximize the expected profit. Note: This figure shows an interface of Tmall's ad manager platform for vendors. Such analysis panel can be found in many e-commercial platforms such as Tmall, Amazon, TikTok, etc. The panel depicts the statistical data of customers' age, gender, city level, and consumption power level. The purple bars illustrate the distributions of types of these features for the real customers (corresponding to P i,k in (3)), and the blue bars are for the potential customers (corresponding to Q i,k in (4)).

Model Fundations
We consider the case that a profit-maximizing advertiser 2 is selling one product online. Formally, the price of the product is p, and the cost of providing this product is c. The sales q of the product depends on both the ad campaign expenditure budget e and the advertising strategy S ( p > c ≥ 0, and q ≥ 0). Here, we call {e, S} the decision bundle. We assume that the maximum sales q will not exceed the scale-free capabilities, so that the cost per product c is not changed by the amount of production. We also assume that the price p of the product is predetermined. Thus, the advertiser's goal to maximize the profit is in choosing his ad campaign expenditure budget e and advertising strategy S: max In many cases, the cross derivative q eS := ∂ 2 (e; S)/∂e∂S = 0. When the cause-and-effect relation between e and S is agnostic, finding the optimal decision bundle {e * , S * } with respect to both variables simultaneously will be difficult. For the sake of simplicity, we rather consider to optimize the advertising strategy S with the ad campaign expenditure budget e fixed. If the expenditure budget e is fixed to e 0 , then problem (1) is simplified to 2 The advertiser can be either the e-commerce seller or the platform. Some platform provides so-called smart advertising service, for example, the TikTok e-commerce platform, to help its client automatically distribute its ads to desired clients; others, such as Tmall e-commerce platform of Alibaba, offer all-in-one tool for clients for design its smart advertising strategy.
The above problem aims at maximizing the profit with a given expenditure. Let then it is equivalent to Hence, the optimal advertising strategy S * 0 will maximize the sales q with a given expenditure budget e 0 . In this context, a persuasive method for finding the (approximately) optimal decision bundle is to calculate the optimal advertising strategy S * i with respect to a series of expenditure budget {e i }, and then the optimial values of q(e i ; S * i ) with respect to {e i } are known to us. So that we can pick {e * , S * } = arg max {e,S} q(e; S)(p − c) − e.
Optimizing the advertising strategy. Practically, the advertiser can manage to advert exclusively to potential customers with specified features. The advertising strategy S is depicted by the choices of a series of features related to the customers. We denote by F = {F 1 , F 2 , . . . , F n } the set of n numerical and/or categorical features available on the ads manager platform. For example, these features can be gender, age, location, operating system, browser, etc. In , the number of elements in F i . For instance, age={male, female, unknown}, and |age| = 3. In fact, the platform is unable to collect all/part of information from a customer because of the privacy policy in case the customer is unwilling to disclose his/her personal information. Still, the unknown has to be considered as one of the types of the customer features. In this context, a potential customer c can defined by his/her features: where c i ∈ F i for all i ∈ {1, 2, . . . , n}. Given any subset F s := {F s,1 , F s,2 , . . . , F s,n } ⊆ F, we abuse the notation by saying that the event (c ∈ F s ) happens if the events (c i ∈ F s,i ) happen for all i. For the convenience of notation, we define the following event: (Buy) = (Customer will buy the product af ter seeing the ad).
Indeed, the statistical data of features of the potential customers will be updated periodically, since, in fact, the active customers group on an e-commerce platform is dynamic. Moreover, there exists certain bias in the statistic result from trial run. Generally, the advertiser needs to regularly update his/her optimal strategy to correspond those changes. As we focus on finding optimal advertising strategy, we omit those technical details.
Explanatory variables. After the trial-run advertisement, the advertiser can obtain the feature statistical data, provided by the ads manager platform, of real customers (the customers who have paid for the product). For example, the advertiser will know the percentage of real customers who are male/female, and he/she will also know the percentage of real customers whose genders are unknown. In this way, the advertiser can observe the probability P (· | Buy) of a real customer. If a potential customer has the type t i , then is known to advertiser. We use P i,k to represent the probability of the event that a customer's ith feature is type k, given that the customer is a real customer. Likewise, for all i ∈ {1, 2, , . . . , n}, the advertiser can observe the probabilities {P i,1 , P i,2 , , . . . , To assist the decision-making process, the platform also disclose the statistical data of all customers accessible to the platform. For a given feature i, the advertiser knows the percentage of potential customers belong to each type t i,k for all k ∈ {1, 2, , . . . , m i }. So that is also known to advertiser. Again, we use Q i,k to represent the probability that the customer's ith feature is type k. Similarly, for all i in {n}, the data {Q i,1 , Q i,2 , , . . . , Q i,m i } of the ith feature can be observed by the advertiser. Though many data of both P i,k and Q i,k are available to advertisers on many ads manager platforms, there are still some platforms only provide P i,k to its clients. To narrate that both P i,k and Q i,k are necessary to advertiser, we consider a case that an advertiser would like to promote a makeup for men on a beauty shopping platform. However, the advertiser discovered that more women than men, say, 60% versus 40%, bought this product. In fact, there are more active female users (80% versus 20%) on this shopping platform. Without the statistic information of all potential customers on the platform, the advertiser can hardly configure advertising strategy properly.
We denote the probability of the event that his/her product is successfully sold by B := P (Buy). In the case that the platform follows CPC or CPM pricing mode, the value of B can be easily estimated. Specifically, the advertiser can estimate B from the number of products sold, the perclick cost, and advertising expenditure spent on the platform. An unbiased estimation will be hardly obtainable, but we neglect the bias analysis as it is subtle. Also, whether the value of B is known does not influence the optimal advertising strategy.
The model. The advertiser will decide which features are selected. Denote by F s the set of selected features, then the strategy S can be represented by F s . That is: where F s,1 ⊆ F i . The advertiser can select one or more possible types from one feature, so that |F s,i | can be greater than 1. The ith feature c i of a potential customer c equals to one element of {t i,1 , t i,2 , . . . , t i,m i }. It implies that the advertiser should select at least one type t i,k of each feature F i . Otherwise P(c ∈ F s ) = 0: if F s,i = ∅ for some i, then the strategy already excludes all potential customers. On the other hand, if F s,i = F i , the advertiser accept a potential customer no matter what type of the feature F i the customer has. The advertiser opt to do so only if he/she does not consider this feature in designing the advertisement strategy. We say the ith feature is active in the strategy if F s,i = F i ; and is inactive if F s,i = F i .
As we discussed above, given the advertising campaign expenditure budget e fixed, the advertiser aims to maximize the sales of its product. In other words, the advertisement should cover a certain range of potential customers, with targets' probability of purchasing the product maximized. Based on the discussion above, we propose the following optimization model: The constraint in model (5) means that the advertiser needs to let its advertisement be reached by enough potential customer. Thus, L denotes the required minimum coverage of potential customers, and is represented by a required minimum probability of a customer belongs to the set of selected features. The parameter L is related to the advertising campaign expenditure budget e. A higher budget e allows the advertiser to select a strategy F s with wider coverage of potential customers. Since (11) is a discrete optimization problem, we use "≥" instead of "=" in the constraint because it is practically hard to meet the equality condition. If there are more active features in the strategy, and/or if there are less types t i,k included in any features, then |F s | := n i=1 |F s,i | will be smaller. Consequently, the value of P (Buy | c ∈ F s ) will be higher, but the value of P (c ∈ F s ) will be lower. The advertiser needs to make a trade-off between the purchasing probability and the advertising coverage of potential customers. It should be mentioned that our proposed advertisement model differs from those models that aims at optimizing or predicting the probability CTR value (Shan et al., 2016;Lee et al., 2018;Miralles-Pechuán et al., 2018). They maximize the probability of a customer clicking the ad, given the features of the customer. In some senses, our model is similar to those investment models that optimizes the return of investment (ROI).

Model derivation
To solve problem (5), we introduce the following two assumptions: Assumption 1. The events (c i ∈ F i ) and (c j ∈ F j ) are independent for any i = j, and i, j ∈ {1, 2, . . . , n}.
Assumption 2. The conditional events (c i ∈ F i | Buy) and (c j ∈ F j | Buy) are independent for any i = j, and i, j ∈ {1, 2, . . . , n}.
Remark 1. We claim that Assumption 1-2 are reasonable, since the most of the demographic features are, at least, statistically independent. Though there exist some available features such as purchase power, monthly shopping frequency, etc. are highly correlated, the advertiser can select only one of them to avoid the violation of these assumptions in the decision-making process. See the numerical experiment in Section 5.
In order to solve problem (5), we need to rewrite the formula in terms of variables that can be estimated. We provide the following theorem to revise the model by using assumptions 1-2.
Theorem 1. Suppose that Assumptions 1-2 hold, then problem (5) can be reformulated as Proof. We recall the Bayes' theorem to obtain: Since Assumption 1 holds, the denominator of equation (7) and the constraint in problem (5) equals to By Assumption 2, the numerator of equation (7) can be written as Plugging equations (8) and (9) into equation (7) , the right hand side of equation (7) becomes .
The advertiser needs to decide each F s,i for all i to obtain the final advertising strategy. For this purpose, we provide the following proposition.
Proposition 1 indicates that the optimization problem (6) is separable, so that one can obtain the optimal strategy F * s if a series of optimal sub-strategies F * s,i is obtained. Based on Proposition 1 and equation (10), we write the ith subproblem as follows: where L i is the required minimum probability for the ith subproblem. Unlike L in problem (5), we cannot obtain values of L i by the advertising campaign expenditure budget e. We will discuss how to determine L i in the next section.
Based on Assumption 3, we have the following two lemmas. The proves of the lemmas are omitted as they are trivial.
As a result, a good procedure for us to set up the solution to a subproblem is to fill the capability L i by the types with profit-to-weight ratios P(c i = t i,k |Buy)/P(c i = t i,l ) from high to low. Based on this idea, we propose the following greedy algorithm for solving the subproblem (11).

4:
if P(c i ∈ F s,i ) ≥ L i then, break.
Lemma 3. Any strategy F s,i obtained by Algorithm 1 satisfies that Proof. If m i = 1, we immediately obtain that F * s,i = {t i,1 } and P(c i ∈F * s,i | Buy) P(c i ∈F * s,i ) = 1. If m i > 1, then there exists at least one t i,k ∈ F i such that P(c i = t i,k | Buy)/P(c i = t i,k ) > 1. Suppose by contradiction that for all t i,k ∈ F i , we have P(c i = t i,k | Buy)/P(c i = t i,k ) < 1. Then we obtain that m i k=1 P(c i =t i,k | Buy) m i k=1 P(c i =t i,k ) < 1, it contradicts with the fact that m i k=1 P(c i = t i,k | Buy) = 1 and m i k=1 P(c i = t i,k ) = 1. Suppose that for all i ∈ {1, 2, . . . , n} we have m i > 1. Hence we conclude that P(c i = t i,1 | Buy)/P(c i = t i,1 ) > 1 for all i.
Suppose that there exists a set F * s,i obtained by Steps 1∼7 of Algorithm 1 such that P (c i ∈ F * s,i | Buy)/P (c i ∈ F * s,i ) < 1, and suppose that Algorithm 1 terminates when j = J < m i . We have . Therefore, we have > 1 for all i with m i > 1.
Theorem 2. Suppose Assumption 3 holds, then the solution obtained by Algorithm 1 is a global optimal solution to subproblem (11).
Proof. Since any set F * s,i obtained by Steps 1∼7 of Algorithm 1 satisfies that P(c i ∈ F * s,i | Buy)/P(c i ∈ F * s,i ) ≥ 1 and P(c i ∈ F * s,i ) > L i . By Assumption 3, we have that for all k ∈ {1, . . . , m i }, t i,k are mutually exclusive, then · P(Buy).
Since the types are ordered by non-increasing ratio P(c i = t i,k | Buy)/P(c i = t i,k ), then, started from an empty set, the sub-strategy F s,i is item-by-item filled by Algorithm 1 until the first item that satisfies P(c i ∈ F s,i ) ≥ L i . For the sake of brevity, we use the notation Q(x) = x k=1 P(c i = t i,k ). We denote β the indicator corresponding to this break item: Based on the fact that if a, b, c, d > 0 and a b ≥ c d , then a b ≥ a+c b+d ≥ c d , one can easily obtain that the sequence of the objective values P(F s,i ) generated by Algorithm 1 is non-increasing. In consequence, the algorithm terminates once the constraint in subproblem (11) holds. Since the ratio of P(c i = t i,1 | Buy)/P(c i = t i,1 ) is the largest, the largest objective value of P(F s,i ) is reached if the strategy uniquely include the first item.
Suppose by contradiction that F * s,i obtained by Algorithm 1 is not optimal, then there exist t i,k and t i,l such that k > β, l < β, we have P(c Hence, we can conclude that the solution generated by Algorithm 1 is globally optimal to subproblem (11).
We use the following example to illustrate how Algorithm 1 solves subproblem (11).
Example 1. Consider the case F i = {t i,1 , t i,2 , t i,3 , t i,4 , t i,5 , t i,6 } with the data presented in the following table. Suppose P(Buy) = B.  According to the last column of the table, we sort {t i,1 , t i,2 , t i,3 , t i,6 , t i,4 , t i,5 } by the ratio of P(c i = t i,k |Buy)/P(c i = t i,k ). We will first include t i,1 into the strategy set. If L i = 0, then Algorithm 1 terminates when j = 1, and we have the optimal strategy F * s,i = {t i,1 }. The value of the objective function P(F * s,i ) is 2.20B. If L i = 30%, then Algorithm 1 terminates when j = 2. We have the optimal strategy F * s,i = {t i,1 , t i,2 }, and the value of the objective function P(F * s,i ) is (16.27% + 49.92%) · B/(7.28% + 26.00%) = 1.99B.
Next, we will discuss how to solve the main problem. Since all the probabilities appeared in problem (6) are nonnegative, we can take logarithm for both the objective function and the constraint. After F s,i for all i ∈ {1, 2, . . . , n} are obtained, we can further convert problem (6) to x i ∈ {0, 1}, i = 1, 2, . . . , n, where p i = log(P(c i ∈ F * s,i | Buy)), q i = log(P(c i ∈ F * s,i )), β = log(P(Buy)), and l = log(L). Problem (12) is a knapsack problem. Given a set of items, each with a weight and a value, knapsack problem aims to decide for each item to be included or not so that the total value is maximized, and the total weight is no more than a given limit. In our case, the values of items are {p i − q i }, the weights of items are {−q i }, and the weight limit is −l. The linear programming (LP) relaxation of problem (12) is 0 ≤ x i ≤ 1, i = 1, 2, . . . , n, and the dual problem of problem (13) is We denote the optimal solution to problems (13) and (14) with x * , y * and s * . From the complementary condition, we know that for i = 1, 2, . . . , n. Notice that, when p i − q i = q i y * , then the optimal solution x * j may be a non-integer value. By exploiting equation (15), the LP relaxation (13) can be solved by the greedy algorithm (Kellerer et al., 2004). The knapsack problem has been thoroughly studied in the last two decades and some exact algorithms for its solution can be found in the literature (Martello et al., 2000;Cacchiani et al., 2022b,a). To give a brief: Algorithm 2 (Self-adjusted algorithm for problem (6)) 1: Initialization: Give L > 0 based on the ad campaign expenditure budget. Set L i = 0 for all i ∈ {1, 2, . . . , n}. Set initial solution x = (0, 0, . . . , 0). if P(c i = t i,1 | Buy)/P(c i = t i,1 ) >= 1 then

5:
Solve the ith subproblem (11) by using Algorithm 1, and obtain F s,i . Set p i = log (P(c i ∈ F s,i | Buy)) and q i = log (P(c i ∈ F s,i )).

10:
end for

12:
Set L i > P(c i ∈ F s,i ) for all i ∈ {1, 2, . . . , n}. approximation to the optimal solution of the primal problem. Problem (12) with bounded coefficients can be solved very fast if the primal problem and the LP relation solutions are sufficiently close to each other. This applies to instance types such as the so-called uncorrelated, weakly correlated and subset-sum problems.
3 In general, the integer solution obtained from greedy algorithm, though most likely not the optimal solution to the integer problem (12), can be viewed as an integer approximation to the (non-integer) optimal solution of the LP (13). Greedy algorithm works as an approximate method to solve problem (12). Consequently, we have the following relation between the optimal objective values of problems (12), (13), and (14): The dynamic programming (Toth, 1980;Kellerer et al., 2004;Martello et al., 1999) method is the most commonly used method for solving Knapsack problem. It solves a problem with time complexity O(nl). Many algorithms are proposed based on some specific amendments to the dynamic programming method. The combo method, a mixed algorithm combines the enumeration process dynamic programming with tight bounds to solve a knapsack problem, has the superior performance amongst others for solving some difficult knapsack problems. Interested readers are referred to Martello et al. (1999Martello et al. ( , 2000, and Cacchiani et al. (2022b).
Unlike a prototypical knapsack problem, problem (6) requires self-adjusted process to determine the parameters L i for the subproblem (11) with i = 1, 2, . . . , n. By the virtue of Algorithm 1 and dynamic programming method, we introduce Algorithm 2 to solve problem (6).
Remark 2. When the knapsack problem (12) is not proper, a trivial solution x = (0, 0, . . . , 0) will be obtained in Step 11. We use Step 12 to amend problem (12) until it is solvable. The process in Step 12 is equivalent to reducing the weights of items in the knapsack problem (12), so that the constraint in problem (12) is easier to be satisfied.
Step 12 also reduces the values of items. Consequently, the optimal objective value of problem (12) decreases after each recursion.

Experiments
To conduct an experiment, we acquired the statistical data of customer of WildFieldHealth ™ , a fitness nutrition brand from Australia. WildFieldHealth ™ lands on the Tmall.com, a Chineselanguage website for business-to-consumer (B2C) online retail operated by Alibaba Group, and provides its products to China's customers since 2019. Alibaba's DMP offers an ads manager platform for vendors on the Tmall to analyze their customers' preferences so as to customize their advertising strategy. All the dataset in our numerical experiment comes from the analysis panel of Alibaba's DMP ads manager platform. In this section, we will describe the experimentation process with real-world data for validating our proposal.

Description of the Dataset
The statistical data of potential customers are summarized from historical click-through data organized from more than 50 million samples, and they are composed of a set of columns that represents features from the customers and their shopping contents. The real customers refer to those customers who have bought the WildFieldHealth ™ fitness product on Tmall. The statistical dataset of real customers is summarized from 20,708 samples. Twenty-four features are comprised in the dataset. The statistical dataset is categorized into four groups: Consumptions, Interests, Customer features and Preference. Detailed explanations about these features are illustrated in Tables 2 and 3. We provide the size of each feature in parentheses after feature name.  Credit level(11) Customer's purchasing credit level is measured when they use credit services on Tmall.
Monthly expenditure(6) Average amount spent by customer on Tmall in the last one year.
Purchasing power in sinking market(6) It measures the purchasing power stratification of the sinking market. The data is obtained based on the purchasing behavior of Customer in the last 6 months.
Purchasing power level(7) Customer's purchasing power level is calculated based on the customer's browsing, searching, purchasing and other behaviors on Tmall.
Sinking market (6) It measures the shopping frequency of customer's in tier 4-6 cities and towns.
Tmall strategical category(9) It categorizes customers based on their purchasing preference.

Interests
Characteristic interests (7) The characteristic interest groups to which the user belongs are obtained comprehensively based on the customer's behavior in Tmall. (6) (7) The age interval of the customer. Tmall obtains this data according to the customer's comprehensively behavior in comparison with the entire customer group.

Content interests
City (19) The city where the customer lives. The data is predicted based on the analysis of customer's behavior .
City level (7) The city where the shipping address is most frequently used by customers in the last 180 days Education (8) The education level of customer.
Generation (6) In which dacade the customer was born. Tmall obtains this data according to the customer's comprehensively behavior in comparison with the entire customer group.
Life stage (8) The ages and stages of customer currently going through.
Occupation (9) The occupation of the customer Phone type (10) The phone model type of the customer access to Tmall.
Preference Browsing preference(8) Customers' browsing preferences for different forms of content in the last 30 days.
Frequently used device(4) Tmall counts the frequency of each terminal used by customer within 90 days , and the terminal with the highest frequency is taken as the frequently used device of a customer.
Nutritional product preference(29) Tmall predicts nutritional product preferences according to the customer's search preferences for nutritional products on Tmall in the last 7 days, click preferences in the last 15 days, favourite preferences in the past 90 days, and purchase preferences in the last 180 days.
Shopping preference (9) Based on the customer's interactive behavior on Tmall in the last 180 days and the feature information of the purchased products, Tmall classifies and scores the customers to 5 tiers.

Description of the Experiments
For this work, we perform an experiment in order to optimize the online advertising strategy using our proposed algorithm. The experiment is performed in MATLAB on a workstation running on 64-bit Windows System with an Intel(R) Xeon(R) W-2245 CPU 3.90GHz and 32 GB RAM. For timing purposes, experiment was computed in 12.200321 seconds per repetition on average.
This experiment aims to implement the proposed optimization method and to determine the characteristics of the optimization procedure. We employ Algorithm 2 armed with Algorithm 1 to solve the problem of finding optimal ad campaign strategy. In Section 2, we mentioned that the advertisement campaign expenditure budget will impact the optimal strategy. In order to find the optimal advertisement campaign expenditure budget e, we test 50 different values of L in problem (6), ranging from 0 to 1. The required minimum probability L is the only parameter considered in our experiment.   Figure 5 shows all the optimal strategy with respect to different values of L. The black squares indicate that the features are selected in the corresponding optimal strategies. It shows that none of optimal strategies selects at least two features among Ages, Generations, and Life stage. Intuitively, these three features may be highly correlated so that a strategy contains at least two of them will violate Assumption 1 and 2. Also,Monthly expenditure, Credit level and Spending power level may be significantly correlated as well.
From Figure 5, we can observe that for all values of L ranging from 0 to 1, the largest number of features activated in the strategy is 6, comparing to 24 available features in total. When the value of L exceeds 2%, there will be at most one active feature. When L is greater than 50%, no feature will be activated. Since there are more than 50 million active customers on Tmall, an ad campaign covering more than a half of all active customers will be expensive or impractical. Still, an ad campaign covering 2 percent of 50 million people will usually be less cost-effective. As it is shown in Figure 6, amongst all 24 features, Nutritional product preference is the most frequently selected feature, followed by Browsing preference, the second most frequently selected feature. These two features have types such as dietary supplement which are directly related to the advertising product. Intuitively, customers labelled with such types have the highest probability of buying the fitness nutrition product. Thus, they are the optimal features to be selected for targeting customers. When the advertisement budget e is reduced, the value of L will be decreased, and the optimal advertisement strategy will contain more active features (shown in sub-graph (d)) . Consequently, the size of targeted potential customer group (P({c ∈ F s }) , see sub-graph (b)) will be sacrificed, and the strategy will be compensated by an increased probability of buying product of a potential customer (P(Buy|{c ∈ F s }), see sub-graph (a)). Even though, the value of P(Buy ∩ {c ∈ F s }) (as it is shown in sub-graph (c)) decreases monotonically with respect to L, which means the probability of selling our product to a potential customer will be decreased. In contrast, if the advertisement budget e is increased, there are fewer active features will be selected in the optimal strategy. Though there will be more products sold to customers if we allow a large advertisement expenditure budget e, such a strategy may not be cost-effective. Hence, the advertiser should carefully choose the expenditure budget e in order to maximize the profit.

Optimize the expenditure budget
By comparing the results shown in sub-graphs (b) and (c) of Figure 7, we discover that, as the required minimum coverage L grows, the group size of targeted potential customer (P({c ∈ F s })) approximately increases in a linear pattern. However, it reveals a quadratic pattern of the probability of selling products to a targeted potential customer (P(Buy ∩ {c ∈ F s })) with respect to the growth of the required minimum coverage value L. It motivates us to find a numerical method to optimize the advertisement campaign expenditure budget. Suppose the total number of potential customer on Tmall is Q, given an advertisement strategy F s , the expected sales of products with respect to expenditure budget e is q(e) = Q · P(Buy ∩ {c ∈ F s }). As we illustrated above, the advertisement strategy F s is influenced by required minimum coverage L. So far as we know, the most of the platforms follow CPC or CPM pricing method, so that we suppose there exists a linear relationship between L and e. That is L = φ(e) and L = a, where a is a positive constant. Suppose that f := P(Buy ∩ {c ∈ F s }) is a smooth function with respect to e, we have q (e) = aQ · ∂f (e) ∂e .
We estimate ∂f (e) ∂e and demonstrate our estimation result in Figure 8. Sub-figure (b) shows that there exists a unique solution to the optimal advertisement expenditure budget. We can calculate the optimal advertisement expenditure budget e if the specific parameters of a, Q and B are given.

Conclusions
In this paper, we develop a modelling framework where customers are labelled by their features. We aim for finding an optimal set of targets' features to maximize the advertiser's profit. An optimization problem is constructed to find the optimal advertising strategy. We revise our optimization problem under some independent assumptions so that the problem can be solved using the given information, i.e., the probabilities of events of different features and types. Two well-known methods, greed algorithm and dynamic programming method, are put forward to find optimal solutions efficiently. We also conduct a numerical experiment with real world data to validate our propose models. Numerical results give the following conclusions: 1 Numerical experiment reveals that the proposed method can optimize the advertisement strategy according to a given advertisement expenditure budget. Specifically, a lower expenditure budget leads to a strategy that contains more active features, and consequently produces a smaller target group. A higher expenditure budget usually leads to a strategy containing fewer active features.
The target group will be larger, and the total sales will be higher as well. However, such a strategy may not be as cost-effective as the one obtained from a lower expenditure budget.
2 As the expenditure budget increases, the group size of target approximately increases in a linear pattern, but the probability of selling product to a target shows a quadratic relationship with respect to the budget. There exists a unique optimal value of advertisement expenditure budget. We also derive a method to numerically estimate the optimal value of expenditure budget.
3 Product preference and browsing preference are two most important and frequently selected features in optimal strategies. These two features provide most information on the probability that customers buy the product to be advertised. Moreover, it is suggested to select at most one feature among features those are highly correlated. It will be less cost-effective if more correlated features are selected.
Admittedly, there are still some limitations in our paper. Assumptions 1-2 are still too strong. Though we provide some compromising methods to avoid the violations of these assumptions, these methods sacrifice the flexibility of the advertisement strategy. Consequently, those strategies obtained by our proposed method may be sub-optimal. Moreover, we do not propose a method to optimize expenditure budget and advertisement strategy simultaneously. In the future studies, we will extend our model by incorporating the correlation between different features as well as the expenditure budget optimization.