{'fraction_non_alphanumeric': 0.03603696495546935, 'fraction_numerical': 0.012502094423034786, 'mean_word_length': 4.46625334648443, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 6, 'https://': 21, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Promotion Optimization for Multiple Items in Supermarkets

Promotions are a critical decision for supermarket managers who must decide the price promotions for a large number of items. Retailers often use promotions to boost the sales of the different items by leveraging the cross-item effects. We formulate the promotion optimization problem for multiple items as a non-linear integer program (IP). Our formulation includes several business rules as constraints. Our demand models can be estimated from data and capture the post-promotion dip effect as well as cross-item effects (substitution and complementarity). Since demand functions are typically nonlinear, the exact formulation is intractable. To address this issue, we propose a general class of IP approximations. For demand models with additive cross-item effects, we prove that it is sufficient to account for unilateral and pairwise contributions and derive parametric bounds on the performance of the approximation. We also show that the unconstrained problem can be solved efficiently via a linear program when items are substitutable and the price set has two values. For more general cases, we develop efficient rounding schemes to obtain an integer solution. We conclude by testing our method on realistic instances and convey the potential practical impact for retailers.


Introduction
Retailers have access to several levers to increase sales and profits. One of these levers is price promotions. For example, in a supermarket, the retailer offers thousands of different items and must decide the price promotions for each item in each period. Setting the right promotions is critical as it can directly impact the retailer's profitability, in an industry where profit margins are very small.It is common for retailers to have thousands of promotions simultaneously. Indeed, offering promotions can help retailers capture different segments of customers and stimulate traffic and demand in the store.
To this day, many supermarket managers are still deciding promotions manually by using a combination of experience and domain knowledge. The substantial amount of available data provides an opportunity to develop data-driven tools that can guide retailers decide promotions at scale.
Retailers need to set the price promotions for thousands of items, while satisfying the relevant business rules. In this paper, we develop a model directly inspired by a collaboration with a large supermarket chain. Our model can help retailers automate the process of deciding the promotions for a large number of items while capturing several key economic factors. We also believe that the models and algorithms developed in this paper are interesting from an optimization theory perspective.
In Cohen et al. (2017), the authors consider a simpler version of the problem where the retailer optimizes the promotions for a single item. In various settings, promoting a specific item can potentially affect the demand of several other items. For example, consider two similar substitutable items such as competing brands of cereals. When one item is on promotion, it can often reduce the sales of the other item given that some customers may switch from one brand to another.
Studying the brand switching effect induced by retail promotions received great attention in the marketing community (see, e.g., Van Heerde et al. 2003, and the references therein). When deciding promotions, retailers need to account for the interplay between the different items. The main goal of this paper is to extend the work in Cohen et al. (2017) for a setting with multiple items, where the category manager needs to simultaneously decide the price promotions of all the items in the category. The solution approach developed for a single item does not yield good results when applied to a setting with multiple items, as it does not properly capture the relationships among the different items. As we will see, extending the solution approach from a single item to a setting with multiple items is not straightforward and requires a different machinery. Interestingly, the method developed in this paper can be applied to more general nonlinear binary integer programming (IP) problems beyond the context of retail promotions.
In this paper, we focus on Fast-Moving Consumer Goods (FMCG). Examples of FMCG include dry goods (e.g., coffee, tea, sugar, and beans), toiletries and cleaning products, and packed beverages. FMCGs typically have a long shelf life and are sold quickly at a relatively low cost. Several sources provide evidence that a large portion of FMCG sales are made on promotions. For example, the group IRI found that in the UK, 54.6% of the products (by volume) were sold on promotion. 1 It is thus not surprising that FMGC manufacturers invest large budgets for promotions: according to Nielsen (2015), the annual promotion budget for FMGC manufacturers is around $1 trillion.
Planning retail promotions is a challenging process for at least fourth reasons. First, as discussed before, cross-item effects on demand may be significant and need to be taken into account. When an item is on promotion, it can also affect the demand of several other items (complements or substitutes). To our knowledge, previous work did not explicitly capture such effects. Second, it is important to carefully capture the business rules that restrict the different promotions. These rules are either set by the supermarket or negotiated with suppliers. For instance, the total number of promotions may be within a certain limit and there are restrictions for promoting competing items at the same time (for more details, see Section 2.2). The third reason is related to the postpromotion-dip effect on demand. Specifically, customers often strategically purchase large amounts of promoted products toward future consumption. This is especially true for non-perishable items.
This stockpiling behavior decrease the demand for the future time periods and hence makes the problem more challenging as it couples the different time periods. Finally, the large scale of the promotion optimization problem contributes to its difficulty. Indeed, it is common for supermarkets to hold thousands of stock keeping units (SKUs), leading to a sizable number of decision variables.
In the retail sector, promotions can substantially affect sales and incentivize customers. In the back-to-school context, the International Council of Shopping Centers run a survey in 2017 and found that promotions influence close to 90 percent of shoppers. 2 As discussed, our main goal is to develop a model and tool that can guide retailers when setting price promotions. We intend to propose a data-driven model that can leverage available data and automate the promotion planning process. In this paper, we tackle this problem by first formulating the promotion optimization problem for multiple items (which we call the Multi-POP). We then propose an efficient approximation solution approach and examine its performance-both analytically and computationally.
We study a class of demand functions that incorporate the post-promotion dip effect and crossitem effects. Our approximate solution approach will provide promotion prices along with analytical performance guarantees. Our Multi-POP formulation is a nonlinear IP, and hence an approach based on directly optimizing the objective is not computationally tractable. We first convey that the method developed in Cohen et al. (2017) for a single item does not perform well in a setting with multiple items. To address this issue, we propose a more general class of IP approximation methods. We then show that for demand models with additive cross-item effects (i.e., promoting item j has an additive effect on the demand of item i), the problem can be efficiently solved by considering only unilateral and bilateral contributions that is, accounting only for the effect of one or two simultaneous promotions; more details are presented in Section 3. We show that realisticsize instances can be solved efficiently: most cases are solved through a single linear program (LP), whereas some more involved cases are solved via an iterative rounding scheme based on solving several LPs. One strength of our method is the fact that it can be applied to a general demand function. We also establish a parametric bound on the performance guarantee relative to the optimal objective. Finally, we use our model and approximation solution to draw managerial insights that can help retailers improve their promotion decisions. Indeed, one of the goals of this research is to develop data-driven optimization models that can guide the promotion planning process for supermarket retailers.

Contributions
We next summarize our main contributions.
• We propose an IP approximation that accurately captures cross-item effects on demand. We introduce a nonlinear IP formulation for the Multi-POP that captures cross-item effects and several business rules. Our demand models include economic factors such as post promotiondip and cross-item effects. Since the problem is not computationally tractable, we propose a class of IP approximations-referred to as App(κ)-based on approximating the objective by unilateral and higher-order contributions. We then focus on App(2) which approximates the objective by only accounting for unilateral (i.e., single promotions) and bilateral (i.e., pairs of promotions) contributions. We show that for demand models with additive cross-item effects, the App(2) approximation is exact. Consequently, one needs to account only for unilateral and bilateral contributions without computing an exponential number of coefficients.
• We show that the approximation solution can be computed efficiently. We observe that the constraint matrix of the approximated problem is not totally unimodular. Nevertheless, we show that for substitutable items and additive cross-item effects, the unconstrained problem admits an integral LP relaxation under two prices. Under these assumptions, we can thus obtain an optimal solution efficiently by solving an LP. Ultimately, it allows us to solve large realistic instances in short timeframes. We also show computationally that even more complicated instances can be solved in acceptable timeframes.
• We develop a performance bound for multiplicative demand functions with additive cross-item effects. We derive a parametric bound on the quality of the IP approximation relative to the optimal Multi-POP solution. We convey that for realistic retail instances, our bound yields a good performance guarantee. We also show that the approximation leads to the optimal solution for additively separable demand functions (in both past and cross prices).
• We use our model to draw insights on promotion planning. We study the interplay between the post promotion-dip and cross-item effects. Understanding such insights can be useful for category managers who need to schedule the promotions of thousands of items. For example, we convey that when the degree of substitution increases, it becomes optimal to reduce the number of promotions. We also show that our model captures the loss leader effect (i.e., the strategy of pricing a product below cost to stimulate the demand of other products) which is often observed in retail. Finally, we test the practicality of our model on realistic instances.

Literature review
Our work is related to three streams of literature: nonlinear optimization, dynamic pricing, and promotions in the field of marketing.
Electronic copy available at: https://ssrn.com/abstract=3061451 Nonlinear optimization: The promotion optimization problem is written as a nonlinear mixed integer program (NMIP). Under most realistic demand models, the resulting objective function is non-concave and thus the problem is hard to solve. Hemmecke et al. (2010) presents several structural assumptions that allow to solve NMIPs in polynomial time. In many practical cases, these assumptions are not satisfied so that one needs to solve the NMIP by using techniques such as Branch and Bound and Extended Cutting Plane methods (Grossmann 2002). One of our approximation methods is based on solving an unconstrained binary quadratic program (UBQP). Rhys (1970) and Balinski (1970) have shown that the UBQP can be solved in polynomial time under certain conditions, which are similar conditions as in our setting. There is a large number of follow-up studies on this topic. For example, in the context of project scheduling, Möhring et al. (2003) considered a similar formulation as ours and extended the reduction of a special case of ordinary precedence constraints and unit processing times to the minimum cut problem.
In this paper, we exploit the discreteness of the Multi-POP to approximate the objective function. More precisely, we propose a general class of IP approximations. We show that approximating the objective by unilateral and bilateral deviations (i.e., contributions of one and two promotions) yields a good performance. This approximation is connected to the well-studied topic of Quadratic Programming (see, for example Frank andWolfe 1956, Nocedal andWright 2006). To our knowledge, the method presented in our paper differs from previous approaches as it exploits the specific structure of the promotion optimization problem to derive structural insights.
Dynamic pricing: The field of dynamic pricing was, and still is extensively studied. For comprehensive reviews, see Talluri andVan Ryzin (2006) andÖzer andPhillips (2012). The work by Cohen et al. (2017) studies the promotion optimization problem for a setting with a single item.
The authors propose an efficient algorithm based on discretely linearizing the objective. They then show that their approximation yields a near-optimal solution in most practical instances, runs in milliseconds, and can easily be implemented by retailers. As we discuss later in this paper, the same methodology cannot be extended to the setting with multiple items without sacrificing performance. Instead, we introduce a more general method that explicitly accounts for the pairwise interactions of promoting two items simultaneously. Cohen and Perakis (2020) present an overview on promotion optimization in retail by discussing the models and insights developed in Cohen et al. (2017) and in the present paper (this book chapter is meant to be an overview and does not contain original research; it does not include the specifics of the algorithms, the formal analytical results and their proofs, and the computational experiments). Dynamic pricing is studied by a multitude of researchers in different contexts (e.g., Ahn et al. 2007, Levin et al. 2010, Su 2010. Ahn et al. (2007) consider a setting where a fraction of the customers will strategically wait and purchase the product if the price falls below their valuation. Su (2010)

investigates a model
Electronic copy available at: https://ssrn.com/abstract=3061451 with several customer types (composed of shopping and holding costs as well as rates of consumption). Finally, Levin et al. (2010) consider a monopolist offering a perishable item to strategic customers. Note that most previous work consider stylized modeling assumptions, and are often restricted to a single item setting. In our paper, however, we consider a practical problem, where the demand models are directly estimated from data, and the optimization formulation includes the promotion decisions of several interconnected items.
Promotions in marketing: Retail promotions are at the core of the marketing discipline.
For more details, see the book by Blattberg and Neslin (1990) and the references therein. In this streams of literature, researchers typically estimate dynamic demand models to study causal effects and sharpen our current understanding on the impact of promotions (see, e.g., Cooper et al. 1999, Foekens et al. 1998). Foekens et al. (1998 estimates parametric models calibrated with scanner data to infer the dynamic impact of promotions. As discussed, for several categories of items, retail promotions may have a post-promotion dip effect. Specifically, when the item is promoted, consumers may stockpile by buying additional units toward future consumption. This effect results in a reduction in short-term future sales. A common way to model this effect is by assuming that the demand function depends both on the current price and on the prices from the previous periods (Macé andNeslin 2004, Ailawadi et al. 2007). The demand models used in our paper also consider that the demand depends explicitly on current and past prices as well as on prices of other items.
Finally, Baardman et al. (2018) address the problem of optimally scheduling promotional vehicles (e.g., end-cap displays, in-store advertisements) for a retailer.
A number of studies empirically examine retail promotions (see, e.g., Van Heerde et al. 2003, Felgate andFearne 2015). Most of these papers adopt a descriptive approach. In our paper, however, we are more interested in the prescriptive side of solving the promotion optimization problem in order to help retailers decide future promotions.
Structure of the paper. In Section 2, we describe the model and assumptions as well as the formulation of the Multi-POP. In Section 3, we introduce and study a class of approximation methods for our problem. In Section 4, we use our model and solution approach to draw practical insights on promotion planning. Section 5 presents computational experiments and conveys the applicability of our solution approach. Finally, we report our conclusions in Section 6. Most proofs of the technical results are relegated to the Appendix.

Problem Formulation
We consider a supermarket category such as ground coffee, cereals, and soft drinks with N items or SKUs. We seek to maximize the total profit throughout a selling season consisting of T periods (e.g., one quarter of 13 weeks). The price of item i at time t is denoted by p i t (the subscript index Electronic copy available at: https://ssrn.com/abstract=3061451 corresponds to the time, whereas the superscript index refers to the item). The (exogenous) unit cost is denoted by c i t .

Assumptions
We assume that the retailer carries a sufficient level of inventory to meet the demand of each of the N items during the selling season. 3 While this assumption is not satisfied for all retail products (e.g., fashion items), it is typically satisfied for FMCGs. Unlike fashion items which are often seasonal, FMCGs are available throughout the year. As mentioned before, FMCGs are easy to store and have a long shelf life. Retailers have an extensive experience in inventory and stocking decisions and often use modern forecasting tools to support ordering decisions (see, e.g., Cooper et al. 1999, Van Donselaar et al. 2006). In addition, grocery retailers are aware of the adverse effects of stock-outs (see, e.g., Campo et al. 2000, Corsten andGruen 2004). We thus assume that FMCG retailers have enough inventory for the selling season. Cohen et al. (2017) examined retail data for FMCGs and confirmed that the demand forecast accuracy is high, and that a very small number of stock-outs occurred in a two-year period.
We assume that the demand is a time-dependent nonlinear function of the prices. More precisely, the demand of item i at time t is denoted d i t (p), where p is a vector of current and past prices (see more details in equation (1)). The objective is to decide which items to promote and when, so as to maximize the total profit over the selling season T .
Each item i = 1, . . . , N can take several prices: the regular price denoted q i0 and K i = |Q i | − 1 promotion prices denoted q ik . The total number of price points for item i is called the size of the price ladder and is denoted |Q i |. For example, if we have K i = 2 promotion prices, then q i2 < q i1 < q i0 and |Q i | = 3.
Without loss of generality, we assume that the regular price q i0 = q 0 is the same across all items and all time periods (this assumption can be relaxed at the expense of a more cumbersome notation). Note that a typical real-world instance can be composed of 30-150 items, 13 periods, and several price points, yielding a large number of decision variables. We define the binary decision variable γ ik t to be equal to 1 if the price of item i at time t is set to q ik , and 0 otherwise. In several product categories, cross-item effects on demand can be significant. Specifically, a promotion for a particular item affects its own sales, but also the sales of other items in the category. One can distinguish between two different types of cross-item effects: substitutability and complementarity. These two types of cross-item effects are well known in economics and operations management (see, e.g., Pindyck and Rubinfeld 2005). The standard example of substitutable items are competing brands such as Coke and Pepsi. In this case, it is clear that promoting a Coke product potentially increases Coke's sales but may also decrease Pepsi's sales. This follows from the fact that some customers may be indifferent between both items and are likely to switch from one brand to the other, when on promotion. Mathematically, if items i and j = i are substitutes,  In what follows, we formulate the promotion optimization problem for multiple items while explicitly incorporating cross-item effects on demand. Before doing so, we impose the following assumption on the demand function.
Assumption 1. The demand function depends explicitly on self past and current prices and on cross current prices.
Assumption 1 implies that the demand does not explicitly depend on cross past prices. In other words, the demand of item i does not depend on the past prices of the other items in the category.
This assumption is supported by the fact that most consumers may be loyal to a particular brand.
As a result, they can stockpile large quantities of a specific item while on promotion. They are also aware of all the prices of the other items at time t, so they can potentially decide to switch and purchase a different item. However, consumers usually do not remember the past prices of other items in the category. We tested the validity of this assumption using data from a large retailer and observed that in the vast majority of product categories, the parameters related to the cross past prices were not statistically significant (the details of these tests are beyond the scope of this paper and hence omitted). The demand of item i at time t can be any nonlinear time dependent function of the form: where M i represents the memory parameter of item i, that is, the number of past prices that affect current demand, and p −i t denotes the vector of prices of all items but i at time t. Note that in practice M i is estimated from data and can be different for different items. The function d i t (·) represents the expected demand. For FMCGs, the demand prediction accuracy is often high, so that expected and actual demands are close to each other (in other words, we assume that demand is deterministic and can be accurately estimated from data). 4

Business rules
We identify two types of business rules: (i) self business rules, that is, price constraints for each item separately and (ii) cross-item business rules, that is, rules that impose price constraints across several items. The self business rules are the same as in Cohen et al. (2017), whereas the cross-item business rules are original from this paper.
Self business rules 1. Discrete price ladder. The price of each item is often restricted to lie in a finite set of admissible prices (e.g., prices must end with 9 cents). For simplicity, we assume that the elements of the price ladder are time independent but our results still hold when this assumption is relaxed. Thus, the price of item i at time t can be written as where the binary variable γ ik t is equal to 1 if the price of item i at time t is q ik , and 0 otherwise.
2. Maximal number of promotions per item. The retailer may want to limit the promotion frequency of a specific item in order to preserve the store image and not train customers to be deal-seekers. For example, it may be required to promote item i at most L i = 3 times during the quarter. This requirement is captured by A common requirement is to space out two successive promotions by a minimal number of separating periods, denoted by S i . As before, this helps retailers preserve the store image and discourage customers to be deal-seekers. In addition, this type of requirement may be directly dictated by the manufacturer who sometimes restricts the frequency of promotions.

Cross-item business rules
1. Total maximal number of promotions for the category. The supermarket may want to restrict the number of promotions for the category during the next T periods (e.g., at most L T = 20 promotions are allowed). This requirement translates to: We notice that the constraint in (2) Inter-item constraints. Business rules often impose price constraints across different items.
For instance, for a given item, the smaller format should be priced at a lower price point than the larger format. Similarly, private labels should be cheaper than national brands. This type of inter-item business rules can be written as linear price constraints: for example, p i t ≤ p j t ∀t captures the fact that item i should be priced no higher than item j.
3. Simultaneous promotions. In some cases, category managers need to promote specific items at the same time. This requirement may come from a special promotional campaign or from a manufacturer trade fund. Specifically, the constraint γ 0i t = γ 0j t ∀t, captures the restriction that items i and j must be promoted at the same time (the binary variable γ 0i t is 1 if there is no promotion for item i at time t).
4. Maximal number of promotions per period. Category managers often need to restrict the number of promotions in the category for each time period (e.g., a week). For example, at most 10% of the items in the category may be promoted (i.e., C t = N 10 ): 5. Inter no-touch constraints. Spacing out promotions can also be required for a set of items.
Once again, such constraints help discourage customers to be deal-seekers as well as preserve the store image. In this case, we need to separate the successive promotions for a given set of items by at least S c separating periods. This requirement translates to: where the summation on i is taken over a specific set of items in the category. The special case with S c = 0 corresponds to never hold simultaneously promotions so as to impose an exclusive deal-a common practice in retail.

Problem Formulation
One can now formulate the promotion optimization problem for multiple items (Multi-POP): Electronic copy available at: https://ssrn.com/abstract=3061451 As discussed, L i , S i , and K i denote the limitation of promotions, no-touch period, and number of promotion prices in the price ladder for item i, respectively. Note that the objective is to maximize the total profit generated by the N items in the category over the selling season. In the formulation (Multi-POP), we have included the various self business rules and two cross-item business rules (total maximal number of promotions and maximal number of promotions per period). Depending on the setting, one can also include alternative cross-item business rules as additional constraints.
We highlight that even in the absence of cross-item business rules, the N items are linked via the cross-item effects on demand.

Solution Approach
In the (Multi-POP) formulation, one can observe two types of effects: (1) cross-time effects, which are driven by the effect of past prices on current demand for each item, and (2) cross-item effects which arise from substitution and complementarity of the different items in the category. Since one needs to decide the promotions for all N items at all times, the problem is a large scale nonlinear IP. Our first attempt was to apply the linear IP approximation based on unilateral contributions of having a single promotion at a time, developed in Cohen et al. (2017). For the case of multiple items, it approximates the objective by the sum of unilateral promotions of each item separately. This approach fails to capture the cross-item effects and will lead to a poor performance, when the crossitem effects are significant. For instance, by ignoring substitution effects, such an approximation can lead to promoting all the items, whereas the optimal policy was to not promote at all. To develop a better solution approach for (Multi-POP), one needs to find a way to incorporate the cross-item effects. To this end, we introduce the class of methods, App(κ), for any given κ = 1, 2, . . . , N , where κ represents the degree of the approximation. More precisely: • App(1) approximates the (Multi-POP) objective function by the sum of the marginal contributions of a single promotion for each item and time period. In other words, App(1) is based on the IP approximation method developed in Cohen et al. (2017) for the setting with a single item. As discussed, however, this method typically yields a poor performance for a setting with multiple items, including in our various computational experiments.
• App(2) approximates the (Multi-POP) objective function by the sum of the marginal contributions, as in App (1), as well as the pairwise contributions, that is, having two items simultaneously promoted. We describe the details of App(2) below.
• App(N ) is an alternative IP approximation that includes the marginal contributions, the pairwise contributions, and so on, up to all possible combinations of having all N items simultaneously promoted.
Electronic copy available at: https://ssrn.com/abstract=3061451 One can also naturally consider any intermediate method for 2 < κ < N . Note that there is a trade-off between simplicity and performance (in terms the approximation method's accuracy). On the one hand, we have App (1). This method only requires to compute the marginal contributions of having a single promotion at a time but can yield a poor performance since it does not capture the cross-item effects on demand. On the other hand, we have App(N ). This method is clearly more accurate than App (1), since it captures all the cross-item effects on demand. Needless to say that this benefit comes at a cost. Indeed, App(N ) relies on computing the marginal contribution of promoting every combination of items at the same time. It thus requires to compute an exponential number of coefficients and to solve an IP that grows exponentially with the number of items. Note that in general, App(N ) is not guaranteed to yield an optimal solution. For the special cases where either T = 1 or M i = 0 ∀i, App(N ) does yield an optimal solution as there are no time effects induced from past promotions. In a general instance, however, App(N ) is not necessarily an exact method. We next present the App(2) method in greater detail.
As mentioned, App(2) approximates the (Multi-POP) objective function by the sum of the marginal contributions (i.e., single promotion for each item and time period) and the pairwise contributions (i.e., two items simultaneously promoted). Accordingly, the approximated objective can be written as: where b ki t and b k ij t are defined in equations (5) and (6), respectively. The binary decision variable, , is equal to 1 if the prices of items i and j at time t are set to q ik and q j respectively, and 0 otherwise. p 0 = (q 0 , . . . , q 0 ) denotes the N T -dimensional regular price vector and corresponds to the situation where the regular price is set for all items at all times. The term M P OP (p 0 ) account for the total profit when no promotion is made. The middle term in equation (4) captures the marginal contributions of having a single promotion at a time. The marginal contribution of promoting item j at time t (using price q kj ) is captured by the N T -dimensional price vector p kj t , which is given by: The vector p kj t is such that the regular price q 0 is used for item j at all times but t as well as for all items different than j at all times. Then, the coefficient b kj t captures the marginal profit contribution of having a single promotion for item j at time t (using price q kj ) and is given by: Electronic copy available at: https://ssrn.com/abstract=3061451 The last term in equation (4) captures the pairwise contributions of having two items promoted at the same time. The marginal contribution of promoting both item j (using price q kj ) and item u < j (using price q u ) at time t, is captured by the N T -dimensional price vector p k ju t , which is given by: The vector p k ju t is such that the regular price q 0 is used for items j and u at all times but t as well as for all items different than j and u at all times. Then, the coefficient b k ju t captures the pairwise contribution on the total profit of having two simultaneous promotions for items j and u at time t and is given by: Note that by construction, App (2) is exact for N = 2 in the sense that it accurately captures all the cross-item effects. For N > 2, App(2) approximates the (Multi-POP) objective by the sum of unilateral and pairwise contributions and is not exact (unless the cross-item effects are present only for pairs of items). However, it performs significantly better than App(1) as the latter does not account for cross-item effects at all. Finally, one can similarly formalize the definition of App(κ), κ = 3, . . . , N .
Ultimately, the App(2) approximation consists of solving the problem in equation (4) while adding the additional constraints in (7). The decisions variables are the binary variables γ. We have one such variable for each of the N item, the T time periods, and the K + 1 price points (i.e., N T (K + 1), assuming for simplicity that K i = K ∀i). We also have one such variable for any pair of items i > j at each time and price (i.e., N (N −1) 2 T K 2 ). As discussed, for the App(N ) method, Electronic copy available at: https://ssrn.com/abstract=3061451 the number of variables increases exponentially in N and K, so that it may be impractical to go beyond App (3) or App(4). Nevertheless, as we show in the next proposition, it is enough to consider App(2) under some assumptions.
Theorem 1. Assume that the cross-item effects for each item are additively separable, that is, Then, we have: In equation (8), the function h i t (·) represents the part of the demand that depends on self current and past prices, and the function H ji t (·) corresponds to the contribution of price p j t to the demand of item i at time t. Note that the result of Theorem 1 applies beyond the context of optimizing retail promotions. Indeed, the same result holds for a general binary nonlinear IP, where the objective function can be expressed as a sum of functions, where each function depends on at most two decision variables. The assumption that the cross-item effects are additively separable allows us to show that App(2) is equivalent to App(N ). As a result, it is sufficient to only consider unilateral and bilateral (pairwise) contributions to capture all the cross-item effects. This assumption is satisfied by several demand functions such as the log-linear model with linear cross terms (see equation (12)) and the linear cross elasticities model (see equation (13)). These models are often used in practice, since they can be easily estimated from data. That said, one could consider alternative demand models that do not satisfy this assumption. In this case, App(2) is not necessarily equal to App(N ). Nevertheless, we have observed computationally that the performance of App (2) is often satisfactory, as it provides a good approximation of the cross-item effects. As expected, the More generally, one can refine the App(2) approximation to be optimal under the following condition.
then the App(2) solution is optimal.
Electronic copy available at: https://ssrn.com/abstract=3061451 In equation (9), the function f i t (·) represents the part of the demand that depends on the current self price p i t , whereas the function g i u (·), for u = 1, . . . , M i captures the part of the demand that depends on p i t−u . Corollary 1 assumes that past and current self prices are also additively separable. For example, this assumption is satisfied for a linear demand function. In this case, one can extend the definition of the App(2) approximation to include all pairwise contributions of two simultaneous promotions: both for different items at the same period and for the same item at different periods (within M i consecutive periods). In this case, all the pairwise interactions are accounted for, so that the App(2) method will lead to an optimal solution. We note that ultimately, the key for App(2) to be optimal is the additively separable property of the demand function.
We return to the more general demand function in equation (8), for which one can solve the (Multi-POP) by applying App (2) and accurately capture the cross-item effects. We are now interested in the following two questions.
1. As discussed, to solve App(2), one needs to solve an IP with a quadratic number of variables in N and K. Can we show that the LP relaxation of App (2) is integral so that one can solve App(2) efficiently as an LP? Is the feasible region totally unimodular as it is for App(1)?
2. Recall that for additively separable cross-item effects, we have App(2) = App(N ). However, App(2) does not always yield an optimal solution, as there is an approximation error induced by the effect of past prices for demand functions that are not additively separable as in equation (9). Can we derive a bound on the performance of the solution obtained from App (2) relative to the optimal solution?
The rest of this section is devoted to answer the above two questions.

Integrality of App(2)
As discussed, the App(2) formulation requires to add four consistency constraints for each time, pair of items, and pair of promotion prices. As expected, adding this set of constraints modifies the feasible region of the (Multi-POP). As shown in Cohen et al. (2017), the single item problemwhich uses App(1)-has a tight LP relaxation, as the constraint matrix is totally unimodular.
One can show that in the absence of cross-item business rules, this property is preserved for the (Multi-POP) as the feasible region for each item is totally unimodular. As a result, App(1) leads to an integral formulation. Although this is not the case for App(2), we can show the following result.
Theorem 2. Consider an additively separable demand as in (8) and K i = 1 (i.e., the price ladder consists of the regular price and one promotion price). For substitutable items, the App (2) formulation is always integral in the absence of business rules.
Proof. We prove the result of Theorem 2 by using the two following lemmas.
Electronic copy available at: https://ssrn.com/abstract=3061451 Lemma 1. Consider an additively separable demand as in (8) with substitutable items. Then, the cross coefficients for App(2), b ij t , ∀i, j > i and ∀t are non-negative.
The proof of Lemma 1 can be found in the Appendix. As we show in the proof of Lemma 1, under , and hence is easy to analyze and interpret.
We next consider the following optimization problem, called the unconstrained binary quadratic program (UBQP): Lemma 2. If all the cross-coefficients b ij are non-negative, one can solve the (UBQP) by an LP.
Lemma 2 follows from Rhys (1970) who has shown that the selection problem of shared fixed costs is integral as it can be viewed as a network flow formulation. More precisely, one can reformulate the (UBQP) as an IP by defining a new variable for each pair of items i, j > i, denoted by x ij and adding the following consistency constraints: Note that when b ij ≥ 0, the last constraint is redundant and can be omitted. In this case, the variable x ij is equal to the product x i x j . Note also that the x ij variables are continuous, whereas the x i variables are binary. In addition, the LP relaxation is not generally tight, as the constraint matrix, which is composed of the consistency constraints, is not totally unimodular. Indeed, as shown in Padberg (1989), every vertex in the linear approximation to (UBQP) is {0, 1 2 , 1}-valued, so that the constraint matrix is not totally unimodular. When all the cross-coefficients b ij are non-negative, however, the result of Lemma 2 directly follows from Rhys (1970).
We next conclude the proof of Theorem 2. By using the results of Lemmas 1 and 2, one can solve the (UBQP) as an LP when the items are substitutable. Recall that the App(2) approximation solves the problem with equation (4) as an objective, which can be equivalently rewritten in the form of the (UBQP).
The result of Theorem 2 shows that there exists an integral solution to the LP relaxation. To arrive at an integral solution, one needs to employ the iterative rounding procedure given in the proof of Lemma 1. Theorem 2 admits the following geometrical interpretation. As discussed, the matrix of the feasible region of App (2) is not totally unimodular. Consequently, some of the extreme points can be fractional. By considering an additively separable demand with substitution effects, Electronic copy available at: https://ssrn.com/abstract=3061451 we ensure that the objective will induce the optimal solution to always lie on integer extreme points. Therefore, one can solve the LP relaxation and obtain an integer solution efficiently.
In Theorem 2, we assume that each item can have two prices: the regular price q 0 and the promotion price q i1 < q i0 . This case is common in practice since the promotion price is often negotiated upfront with the manufacturer via trade-funds and other contractual agreements. Subsequently, the retailer needs to decide when to schedule the promotions of the different items. In the more general case where the retailer can choose among more than two promotion prices, the IP formulation is not guaranteed to be integral anymore. In such a case, as we will show in Section 5, one can still solve the IP in low runtimes for realistic-size instances.
We highlight that in most supermarket categories, the items are either independent (i.e., no cross-item effects) or substitutable. For categories such as coffee, tea, and chocolate, we could not find any complementarity effects in the data we analyzed. Note also that even if some items are complements, we observed by extensive testing that App(2) often yields an optimal integer solution.
Specifically, we considered a computational experiment based on 10, 000 random instances with N = 5 and K = 2 in which the cross price sensitivity values are randomly generated (more details on the instances are presented in Section 5). We then observed the following: (i) the App(2) solution was integral 99% of the time (in the absence of cross-item constraints), and (ii) 91% of the time in the presence of cross-item constraints. More details on our computational tests are presented in Section 5. In addition, recall that in most applications, we only have substitution effects, so that App(2) is always integral in the absence of business rules. Finally, we observed by extensive computational testing that even in the presence of business rules, App(2) yields an integral solution most of the time.
We next discuss the properties of the polytope from Lemma 2-called the Boolean Quadric Polytope-for the general case when cross-coefficients are not necessarily non-negative. It is known from Padberg (1989) that every vertex of the LP relaxation of a Boolean Quadric Polytope is {0, 1 2 , 1}-valued. Using Section 6 of Padberg (1989), there exist sufficient conditions for LP integrality, even when not all the cross-coefficients are non-negative. Two such cases are the following: (i) when the set of items is acyclic, and (ii) when the items are pairwise complementary.
Corollary 2. Consider an additively separable demand with K i = 1 in the absence of business rules. Then, we have: 1. For a set of items (either substitute or complement) that correspond to a forest in the graph, the App(2) formulation is always integral. In this case, the graph corresponding to the set of items is acyclic.
2. For a set of pairwise complementary items (i.e., b ij ≤ 0) which can be transformed into a bipartite graph, the App(2) formulation is always integral.
Electronic copy available at: https://ssrn.com/abstract=3061451 In Corollary 2, we use a graphical way of representing the N items so that items i and j are connected via an edge in the graph if b ij = 0. In practice, the conditions of Corollary 2 are not easy to motivate in most retail settings, whereas the case where all the cross-coefficients are non-negative is very common. Indeed, in most retail categories, the different items are either independent (i.e., b ij = 0) or substitute (i.e., b ij > 0).

Rounding Schemes for App(2)
Since solving the LP relaxation of App(2) does not always lead to an integral solution, we next explore different schemes to round the fractional solution to make it integral. We first discuss a naive rounding scheme. We then introduce three rounding schemes based on iteratively resolving the LP relaxation. We next show analytically the convergence and integrality-preservation property of these rounding schemes. Finally, in Section 5.3, we compare computationally the performance of our rounding schemes relative to the App(2) solution by directly solving the IP.
3.2.1. Naive Rounding Scheme. We first consider a naive scheme, obtained by rounding all the fractional variables in the LP solution to 0. Note that this rounding scheme guarantees that the new rounded solution is feasible. Since the solution is always {0, 1 2 , 1}-valued, then all the fractional variables are necessarily equal to 1 2 . We next separate the analysis into two cases. 1. Case 1: There exists at least one fractional x * i . Since x ij ≤ x i , ∀ j, then all the corresponding x * ij can only be 0 or 1 2 . If x * ij = 0, then we do not need to round x * ij , and hence the constraint x ij ≥ x i + x j − 1 will still hold (the left hand side remains the same and the right hand side decreases). If x * ij = 1 2 , then it would be rounded down to 0. In this case, the new solution will be feasible if 0 ≥ x j − 1, and this naturally holds since all x j are less or equal than 1.

Case 2:
There is no fractional x * i . In this case, if we have a fractional x * ij , it would be rounded to 0. Given the constraints x ij ≤ x i and x ij ≤ x j , the corresponding x * i and x * j must be equal to 1. In this case, however, the constraint x ij ≥ x i + x j − 1 cannot be satisfied by the original solution, so that this case cannot exist.
Although the feasibility of the rounded solution is guaranteed, we will see from our computational tests that the above naive rounding scheme does not yield a good performance. In particular, the gap between the objective value and the optimal MIP objective was found to be as large as 40%, in our tested instances. This motivates us to propose more sophisticated rounding schemes that can still preserve feasibility while providing a better performance.

Greedy
Iterative Rounding Scheme (Rounding Scheme 1). We next consider a rounding scheme that involves re-optimization. In this scheme, we inspect all the parameters b i that correspond to a fractional x * i (if any). We then separate the procedure into three cases: (i) If there is no negative b i , we increase the fractional x * i with the highest b i to 1; Electronic copy available at: https://ssrn.com/abstract=3061451 (ii) If all b i s are negative, we decrease the fractional x * i with the lowest b i to 0; (iii) Otherwise, we compare the objective value of increasing the fractional x * i with the highest b i to 1 relative to the objective value of decreasing the fractional x * i with the lowest b i to 0, while keeping all other x * i unchanged. We then choose to add the constraint that yields the largest objective value (either x i = 1 or x i = 0). We next resolve the LP relaxation problem with the additional constraint x i = 1 or x i = 0. We iteratively repeat the above procedure until all x i s are integral. Once all x i s are integral, we can obtain the values of x ij using x ij = x i × x j . We next show that the new solution is feasible and that the above re-optimization procedure converges and satisfies the integrality-preservation property.
Proposition 1. The integral x i s from the original App(2) solution keep the same value in the new solution obtained from re-optimizing with the constraint x k = 1 or x k = 0, for some k = i.
The proof of Proposition 1 can be found in the Appendix. Using Proposition 1, the number of fractional x i s decreases in each iteration. Since we have a finite number of x i variables, we conclude that our re-optimization rounding procedure converges in a finite number of iterations.

Exhaustive Greedy Iterative
Rounding Scheme (Rounding Scheme 2). We next consider an alternative rounding scheme also based on re-optimization. In the previous scheme, we only considered the coefficients b i in a greedy iterative fashion. This procedure ignores the pairwise effects among different items and focuses on local objective improvements. To mitigate this issue, we propose the following rounding scheme. Instead of increasing or decreasing the fractional variable with the highest or lowest b i , we exhaustively try all fractional variables in each iteration.
Assume that we have solved the LP relaxation and obtained 0 < K ≤ N fractional variables x i . We then consider increasing each fractional x i to 1 if its b i is non-negative, and decreasing it to 0 if its b i is negative. For each fractional x i , we resolve the optimization problem with the appropriate additional constraint. At this point, we have solved K optimization problems. We compare the K objective values and choose to add the constraint x k = 0 or x k = 1 which leads to the highest objective. We iterate the above procedure until all x i s are integral and compute the values of x ij using x ij = x i × x j . One can see that this rounding scheme satisfies the convergence and integralitypreservation properties from Proposition 1.

Second-Order Greedy Iterative Rounding Scheme (Rounding Scheme 3).
We finally consider one last re-optimization rounding scheme. In the previous rounding schemes, we did not account for "network effects" (i.e., the fact that changing the value of x i may ultimately affect some connected variables x j , j = i). We next propose a refined version of rounding scheme 1 that partially accounts for network effects. More precisely, instead of comparing the values of b i Electronic copy available at: https://ssrn.com/abstract=3061451 for all fractional x * i s in the original optimal solution, we now compare b i + j b ij , where j is such that x * j are equal to 1 and connected to x * i in the original optimal solution. The rounding scheme proceeds as follows: (ii) If all b i + j b ij are negative, we decrease the fractional x * i with the lowest b i + j b ij to 0; (iii) Otherwise, we compare the objective value of increasing the fractional x * i with the highest b i + j b ij to 1 relative to decreasing the fractional x * i with the lowest b i + j b ij to 0, and add the constraint that leads to the largest objective value (either x i = 1 or x i = 0). We next resolve the LP relaxation problem with the additional constraint x i = 1 or x i = 0. We iteratively repeat the above procedure until all x i s are integral. Once all x i s are integral, we can obtain the values of x ij using x ij = x i × x j . One can see that this rounding scheme satisfies the convergence and integrality-preservation properties from Proposition 1.
We test computationally all four rounding schemes in Section 5.3.

Performance Bound
We next present a performance guarantee for the App(2) solution relative to the optimal (Multi-POP) solution. We consider a multiplicative demand with additive cross-item effects such as the log-linear model with additive linear cross effects (see equation (12)). More precisely, the demand of item i at time t can be written as: where the first product of M i + 1 functions represents the effect of item i's prices, and the second term corresponds to the additive cross-item effects induced by the other items j = i. For the demand model in (10), we develop the following parametric bound.
Here,L i denotes the effective maximal number of promotions for item i and is defined as: Electronic copy available at: https://ssrn.com/abstract=3061451 We assume that L i ≥ 1 (the case of L i = 0 is not interesting, as no promotions are allowed for item i). SinceÑ i ≥ 1, we also haveL i ≥ 1.
The result presented in Corollary 3 can be shown in the same way as Theorem 1 of Cohen et al. (2017), and hence we omit the proof for conciseness. In Cohen et al. (2017), the authors show that in a single item setting, the App(1) approximation yields a provably good performance by deriving a parametric bound in closed form. In Corollary 3, we extend such a guarantee to the setting with multiple substitutable items. We make the following observations. First, in the setting with multiple items, one needs to consider the App(2) approximation, instead of App(1). Second, since App(2) = App(N ) under additively separable demand models, the only approximation is in terms of the dependence on past prices. Third, we show that the same bound as in the single item setting holds, just that now the bound is driven by the item with the lowest-valued g(·) function.
Consequently, the good performance of the bound from the single item setting is preserved.
Indeed, the parametric bound R M is characterized by the worst value of R i for each item i = 1, 2, . . . , N . As discussed in Cohen et al. (2017) for the single item setting, this bound yields a good performance guarantee for a wide range of practical instances. Consequently, it also performs well for the multiple item setting. By considering several instances of the log-linear model with additive linear cross effects (see equation (12) in Section 5), we observe that the bound was always within 30% of optimal. One can also show the following comparative statics: the value of 1 R M improves (i.e., gets closer to 1) when (i) L i decreases, (ii) S i increases, and (iii) q jK j increases.
More importantly, recall that the bound from equation (11) is only a theoretical performance guarantee, whereas in practice the ratio M P OP (γ M P OP ) M P OP (γ App (2) ) is often much closer to 1. One can also show that the bound presented in Corollary 3 is (asymptotically) tight in a similar fashion as in Cohen et al. (2017). Finally, recall that for the additive demand model from equation (9), the App (2) method and always leads to an optimal solution.

Insights
In this section, we present several managerial insights drawn from our promotion optimization problem. We first show that our model can capture the loss leader effect which is often observed in retail environments. We then consider a simple symmetric setting allowing us to investigate the impact of substitution and complementarity on the optimal promotion strategy.

Loss Leader
The loss leader is a common phenomenon in which one item is priced below cost in order to extract significant profits from complementary items (see, e.g., Hess and Gerstner 1987). Examples include a printer and cartridges as well as a video console and games. We next present an illustrative example to convey that our promotion optimization model can capture the loss leader effect. We Electronic copy available at: https://ssrn.com/abstract=3061451 consider an example of complementary items and show that the optimal promotion strategy leads to a loss leader. We consider a setting with N = 4 items and T = 1, where item 1 is the leader (e.g., the printer) and items 2, 3 and 4 are the complements (e.g., cartridges). We then consider a linear demand model d(p) =d − βM p with a price sensitivity matrix given by: 1 r/2 r/2 r/2 r/2 1 0 0 r/2 0 1 0 r/2 0 0 1    .
Here, r represents the degree of complementarity between the leader and the complements. In addition, we assume that the complements are independent of each other. We assume that the cost of each item is c = 0.4, the regular price is q 0 = 1, and the promotion prices can be any price between 0 and 1 with 0.02 increments. We then solve the unconstrained (Multi-POP) and plot the optimal solution in Figure 1. One can see that when r = 0 (i.e., independent items), it is optimal to have no promotion. When the degree of complementarity r increases, it becomes optimal to promote item 1 (the leader) but never the complements. When r is large enough (in this example r > 0.66), it becomes optimal to set the price of the leader below cost. Consequently, this illustrates that our model can capture the situation where it may be optimal to sell an item below cost to extract positive profits from complementary items.

Cross-Item Effects
We next present several insights related to the impact of cross-item effects on promotion planning.
Specifically, we consider solving the (Multi-POP) and examine the impact of cross-item effects on the optimal solution. For simplicity, we consider a setting with N identical items (i.e., same demand function, cost, and price ladder) in the absence of business rules. In addition, we assume that the Electronic copy available at: https://ssrn.com/abstract=3061451 demand function does not depend on past prices (i.e., M i = 0 ∀i). These simplifying assumptions allow us to isolate and focus on the impact of the cross-item effects. The results are summarized in  Table 1 that for N substitutable items, it is either optimal to promote all the items at all times, or to not promote at all. In particular, it depends on the magnitude of the substitution effect. Under strong substitution effects, promoting an item increases its own sales, but at the same time, decreases the sales of the other items. As a result, one is better off by not promoting at all. When the substitution effects are mild, the benefit of promoting one item overcomes the loss from cannibalization so that it becomes preferable to promote all the items (more details can be found in Section 5.5).
For N complements, the conclusions are reversed. Under strong cross-item effects, promoting one item yields larger sales from this particular item and at the same time, increases the sales of other items. As a result, one is better off by promoting all the items at all times. This result is surprising as one would think that when two items are complements, it is enough to only promote one of them. However, recall that we assume a symmetric setting where any pair of items i and j = i are complements. Then, promoting item i enhances the sales of both items i and j, and promoting item j has the same effect. In other words, by promoting both items, some additional buyers will be incentivized to purchase the complementary item. Under mild cross-item effects, promoting all the items is not optimal anymore. In this case, the benefit from the complementarity is not larger relative to the price decrease. It thus becomes optimal to only promote a subset of items (the size of the subset depends on the magnitude of the complementarity effect).
In practice, supermarkets solve the (Multi-POP) for large scale instances that involve asymmetries, seasonality, post-promotion dip, substitutes and complements as well as several business rules. It is not easy to plan promotions while accounting for all these conflicting tradeoffs. This suggests the need for an optimization tool, such as the one developed in this paper. Our model and approach can account for the different tradeoffs and compute a near-optimal solution for the promotion planning problem. In addition, since our methods are solved in low runtimes, one can perform a sensitivity analysis that can test how the promotion planning is affected by changes in demand parameters or in business rules. This allows category managers to reach a better understanding on how several behavioral effects-such as the post-promotion dip effect and cross-item effects-impact promotion decisions.

Computational Experiments
In this section, we conduct computational tests to evaluate the performance of the App(2) approximation method in terms of tightness and runtime. We also examine the interplay between the post-promotion dip effect and cross-item effects.

Computational Setting
We consider a realistic demand model inspired by our collaboration with supermarket retailers.
Specifically, we consider two types of demand models: 6 • A log-log model with additive linear cross-item effects: • A linear model with additive linear cross-item effects: Note that both models have additively separable cross-item effects and are special cases of equation (8). As a result, the App(2) approximation is equivalent to App(N ). For both models (12) and (13), we calibrated the different parameters using actual data from the coffee category of a large supermarket retailer. More precisely, we estimated the following parameters: a i t (corresponding to seasonality effects), b i 0 (price sensitivity factor), b i k or α (that capture the effect of past prices on current demand), and δ ji (cross-item effects). In addition, we estimated the value of M i by removing the past prices which were not statistically significant in our estimation. To thoroughly test the robustness of our results, we further perturb the estimated demand models by randomly varying the estimated parameters. Ultimately, we consider a wide range of realistic parameter values, summarized in Table 2 (each parameter is randomly drawn from the range of values shown in the table). To avoid negative demand values, we focus on combinations of parameters that yield non-negative demand values. Specifically, we randomly generate demand instances using the range of parameters in Table 2, and if the non-negativity property is not satisfied, we drop the instance and generate a new one.

Parameter
Interpretation Log-log model in (12)  Our computational environment consists of a 2015 Macbook Pro with 16GB RAM and 2.2GHz processor using Gurobi 7.02's Python interface.

Testing the Tightness
We examine the impact of both cross-item effects and cross-item business rules on the tightness of the App(2) approximation. In this context, tightness refers to whether or not the mixed IP that characterizes the App(2) approximation has an integral LP relaxation. In Proposition 2, we have shown that for an additively separable demand with substitutable items and a price ladder of size 2, the App(2) approximation is tight in the absence of business rules. In Figures 2 and 3, we explore the tightness of App(2) in a setting with substitutes and complements respectively, and vary the size of the price ladder between 2 and 4. For each value of N , we randomly sample 1,000 log-log demand functions from the parameter values in Table 2 We next examine the impact of adding business rules to the formulation. We consider a setting with N = 10 items and a price ladder with |Q| = 2 prices. Based on 10,000 randomly generated instances, we observe that App(2) was always integral in the presence of self business rules (i.e., constraints for each item separately). We then examine the impact of adding cross-item business rules on the tightness of the App(2) approximation. For each data point, we solve 1,000 randomly generated instances with a log-log demand function and additive mixed cross-item effects (i.e., either substitutes or complements) and record the percentage of tight instances. For simplicity, we focus on instances with T = 1. In Figure 6, we test the impact of imposing a limit on the total Electronic copy available at: https://ssrn.com/abstract=3061451  (2). One can see that the problem tends to be tight when L T is either large or small. In Figure 7, we consider a setting with N = 10, T = 10, and |Q| = 2 and test the impact of imposing a cross no-touch constraint in which successive promotions for any pair of items need to be spaced out by at least S c periods. For each value of S c , we generate and solve 1,000 App(2) instances and record the percentage of tight instances. Even in the presence of a cross no-touch constraint, the App(2) model is tight more than 90% of the time in our tested instances. For settings where the App(2) model is not guaranteed to be tight (e.g., a price ladder with more than two prices or in the presence of business rules), we propose to use one of the two following solutions: (i) implementing our proposed rounding schemes or (ii) directly solving the mixed IP formulation, instead of relying on the LP relaxation. In Section 5.3, we test our rounding schemes, whereas in Section 5.4, we show computationally that for many tests, the mixed IP solves within acceptable runtimes for retail applications.

Testing the Rounding Schemes
We next conduct computational tests to compare our different rounding schemes. We consider the following demand model for item i: The range of parameter values is reported in Table 3. We randomly generate 5,000 independent instances for each value of the number of items N . To keep our tests general, the items in each instance can be substitutable, complementary, or not connected to the other items. For simplicity of exposition, we consider instances with small values of N . We will consider large-scale practical instances in Section 5.6.
Electronic copy available at: https://ssrn.com/abstract=3061451  We first plot the proportion of instances with the same solution as the optimal MIP solution in Figure 8. As we can see, the naive rounding scheme performs the worst, whereas our three proposed rounding schemes often lead to the same solution as the MIP.
We then plot the average and maximum (Figure 9) difference between the objective value and the optimal MIP objective, for each rounding scheme. As expected, the naive rounding scheme can yield a low performance: an average loss of 10% and a maximum loss of 100% (such an outcome happens when all x i s are fractional in the LP original solution). On the other hand, our three proposed rounding schemes lead to a near-optimal solution: the average gap is lower than 2% in all our tested instances for all three rounding schemes. As expected the performance of rounding scheme 2 is always slightly better than the performance of rounding scheme 1.
Finally, we report the average and maximum ( Figure 10) number of re-optimizing iterations (i.e., the number of iterations needed to reach an integral solution) for our three proposed rounding schemes. For rounding schemes 1 and 3, each iteration corresponds to solving a single LP, whereas for rounding scheme 2, it can correspond to solving several LPs. We observe that the number of re-optimizing iterations remains small across all three rounding schemes. As expected, rounding scheme 2 usually requires a larger number of resolving iterations.
Electronic copy available at: https://ssrn.com/abstract=3061451 Given that rounding scheme 2 needs a larger number of iterations than rounding scheme 1, the slight performance improvement may not be enough to justify using rounding scheme 2. In summary, we conclude that the greedy rounding scheme (i.e., re-optimization rounding scheme 1) is a good candidate for solving our problem: (i) it yields the same solution as the MIP most of the time, (ii) when it does not, the optimality gap is low, and (iii) the required number of resolving iterations is small-thus, making this scheme efficient and applicable to large instances as illustrated in Section 5.6.  Figures 11 and 12, we report the model building time and solving time, respectively. We consider a setting with T = 1, vary the size of the price ladder, and vary the number of items between 10 and 100. For each value of N , we randomly sample 100 independent log-log demand functions with additive cross-item effects. We then record the maximum runtime (in seconds) observed over the 100 samples.
One can see that most of the total runtime is spent building the model. Finally, in Figures 13 and 14, we examine the total runtime to build and solve the mixed IP. In Figure 13, we consider a setting with T = 1 and randomly sample 100 log-log demand functions with additive cross-item effects while varying N and |Q|. In Figure 14, we use |Q| = 2 and vary N over a wider range of values. For each test, we record the maximum runtime over the 100 samples.
We can see that the App(2) method can be solved efficiently even for categories with over 100 items.
In addition, for settings with a price ladder of size 2 (i.e., facing decisions of whether promoting or not), one can solve instances with a large number of items in a reasonable time frame.

Interplay of Time and Cross-Item Effects
In addition to testing the performance of the App(2) approximation, we conduct computational experiments to observe general trends in the optimal promotion strategy in the presence of time effects (i.e., post-promotion dip) and cross-item effects (i.e., substitution and complementarity). In this section, we consider a realistic setting with T = 35, N = 10 symmetric items, and a price ladder with 4 price points (1, 0.9, 0.8 and 0.7). We use a linear demand model calibrated with data from the coffee category of a large retailer with b i 0 = 50, α = 15, and vary the magnitude of the cross-item effects δ between -50 and 50. Our goal is to examine the interplay between α and δ, as well as their impact on the optimal promotion strategy. For each value of δ, we report the optimal number of promotions from the App(2) solution in Figure 15. We can see that for complementary items (i.e., when δ < 0), the App(2) solution leads to offering more promotions, whereas the number of promotions decreases for substitutable items. This outcome is expected, as when δ becomes large, promoting an item decreases the sales of other items via a cannibalization effect.
We next vary the time effect parameter α for different values of δ. We consider the same setting as in Figure 15, but we now vary the effect of past prices in current demand. Specifically, we consider a linear demand model with a memory of three past prices (M i = 3 for all i), where the Electronic copy available at: https://ssrn.com/abstract=3061451 effect of the past price p t−i on current demand is equal to α 1 2 i−1 for i ∈ (1, 2, 3), and 0 otherwise.
In Figure 16, we report the total number of promotions from solving App(2) as a function of α, for three different values of δ. One can see that the number of promotions increases as α decreases.
This follows from the fact that when α is larger, promotions will reduce future demand and hence are less desirable. In addition, we can see that in a setting with complements (i.e., when δ < 0), the optimal strategy will have a higher number of promotions.

Computational Experiments for Larger Instances
In this section, we consider large scale practical instances. In most retail categories (e.g., soft drinks, cereals, yogurts), there can be 30-150 different items. We vary the number of items N = 50, 100, 150, 200, and 250. For each value of N , we consider several independent instances. As before, we consider that the demand model for item i is given by equation (14). The range of parameters and number of instances are reported in Table 4, respectively (for efficient computations, we decrease the number of independent instances as N increases). For simplicity, we consider two prices (i.e., K i = 1) and a single time period (i.e., T = 1).  For each instance, we (i) solve the MIP, (ii) solve the App(2) approximation solution via the LP relaxation, and (iii) compute the proportion of tight instances. Given that we do not restrict the parameters in any way, we obtain a large proportion of instances that are not integral, especially when N is large. One can see from the left panel of Figure 17 that the percentage of tight instances decreases rapidly as N increases.
For non-integral instances, we implement the greedy re-optimization rounding scheme (rounding scheme 1) and compare its solution to the optimal MIP solution both in terms of objective value and running time (see the right panel of Figure 17 where we report the maximum running time for different values of N ). When the number of items is large, it can take up to several days to solve the MIP: it took 500,000 seconds = 5.787 days for N = 250. However, using rounding scheme 1, we can obtain a feasible integral solution in 1-20 minutes. Furthermore, the objective value was always within 95% of the MIP optimal objective in all our tested instances. Finally, for a realistic instance with N = 100 and T = 10, our method runs in 2-4 minutes.

Conclusions
In many retail settings, promotions are a key instrument for driving sales and profits. In a typical supermarket, each category manager needs to decide the promotion strategy for multiple items during the selling season. The large volume of available data allows retailers to improve demand forecasts. The next step is to use these accurate demand forecasting models to carefully decide future promotions so as to maximize profits. In this paper, we introduce and study a practical optimization formulation for deciding the promotions of multiple items. Our model captures important business requirements and encompasses common demand models calibrated from data. Solving this problem is relevant to many retailers and can significantly enhance the bottom line. However, optimally solving this problem is challenging as it involves a large scale non-linear integer program.
Electronic copy available at: https://ssrn.com/abstract=3061451 We propose a tractable approximation method for solving this problem and present analytical and computational results on the performance of the approximation solution.
We first show that a method based on linearizing the objective does not perform well, as it was for a single item. We next consider a modified approach, called App (2), based on approximating the objective with unilateral and pairwise contributions. We show that when the demand has additively separable cross-item effects, App(2) accurately captures the cross-item effects without computing an exponential number of coefficients. We further prove that when the items are substitutable and the retailer decides between two prices, the App(2) formulation admits a tight LP relaxation, in the absence of business rules. For cases where the LP relaxation is not tight, we propose three efficient rounding schemes. Armed with these results, we show that the App(2) method yields a solution with a parametric worst-case guarantee relative to the optimal solution.
We next use our model to study the interplay between the post promotion-dip effect and crossitem effects. We convey that when the degree of substitution increases, it becomes optimal to reduce the number of promotions. We also conduct several computational tests to show that the App(2) method can be successfully applied in realistic instances. We first test the tightness of the LP relaxation when the sufficient conditions are relaxed. In the majority of our tested instances, solving the LP relaxation leads to an integer solution. We then show that solving the mixed IP is relatively fast, and can be done in reasonable runtimes. Finally, we use our method to draw managerial insights on the interplay of the time and cross-item effects. More generally, the results presented in this research can guide retailers to test different promotion strategies and sharpen their understanding on promotion planning. each other out. Therefore, all the coefficients with three items simultaneously on promotion are As before, the last step follows from canceling terms. Note that all pairs of items where item i is not included have a contribution of zero.

Proof of Corollary 1
Corollary 1 can be shown in a similar way as the proof of Theorem 1 by refining the definition of App(2) to include all the pairwise contributions of two simultaneous promotions: both for different items at the same period and for the same item within M i consecutive periods. In this case, when the function h i t p i t , p i t−1 , . . . , p i t−M i is additively separable for each item, we obtain that the resulting objective function can be expressed as a sum of functions, and each function depends on at most two binary decision variables. Consequently, the same argument as in Theorem 1 applies.

Proof of Lemma 1
Proof. Recall that the pairwise coefficient for items i and j at time t is given by (we drop the time index for clarity): b ij = M P OP (i, j) − M P OP (i) − M P OP (j) + M P OP (0).
As before, M P OP (i, j) denotes the total profit generated by all N items during the T periods, when only items i and j are on promotion at time t. We note that all the terms at times different than t are zero. We also note that the coefficient in equation (17) has three different types of contributions (for items i, j, and k = i, j at time t). We next show that each one of the three contributions is non-negative.
1. For item i at time t, we have: We know that q 0 ≥ p i