Pricing heterogeneous products to heterogeneous customers who buy sequentially

Abstract

This paper considers optimal pricing in a system with limited substitutable resources, such as certain goods or services. Prices for the different resources have to be set and then customers with heterogeneous preferences show up sequentially. Customers, of n types, select an item from the m available resources, depending on their valuations of the resources and the prices. The goal is to analyze this optimization problem, characterize a set of candidates to optimal solutions and provide methods for solving it. We prove that this problem is NP-hard to approximate within a factor $O(n^{1-\varepsilon })$ for any fixed $\varepsilon >0$. Another important contribution is to prove that, the space of prices (which in principle is a continuous domain in ${\mathbb {R}}^m$), can be reduced to a finite set of vectors of cardinality $m^{m-2}n^m2^m$. For a deterministic version of the problem, where the customer types are known to the firm, we provide a mathematical program that chooses the best set of prices. We report extensive computational results showing the usefulness of our exact approach to solve medium size problems with up to 200 customers and different assortments of products and customer types. We then show how to approximate the stochastic model by a small number of solutions of deterministic scenarios solved using a mixed-integer linear program.

1 Introduction

Our general setting concerns optimal pricing in a system with two-way (or horizontal) substitutability. A manager sets a price for each resource (product or service) and then customers with heterogeneous preferences show up sequentially. Customers select an item from the available resources, depending of their valuations of the resources and the prices. A resource may be depleted during the process and subsequent arrivals must compromise and either select a less desired resource or even give up and leave empty handed. The manager’s goal is to maximize profits or welfare by selecting adequate prices. We denote this model as the max-surplus choice with limited substitutable resources (MSCLS) problem.

In the short-run problem, the firm has given quantities of items from each type, and its goal is to set their prices so as to maximize the firm’s expected profits. The expectation may be over the number of arrivals and their types, but mainly over the order by which they arrive. In the long run problem, the quantities of each type of the product are also decision variables.

One of our important contributions is reducing the set of admissible prices to only a finite set. We then formulate a scenario-based mixed-integer linear programming (MILP) model which chooses, for a given scenario (i.e., sequence of customer types) the best set of prices among the continuum set. We illustrate the usefulness of our MILP formulation to solve actual problems with random arrivals based on simulations of customers’ arrival scenarios.

In the closest paper to ours, Burkart et al. (2012) formulate an MILP and suggest exact and heuristic algorithms for a variation of our model. They assume a deterministic demand process, i.e., the sequence of customer arrivals and their preferences is known to the decision maker. We note that they provide real life examples to justify the model, but in these examples it is more natural to assume, as we do, that the sequence of arrivals is stochastic. They also assume that the prices should be taken from a set of discrete possible values. Mayer and Steinhardt (2016) extend the model of Burkart et al. allowing each customer to purchase more than a single type of a product subject to individual budget constraints. Moon et al. (2017) also extend this model assuming that the initial inventory level, and the prices, are decision variables, and the firm incurs fixed and variable inventory costs. They suggest a hybrid genetic algorithm.

Several authors considered models closely related to ours but where the decision variables are the inventory ordering quantities rather than the prices, and the arrival process is deterministic.

In an early paper, Khouja et al. (1996) assume that the amount purchased is independent in this model of the order by which customers arrive. Instead, it is assumed that if the demand for one product exceeds the ordered quantity then part of it, a certain proportion, can be substituted by the other products. Ryzin and Mahaja (1999) assume a multinomial logit (MNL) choice decision, while Smith and Agrawal (2000) assume that customers who do not find their first choice randomly choose according to a logit model a substitute or leave without buying. Mahajan and Ryzin (2001a) characterize and compute the optimal initial inventory levels by applying a stochastic gradient algorithm. Li (2007), Maddah and Bish (2007), Rusmevichientong et al. (2010), and Bernstein et al. (2015), assume that customers randomly select a product from the existing inventory, or give up purchase, according to a multinomial logit model. An algorithm based on dynamic programming is given by Honhon et al. (2010). Burnetas and Kanavetas (2018) consider a multi-period scenario with two products and base-stock replenishment policy. They develop a Markov-chain model assuming that there are given substitution probabilities, $p_{ij}$ that customers of type i are ready to purchase product type j if their first preference product i is not available. They obtain analytic formulas for the profit function, leading to an efficient algorithm for computing the profit-maximizing order quantities. Mahajan and Ryzin (2001b) consider competition in the model of Mahajan and Ryzin (2001a). Each of the product types is sold by a different firm, and the authors compute the Nash equilibrium ordering strategies and the impact of competition on profits. Nagarajan and Rajagopalan (2008) compute base-stock policies in a similar multi-period model.

Other papers, such as Stavrulaki (2011), generalize the model by adding demand stimulation effects, meaning that the demand depends also on the initial inventory (the ordered quantities). Netessine and Rudi (2003) consider a multi-product model with a single substitution attempt: If the demand for product i exceeds the stored quantity, the unmet demand will attempt to purchase product j as a substitute, if available, and then the unmet demand is lost. Salameh et al. (2014) consider a deterministic EOQ-type two-product model with partial substitution.

The main feature of our MSCLS problem is that the profit depends on the order of customer arrival types, which affects the availability of products for future arrivals. This feature reminds of, but is different from, secretary-type models and other online optimization models. In those models the order of type arrivals is random, as in our case, but the decision is dynamic and done after information is gathered on the type distribution, while profit depends on current and future arrivals. In our case, we assume that the distribution is known, but the order of arrivals is random. The decision maker sets the prices once and then each arrival selects its favorite item type from the available selection. See, for example, Babaioff et al. (2008). Our model is an off-line model where the firm sets prices once. But, in some aspects it resembles an on-line setting, such as described, for example, by Stein et al. (2020). The crucial difference is that unlike the on-line models where the firm assigns products to customers without having information on future arrivals, in our model the customers are strategic and make their own choice given the availability of product types, their values, and their prices.

Buchbinder and Gonen (2015), Korula et al. (2018) and Buchbinder et al. (2020) solve related online models where there are m products and n buyers, and buyer i values the subset of products S at $V_i(S)$. In the former paper, buyers arrive sequentially, whereas in the two latter papers the items arrive sequentially. The goal in both models is to assign the items, online, and maximize the total welfare. Buchbinder and Gonen’s paper is closest to ours. The main differences are that they allow dynamic choice of prices which are used to induce buyers to purchase the desired items under asymmetric information about their preferences. In our model, in contrast, the prices must be fixed once for the complete horizon, and we discuss both welfare and profit maximization.

Our research is also related to the paper by Gilland and Heese (2013). This paper, as ours, assumes that product sales and profitability depend on the specific sequence of customer arrivals rather than only on the aggregate demands for the different products. The focus of Gilland and Heese (2013) is on evaluating the impact that the sequence of arrivals has on sales and profits. We do the same, but they assume given prices (and two products and two customer types). Their problem is to determine the assortment and inventories subject to constrained shelf space. They derive the probabilities that the n-th arrival is of a given type and finds his best or second-best choice or none of them, derive monotonicity properties, and conduct a numerical study that compares three heuristics (they refer to them as benchmarks).

Related models correspond to queueing systems with heterogeneous customers, where the order of arrival types has an effect on the performance of the system. For example, there may be setup costs or setup times between the processing of customers of different types. See also Cláudio et al. (2016)

Another related problem is the Product Line Design Problem considered in Bertsimas and Mis̆ić (2019). In this problem, the decision is to choose a subset of products to be offered in order to maximize the profit that is realized when customers make purchases according to their preferences. In this model, inventory is unlimited, there is a finite set of customer types each having a preference ranking over the products, profit for each product is known and fixed, and there is a number of admissible product types designs chosen from a polyhedral set. The model chooses the best design and the best assignment of customer types to that design according with the fixed rankings.

The paper by Yücel et al. (2009) is related to the assortment problem and the decisions are made on which product to offer and their inventory (how much to order from each supplier); however there are no decisions on prices; which are given. They assume random demand and employ a scenario-based approach to handle it. Note that in our setting, the order of demand affects profits because the inventory levels are finite and customers may substitute to less desired products. In contrast, in the assortment problems the inventory is unbounded but there may be a cost per holding each type of product.

The rest of the paper is organized as follows: In Sect. 2.1 we analyze the complexity of the MSCLS problem showing that even the single-customer problem is NP-hard to approximate. Section 2.2 is devoted to give insights on the solutions of the simplest problem with two products and one customer type, whereas Sect. 2.3 analyzes the case of two products and two customers types. Next, Sects. 2.4 and 2.5 extend the characterization of solutions to the more general case of two products and n customers types and the fully general situation with m products and n customers types. Moreover, in Sect. 2.5 we prove the existence of a finite dominating set, i.e. a finite set of candidates, of prices for optimal solutions of the problem, and use it to solve instances of relatively small size. Section 3 provides an exact mixed integer linear programming (MILP) model to solve the deterministic version of the MSCLS problem where the firm knows the sequence of customer types. Extensive computational results on two different types of randomly generated data are reported in Sect. 3.1. Interestingly, we observe that, what may seem to be counter-intuitive, when we are concerned with social welfare, it is more important to control the prices when there is enough inventory than when there is short inventory. Based on the results we gather in this section some managerial insights comparing the profit-maximizing solution with the system welfare are given. We then show in Sect. 4 how to approximate the stochastic instances of medium size by a small number of solutions of deterministic scenarios solved with our MILP formulation. The paper terminates in Sect. 5 with some concluding remarks and extensions of the current works worth to be investigated.

2 The problem: complexity and special cases

In the MSCLS problem, a monopolistic firm sells m types of a certain class of products. Let $p_j$ denote the price set by the firm for a unit of type j, $j=1,\ldots ,m$. Customer types, $i=1,\dots ,n$ are random with a given probability distribution. Customers of type i value the unit of type j at $v_{ij}\ge 0$. Given prices $p_1,\ldots ,p_m$ we denote by $u_{ij}=v_{ij}-p_j$ the net utility to a customer of type i who buys an item of type j (note that we simplify the notation and do not mention the price $p_j$ explicitly). Customers sequentially inspect the set $S\subseteq \{1,\ldots ,m\}$ of available types and depending of their type i computes $j^*=\arg \max \{u_{ij}|j\in S\}$. If $u_{i,j^*}<0$ the customer balks, i.e., leaves without making a purchase. Otherwise the customer buys a unit of type $j^*$. Two goals are considered in this paper maximization of overall profit ($p_j$) or welfare ($v_{ij}$). The latter given as the summation of the values given for customer i to product j, namely $v_{ij}$, for all i, j over all customers and purchased products.

2.1 Complexity of the MSCLS problem

The single-customer problem can be shown to be NP-hard to approximate within factor $O( n^{1 - \epsilon })$, for any fixed $\epsilon > 0$. This inapproximability bound follows by adapting an analogous hardness result due to Theorem 1 in Aouad et al. (2018), which establishes a relationship between computing large independent sets in graphs and assortment optimization under the ranking-based choice model. In the former problem, given an undirected graph $G = (V,E)$, a subset of vertices $U \subseteq V$ is independent when no pair of vertices in U is joined by an edge. The objective is to compute an independent set of maximal cardinality. In this context, Hastad (1996) showed that the independent set problem on n-vertex graphs cannot be approximated in polynomial time within factor $O( n^{1 - \epsilon })$, for any fixed $\epsilon > 0$, unless $\textrm{P} = \textrm{NP}$. See Aouad et al. (2018) for details.

Given an independent set instance, $G = (V,E)$ with $V = \{ v_1, \ldots , v_n \}$, we define the set of customer types as [n]. Each type $i \in [n]$ is sampled with probability $\frac{ \alpha }{ n^{2i} }$, where $\alpha =(\sum _{i\in [n]}{1\over n^{2i}})^{-1}$ is a normalization constant. In addition, the set of products is [n], and the value customer of type i associated with product j is given by:

$$\begin{aligned} v_{ij} = \left\{ \begin{array}{ll} n^{2i}, \qquad &{} \quad \text {if } j=i \\ n^{2j+1}, \qquad &{}\quad \text {if } j < i \text { and } (v_i, v_j) \in E \\ -\infty , \qquad &{} \quad \text {otherwise}. \end{array} \right. \end{aligned}$$

Observation: The optimal prices satisfy $p_j^*\in \{n^{2j},n^{2j+1},\infty \}$.

Let $R^*= {\mathbb {E}}[p^*]$. We now show that the size of the maximum independent set is within $[{R^*\over \alpha }-1,{R^*\over \alpha }].$

Consider an independent set $U \subseteq V$ and define the pricing vector $p_j=n^{2j}$ if $v_j\in U$ and $p_j=\infty$ otherwise. A customer of type i buys product of type i (since every product $j\ne i$ either has $v_{ij}=-\infty$ or $p_j=\infty$), and the expected price paid by a customer is ${\mathbb {E}}[p] \ge \sum _{j\in U}p_j{\alpha \over n^{2j}}=\alpha |U|$.

In the opposite direction, we claim that there is an independent set in G consisting of at least $R^*-O(1)$ vertices. To verify this claim, note that with respect to any pricing vector that satisfies the observation, every customer type $i\in [n]$ can either:

• 1. Purchase product i (only if $p_i=n^{2i}$).

• 2. Purchase product $j<i$ such that $(v_i,v_j)\in E$ at a price of at most $n^{2j+1}\le n^{2i-1}$.

• 3. Not purchase any product.

The individual contribution toward $R^*$ is $\alpha$ in the first case and at most${\alpha \over n}$ otherwise. Let U consist of the customes who fall in case 1. We observe that:

• 1. $|U|\ge {R^*\over \alpha }-1$ since by the preceding discussion, $R^* \le \le \alpha |U|+{\alpha \over n}(n-|U|)\le \alpha (|U|+1).$

• 2. U is an independent set in G. To verify this claim, suppose that two vertices $v_{i_1}\ne v_{i_2}\in U$ were joined by an edge; without loss of generality, $i_1 < i_2$. Since $i_1$ purchases product $i_1$ we must have $p_{i_1} = n^{2i_1}$. As a result, customer $i_2$ associates a utility of $n^{2i_1+1}-n^{2i_1}>0$ with product $i_1$ and a zero utility with product $i_2$, in contradiction to the fact that $v_{i_2}\in U.$

2.2 Two product types and one customer type

This section analyzes the special case of two product types and a single customer type, while introducing our solution approach. Suppose all customers are of the same type, which we call type i. If both products are available, the customer compares $u_{i1}:=v_{i1}-p_1$, $u_{i2}:=v_{i2}-p_2$, and 0. Assuming that $v_{i1}$ and $v_{i2}$ are fixed, we view this decision as a function of the prices. There are five possibilities:

• $u_{ij}<0$ for $j=1,2$. i-customers balk. We denote this possibility by the preference ranking $\mathbf {(0)}$.

• $u_{i1}\ge 0>u_{i2}$. i-customers purchase a 1-item if $1\in S$, otherwise they balk. We denote this possibility by the preference ranking $\mathbf {(1)}$.

• $u_{i2}\ge 0>u_{i1}$. i-customers purchase a 2-item if $2\in S$, otherwise they balk. We denote this possibility by the preference ranking $\mathbf {(2)}$.

• $u_{i1}\ge u_{i2}\ge 0$. i-customers purchase a 1-item if $1\in S$, they purchase a 2-item if $S=\{2\}$, and balk only if $S=\emptyset .$ We denote this possibility by the preference ranking $\mathbf {(12)}$.

• $u_{i2}\ge u_{i1}\ge 0$. i-customers purchase a 2-item if $2\in S$, they purchase a 1-item if $S=\{1\}$, and balk only if $S=\emptyset .$ We denote this possibility by the preference ranking $\mathbf {(21)}$.

The five regions are shown in Fig. 1. The partition is determined by the point $(v_{i1},v_{i2})$ which we call the pivot point.

Considering the firm’s pricing choice, since the product ranking is fixed in any region, the firm’s choice would be to set the highest possible value for each price as long as it stays in the region. In the upper-right region there are no sales and prices are not relevant. In the other two outer regions, one of the prices is not relevant, and can be decreased, without loss of generality, towards the bordering inner region.

In the two inner regions, the firm profits from increasing both prices, and the optimal point is the upper-right point of the region. The arrows in Fig. 1 mark the directions in which profits increase without changing customers’ preferences.

We conclude that the optimal prices are $p_1=v_{i1}$ and $p_2=v_{i2}$, but the firm can still choose, by a slight reduction in one of the prices, the product that customers will prefer when both product types are available. Specifically, if $v_{i1}>v_{i2}$ then the firm will set $p_1=v_{i1}-\epsilon$ for a small $\epsilon >0$ to induce sales of product 1 which entail a higher profit. Similarly, if $v_{i2}>v_{i1}$ the firm will reduce $p_2$ by a small amount.

Fig. 1

Preference space of i-customers

Remark 2.1

As we see, in all candidates for optimality, the prices are equal to the customer’s welfare. In other words, the net consumer surplus is zero. Therefore, the monopoly’s profit is equal to the social welfare, and maximization of profit also achieves maximum social welfare.

2.3 Two product types and two customer types

Consider now the joint selections of two customers, say customer types i and j. Without loss of generality, assume $v_{j1}>v_{i1}$, and to simplify the exposition by avoiding tie-breaking rules in case of indifference, we assume $v_{j2}\ne v_{i2}$. There are three cases depending on the relative locations of the pivots of customers of types i and j, and each case is further divided into two subcases:

• 1. $v_{j2}<v_{i2}$

  • (a) $v_{j1}-v_{j2}<v_{i1}$,

  • (b) $v_{j1}-v_{j2}>v_{i1}$;

• 2. $v_{j2}>v_{i2}$ and $v_{j2}-v_{j1}<v_{i2}-v_{i1}$

  • (a) $v_{j1}-v_{j2}<v_{i1}$,

  • (b) $v_{j1}-v_{j2}>v_{i1}$;

• 3. $v_{j2}>v_{i2}$ and $v_{j2}-v_{j1}>v_{i2}-v_{i1}$

  • (a) $v_{j2}-v_{j1}<v_{i2}$,

  • (b) $v_{j2}-v_{j1}>v_{i2}$.

We now analyze the case $v_{j2}<v_{i2}$. The analysis of the other cases is similar and we present it in the appendix.

Fig. 2

Preference space of i- and j-customers

The case 1(a), i.e., $v_{j2}<v_{i2}$ and $v_{j1}-v_{j2}<v_{i1}$, is shown in Fig. 2. The joint performance space has thirteen regions. We call the five open regions outer regions, and the other regions inner regions. Case 1(b) is similar except for that the pivot of customer type j moves to the right so that region (21,21) in Fig. 3 disappears.

Considering the firm’s pricing choice, since the ranking by both customers are fixed in any region, the firm’s choice would be to set the highest possible value for each price as long as it stays in the region. The arrows in Fig. 2 mark the directions in which profits increase without changing customers’ preferences. Note that in the upper-right region there are no sales and prices are not relevant. In the other four outer regions, one of the customers buys only one of the products and the other customer either doesn’t buy any product or buys only the same product as the first customer. This means that in these regions one of the prices is not relevant, and can be decreased, without loss of generality, towards the bordering inner region.

In all other eight regions, the firm profits from increasing both prices, and the optimal point is the upper-right point of the region.

Claim 2.2

Without loss of optimality, the profit-maximizing prices are not set in any of the outer regions.

Proof

The upper-right region is clearly not optimal since there are no sales there. In the other outer regions only one product is sold. Decreasing the price of the other product till we reach another region enables sales of this product when the other one is not available, while not affecting the sales of the other product that remains the preferred one for both customer types. $\square$

We mark the preference types related to customers i and j. For example, in region $\mathbf {(12,1)}$, i-customers’ preference is $\mathbf {(12)}$ and j-customers’ preference is $\mathbf {(1)}$.

Fig. 3

Customer preferences: $v_{j1}>v_{i1}$ and $v_{j2}<v_{i2}$

The above discussion leaves, in the case given in Figs. 2 and 3, the following eight candidates for optimal pricing:

• 1. $(v_{i1},v_{i2})$

  • (a) from region (21,1),

  • (b) from region (12,1);

• 2. $(v_{j1},v_{j2})$

  • (a) from region (2,12),

  • (b) from region (2,21);

• 3. $(v_{j1},v_{i2})$

• 4. $(v_{i1},v_{j2})$

• 5. $(v_{i1}-v_{i2}+v_{j2},v_{j2})$,

• 6. $(v_{i1},v_{i1}+v_{j1}-v_{j2})$.

Remark 2.3

Social welfare depends on customer choice and is affected by the customers choice as determined by the partition of the plane as induced by the prices. However, the welfare is independent of the exact point within the cell.

We observe that the best pricing in both regions (21,1) and (12,1) are $(v_{i1},v_{i2})$. Similarly, the best pricing for regions (2,12) and (2,21) is $(v_{j1},v_{j2})$. However, the firm can choose, by a slight change of the prices, whether it wants to reach these points from one of the regions or the other. The better choice between such a pair of options that have identical prices, is determined by the available quantities of the products and the number of customers of each type.¹ For the other candidates, it is easy to see that the best preference region that contains them is such that the candidate prices are at its upper-right corner, as in Fig. 3.

To illustrate the use of these insights, consider a simple case were there is one item of each type and one customer of each type, and the preferences are as in Fig. 3. Except for two cases, the profit will be $p_1+p_2$. For example, with prices $v_{j1},v_{i2}$ and preferences (2,1), both customers will buy their preferred type for any order of their arrival, with profit $p_1+p_2$. However, in region (12,1), if the i-customer arrives first, she will buy product 1, and customer j will not make a purchase. The expected profit will be then $p_1+0.5p_2$. In this simple example, the optimal pricing is $(v_{j1},v_{i2})$ which clearly dominates the other candidates.

Denote by $I_\ell$ the number of type $\ell$ items available for sale, and suppose that the number of customers of type i is fixed at $c_i$. With the input values $(v_{i\ell })$, the prices determine the rank vector R. To compute an optimal pricing policy we need to be able to compute $\Pi (R,p)$, the expected profits (over the permutation of arrivals of customers) associated with a given set of prices, $p=(p_1,p_2)$ and the resulting rank vector R.

For example, consider the case where all customers prefer product type 1, and only type 1 customers are ready to purchase product type 2, i.e., $R=$(12,1).

• If $I_1\ge c_1+c_2$ then $\Pi =p_1(c_1+c_2)$.

• Suppose $I_1<c_1+c_2$. Denote by q(k) the probability that among the first $I_1$ arrivals there are exactly k type 1 customers. Then,

  $$\begin{aligned} q(k)={{c_1\atopwithdelims ()k}{c_2\atopwithdelims ()I_1-k}\over {c_1+c_2\atopwithdelims ()I_1}}. \end{aligned}$$

  The value of k satisfies of course $k\le c_1$ and $I_1-k\le c_2$, hence $k\in [I_1-c_2,c_1]$. The expected profit is therefore

  $$\begin{aligned} \Pi =p_1I_1+\sum _k q(k)\cdot \min \{c_1-k,I_2\}p_2, \end{aligned}$$

  and social welfare equal

  $$\begin{aligned} S=\sum _k q(k)\left\{ kv_{11}+(I_1-k)v_{21}+\min \{c_1-k,I_2\}v_{12}\right\} . \end{aligned}$$

  A similar computation applies for region (2,21).

• In the other cases, the sales, profits, and welfare are deterministic. The case (1,2) (and similarly and (2,1)) is, of course, simple, and the sales of product i are $\min (c_i,I_i)$. In the case (21,1), the profit is also deterministic, and equal $p_2\min (c_1,I_2)+p_1(\min (I_1,c_1+c_2-\min (c_1,I_2)).$ Finally, for (21,12)), the sales of product 1 are like in the case (21,1) and the sales of product 2 are as in the case (2,12).

2.4 Two product types and n customer types

Suppose that there are n customer types, and two product types. We form the joint performance space of these n customer types. To each pivot there are 3 lines, the horizontal, the vertical, and the one with slope of 45 degrees. The candidate points for optimal prices are the intersections of these lines. The performance space is characterized by the ranking of the input values $\{v_{i1}\}, \{v_{i2}\}$ and $\{v_{i1}-v_{i2}\}$ for all $i=1,\ldots ,n$. The number of candidates pricing options becomes quadratic in n. For each candidate we know the ranking vector associated with it. We compute and compare $O(n^2)$ return values.

2.5 m product types and n customer types: Structure of the solutions of the problem

Let us assume that we have m product types and n customers. The availability of products is described by the vector $I=(I_1,\ldots ,I_m)$, $I_j$ is the number of items for product type j. Moreover, we suppose a constant number of customers $c_i$ of class i. Thus, $C=(c_1,c_2,\ldots ,c_n)$ is the overall population of buyers and $\sum _{i=1}^n c_i$ is the size of the population.

The feature space, i.e., the space of meaningful prices is a subset of ${\mathbb {R}}^m_+$. This space is subdivided into cells where the preferences of customers are constant with respect to the product types. In other words, the order of the preferences over the products does not change. It is not difficult to see that these cells are induced by the following arrangement of hyperplanes:

$$\begin{aligned} p_j=&v_{ij},&i=1,\ldots ,n,\; j=1,\ldots ,m, \end{aligned}$$

(1)

$$\begin{aligned} p_j-p_k=&v_{ij}-v_{ik},&i=1,\ldots ,n,\; j\ne k=1,\ldots ,m. \end{aligned}$$

(2)

Recall that the combinatorial complexity of an arrangement is the overall number of cells of all dimensions in this arrangement. It is well-known that the combinatorial complexity of an arrangement of n hyperplanes in ${\mathbb {R}}^m$ is $\Theta (n^m)$, see e.g. (Edelsbrunner 2012, Chapter 7) and (Halperin 2004, Chapter 24).

Overall, the number of hyperplanes that are relevant to determine the prices is $O(m^2n)$ in ${\mathbb {R}}^m$. Therefore, the combinatorial complexity of this arrangement is $\Theta (m^{2m}n^m)$. Vertices of the cells in this arrangements are candidate prices. The complexity of the number of vertices is bounded above by the overall number of cells of any dimension. Therefore, the number of candidate prices is $O(m^{2m}n^m)$.

We recall that a finite dominating set for a problem is a finite subset of its feasible domain where one can always find an optimal solution of the problem. The reader should observe that the set of admissible prices for this problem is a continuum set of ${\mathbb {R}}^m_+$. However, as it is stated in our next result one can reduce to a finite set to find an optimal solution for the MSCLS problem.

Theorem 2.4

There exists a finite dominating set of admissible prices for the MSCLS model considered in this paper.

The proof follows from the discussion above since one can always find an optimal solution of the corresponding problem among the vertices of the cells induced by the arrangement, ${\mathcal {A}}$, of hyperplanes (1) and (2).

We note in passing that if the number of products m is fixed, then the number of candidate prices is polynomial in the number of customers.

Within each cell of this arrangement one can determine an n-vector $s=(s_1,\ldots ,s_n)$ where $s_i$ is an ordered tuple with up to m elements, $s_i=(j_1,\ldots ,j_m)$. The index $j_\ell$ is the customer i’s $\ell$-th most preferred product type in that region.

Then, for a given configuration of values $v_{ij}$ for all $i=1,\ldots ,n,\; j=1,\ldots ,m$, and inventory levels I, the goal is to compute for each cell $A\in {\mathcal {A}}$, the expected value of the reward obtained with respect to the permutations of arrivals.

$$\begin{aligned} \Pi (A) = \frac{1}{\# \textrm{PR}(C)} \sum _{\sigma \in \textrm{PR}(c_1,\ldots ,c_n)} \sum _{j=1}^m p_j N_j(A,I,\sigma ) \end{aligned}$$

(3)

where $\textrm{PR}(C)$ is the set of permutations with repetition of C, $N_j(A,I,\sigma )$ is the number of items of type j from I, bought by the customers in C when they arrive in the order induced by $\sigma$ and $p_j$ is the price of item j in the cell A.

The reader may note that to get the expected value of the reward, $\Pi$, for a given configuration v of values and inventory level I, it suffices to compare the values $\Pi (A)$ for all $A\in {\mathcal {A}}$,

$$\begin{aligned} \Pi = \max _{A\in {\mathcal {A}}} \Pi (A). \end{aligned}$$

(4)

Needless to say, this evaluation requires to explicitly enumerate all the cells in ${\mathcal {A}}$. This is a difficult task because of the number of such cells but also because one must generate them explicitly.

In the following, we show 1) how to refine (reduce) the number of cells (candidate price vectors); and 2) how to efficiently evaluate implicitly all the cells by two different methods.

Refined number of candidate price vectors: We now improve the bound on the number of cases to be compared.

Let’s add a new product that corresponds to balking (not buying any product) indexed 0 with $p_0=0$ and $v_{i0}=0$ for all i.

Consider a candidate vector of prices (corresponding to a vertex of the arrangement of hyperplanes), $p_0=0,p_1,\dots ,p_m$. To avoid dealing with ties, assume that the $v_{ij}$ values are in “general position” so that no linear combination of them with $0,\pm 1$ coefficients equals zero.

Consider the indifference graph G with $m+1$ vertices corresponding to the products (including product 0), and edges corresponding to the pairs of products (j, k) for which there exists a customer i who is indifferent between the products, i.e., $v_{ij}-v_{ik}=p_j-p_k$.

Note that G does not contain a cycle except for cycles induced by the same customer i (such cycles follow from transitivity—if customer i is indifferent between products j, k and between k, l then i is also indifferent between j and l). Otherwise, consider a cycle where not all edges are induced by the same customer, and follow it according to an arbitrary orientation. The price differences over the edges of this cycle sum up to zero, and this means that the sum of the value differences is also zero, contradicting the general-position assumption. Now, orient each edge so that it points to the product which the customer is induced to prefer by the perturbation of prices selected by the solution.

Note that when the indifference graph contains a connected component related to the same customer type, these preferences are induced by a directed path that spans this component, which gives the associated permutation. Replacing the component by that path, and ignoring the other indifference edges in this component, yields a directed forest, which we also call G.

Claim 2.5

Under the optimal set of prices, the underlying undirected graph of G is a spanning tree.

Proof

Otherwise, we can simultaneously increase the prices of products related to a component that does not include product zero, without affecting the customers’ preferences. $\square$

Consider the cells adjacent to the given point. The preferences in each cell correspond to a digraph obtained from G by orienting its edges, say from the more preferred product to the less preferred. It is possible to induce these preferences by small reductions in the prices, starting from leaves of the tree.

There are $m^{m-2}$ spanning trees, and each has $n^m$ possible assignments of customer types and $2^m$ orientations. Therefore the number of cells to be checked is $m^{m-2} n^m 2^m$.

We conclude that when m and n are relatively small it is possible to enumerate the set of candidates of price vectors. To complete the solution we need a way to compute the best one among them by evaluating the expected value of each. We propose two methods for doing it. The first is an exact method that can be implemented when the number of arrivals is not too large, and the second is a faster heuristic.

It is easy to compute recursively the expected profit associated with a given price vector. For example, suppose that the number N of arrivals is given but not their types which are random variables. Let $q_i$ be the probability that a customer is of type i, where these events are independent. The formulation for a deterministic scenario is very similar. Let $f_\ell (I)$ be the expected profit when there are $\ell$ customers to arrive and inventory levels $I=(I_1,...,I_m)$. Then

$$\begin{aligned} f_\ell (I)= & {} \sum _{i=1}^n q_i (p_{j(i)}+f_{\ell -1}(I\setminus e_{j(i)})): \ j(i) \mathrm{~ is~ the~ most~ preferred~ item~ in~ }\\{} & {} \{k:I_k>0\}\mathrm{~for~ an~} i\mathrm{-customer} , \end{aligned}$$

where $e_j$, $j=1,\ldots ,m$ is the j-th canonical vector of ${\mathbb {R}}^m$ and $e_0$ is the null vector if the customer $i_\ell$ balks. In a preprocessing phase we generate preference lists, one for every product type. Then, whenever a product type is depleted, we go over these lists and delete this product type. All these deletions take O(mn) which is dominated by the other operations, and then finding the preferred product for a customers from the available inventory takes constant time. If all I-values are bounded by U then the complexity is $O(nNU^m)$. Finally, we repeat this computation for each of the $O(m^{m-2}n^m 2^m)$ admissible price vectors. This approach is valid although very costly, due to the high number of evaluations required for its application.

Note that, without loss of generality, we can assume that $U\le N$. When N is large we suggest an alternative approach. For given prices we apply Monte Carlo simulation by generating many scenarios (sequences of arrival types of customers). We estimate the expected profit associated with these prices by taking the average profit across these scenarios.

Due to the large cardinality of the state space of our recursive approach, we propose an alternative, more efficient procedure for optimizing the profit in our model, including a detailed description of the Monte Carlo method for medium-sized instances will given in Sects. 3 and 4. The alternative approach is based on a mixed-integer linear programming formulation that takes advantages of implicit enumeration of feasible solutions based on pruning and bounding, as usual in mathematical programming models.

3 A mixed integer linear programming (MILP) formulation for the evaluation of optimal policy prices in the MSCLS problem

The goal in this section is to find a valid MILP formulation that computes the optimal prices and optimal reward, $FO(I,\sigma )$, provided that a deterministic arrival scenario $\sigma$ and inventory level vector I, are given. The computation of $FO(I,\sigma )$ is provided in formulations (6)–(23) and (27)–(38). Then, it is possible to obtain the expected value of the reward $\Pi$ for any deterministic scenario determined by a set of customers C, inventory level I and configuration of values v

$$\begin{aligned} \Pi = \frac{1}{\# \textrm{PR}(C)} \sum _{\sigma \in \textrm{PR}(c_1,\ldots ,c_n)} FO(I,\sigma ). \end{aligned}$$

(5)

In order to obtain a valid formulation for the computation of $FO(I,\sigma )$, we consider the following elements. A set of inputs which are given.

• The deterministic arrival scenario, $\sigma$, is known and there are K arrivals. To simplify the presentation we assume that each client has its own type and preference and therefore, we identify the index of the customer with the stage when it arrives.

• Let ${\hat{v}}_{rj}$ denote the r-th highest admissible price given by the different customers to product type j. We assume that there are $N_j$ such admissible prices induced by the finite dominating set described in Sect. 2.5. It is clear that ${\hat{v}}_{1j}\ge {\hat{v}}_{2j}\ge \ldots \ge {\hat{v}}_{N_jj}$ for all $j=1,\dots ,m$.

• The initial inventory levels of the different product types $I_j$ for $j=1,\ldots ,m$.

We define the following variables:

• $p_j$ is the price assigned to the j-th product type, for $j=1,\ldots ,m$;

• $d_{rj}$ is equal to 1 if $p_j$ is set to ${\hat{v}}_{rj}$ and zero otherwise. Thus, $p_j$ is set to the rth highest admissible price given to product j. Then,

  $$\begin{aligned} p_j=\sum _{r=1}^{N_j} d_{rj} {\hat{v}}_{r j},~~~~~~~~~\forall j=1,\ldots ,m \end{aligned}$$

• $z_{ij}$ is equal to 1 if customer i is willing to buy product type j at the price $p_j$ (i.e., $v_{ij}\ge p_j$), and zero otherwise. Since optimal prices must coincide with one of the customers’ admissible prices we have represented $z_{ij}$ as a single choice equation. Then,

  $$\begin{aligned} z_{ij}=\sum _{r:{\hat{v}}_{rj}\le v_{ij}} d_{rj},&\forall \; i=1,\ldots ,K,\; j=1,\ldots ,m. \end{aligned}$$

• $\zeta _{jk}$ is equal to 1 if product j is available at period k;

• $w_{jk\ell }$ is equal to 1 if product type j is the $\ell$-th most preferred by customer k given the prices $p_1,\dots ,p_m$ and zero otherwise. These $w_{jk\ell }$ variables will allow us to implicitly enumerate all the ordered regions of preferences of customers on product types.

• $\eta _{jk\ell }$ is equal to 1 if at period k product j is available and it is the $\ell$-th most preferred for customer k given the prices $p_j$ and this customer is willing to buy it, and 0 otherwise. Actually, this means that $\eta _{jk\ell }=z_{kj}\zeta _{jk}w_{jk\ell }$. We observe that $\sum _{j=1}^m \eta _{jk\ell }=1$ states that at period k there is some product available for customer k with $\ell$-th level of preference, and this customer is willing to buy it.

• Moreover, we define variable $\alpha _{jk\ell }$ that equals 1 if customer k actually buys product type j at price $p_j$ provided that it is available and product j is the $\ell$-th most preferred. Formally, $\alpha _{jk\ell }$ are similar to the $\eta$ variables but imposing that only one of them can assume value 1 for each k:

  $$\begin{aligned} \sum _{j=1}^m\sum _{\ell =1} ^m \alpha _{jk\ell } \le 1, \quad k=1,\ldots , K. \end{aligned}$$

  These variables define the product actually bought at stage k, namely it is the product $j^*$ such that $\sum _{\ell =1}^m \alpha _{j^* k\ell }=1$. Here, the reader must also observe that customer k buys the $\ell$-th most preferred product at period k only if all the product types that are more preferred than the $\ell$-th one have been already sold. This relationship links variables $\eta$ and $\alpha$:

  $$\begin{aligned} \sum _{j=1}^m \eta _{jk\ell } + \sum _{j=1}^m \sum _{\ell ' = \ell +1}^m \alpha _{jk\ell '} \le 1, \qquad \forall k=1,\ldots ,K, \; \ell =1,\ldots ,m. \end{aligned}$$

  The above inequality states that if there is some available product for customer k with preference $\ell$ this customer, k, will not buy another product with lower preference. The reader should observe that since ${\eta _{jkl}=z_{kj}w_{jk\ell } \zeta _{jk}}$, in the non-linearized version of the formulation, this inequalities appear as (20):

  $$\begin{aligned} \sum _{j=1}^m z_{kj}w_{jk\ell } \zeta _{jk} + \sum _{j=1}^m \sum _{\ell ' = \ell +1}^m \alpha _{jk\ell '} \le 1, \qquad \forall k=1,\ldots ,K, \; \ell =1,\ldots ,m. \end{aligned}$$

• We denote by $A_{jk}$ the amount of product type j available just before the $(k+1)$st arrival occurs. We can compute recursively $A_{jk}$: $A_{j0}=I_j$ and $A_{jk}=A_{jk-1}- \sum _{\ell =1}^m \alpha _{jk\ell }$, for $k=1,\ldots ,K$, $j=0,\ldots ,m-1$. Observe that the variable $\zeta _{jk}$ is clearly defined by $A_{jk-1}$. Actually, $\zeta _{jk}$ equals 0 if $A_{jk-1}=0$, and 1 otherwise.

The objective function aims at maximizing the revenue along the planning horizon $1,\ldots ,K$ assuming that customers buy their most preferred available product type. In the case of welfare optimization, we simply replace $p_j$ by $v_{jk}$ in the objective function.

$$\begin{aligned} FO(I,\sigma ):=\max&\sum _{k=1}^K \sum _{j=1}^m \sum _{\ell =1}^m \alpha _{jk\ell } p_j \; \end{aligned}$$

(6)

$$\begin{aligned} \text{ s.t. }&p_j=\sum _{r=1}^{N_j} d_{rj} {\hat{v}}_{r,j}, \quad j=1,\ldots ,m \end{aligned}$$

(7)

$$\begin{aligned}&z_{kj}=\sum _{ r: v_{kj}\ge {\hat{v}}_{rj}} d_{ rj}, \quad \; k=1,\ldots ,K,\; j=1,\ldots ,m \end{aligned}$$

(8)

$$\begin{aligned}&\sum _{\ell =1}^m w_{jk\ell }\le z_{kj}, \quad j=1,\ldots ,m, \; k=1,\ldots ,K \end{aligned}$$

(9)

$$\begin{aligned}&\sum _{j=1}^m w_{jk\ell }\le 1, \quad k=1,\ldots ,K, \; \ell =1,\ldots ,m \end{aligned}$$

(10)

$$\begin{aligned}&\sum _{j=1}^m w_{jk\ell } (v_{kj}-p_j) \ge \sum _{j=1}^m w_{jk\ell +1} (v_{kj}-p_j), \quad \nonumber \\ {}&\quad k=1,\ldots ,K, \; \ell =1,\ldots ,m \end{aligned}$$

(11)

$$\begin{aligned}&A_{jk} =A_{jk-1} - \sum _{\ell = 1}^m \alpha _{jk\ell } \quad j=1,\ldots ,m, \; k=1,\ldots ,K \end{aligned}$$

(12)

$$\begin{aligned}&A_{j0} = I_j, \quad j=1,\ldots ,m \end{aligned}$$

(13)

$$\begin{aligned}&\sum _{j=1}^m \sum _{\ell = 1}^m \alpha _{jk\ell } \le 1, \quad k=1,\ldots ,K \end{aligned}$$

(14)

$$\begin{aligned}&\sum _{\ell =1}^m \alpha _{j k\ell }\le z_{kj}, \quad j=1,\ldots ,m, \; k=1,\ldots ,K \end{aligned}$$

(15)

$$\begin{aligned}&A_{j k-1} \le I_j\zeta _{jk}, \quad j=1,\ldots ,m, k=1,\ldots ,K \end{aligned}$$

(16)

$$\begin{aligned}&\zeta _{j,k}\le A_{j,k-1}, \quad j=1,\ldots ,m,\; k=2,\ldots ,K \end{aligned}$$

(17)

$$\begin{aligned}&\alpha _{jk\ell }\le w_{jk\ell }, \quad j,\ell =1,\ldots ,m, \; k=1,\ldots ,K \end{aligned}$$

(18)

$$\begin{aligned}&\alpha _{jk\ell }\le \zeta _{jk}, \quad j,\ell =1,\ldots ,m, \; k=1,\ldots ,K \end{aligned}$$

(19)

$$\begin{aligned}&\sum _{j=1}^m z_{kj}w_{jk\ell }\zeta _{jk} + \sum _{j=1}^m \sum _{\ell ' = \ell +1}^m \alpha _{jk\ell '} \le 1, \quad \nonumber \\ {}&\quad \ell =1,\ldots ,m-1, \; k=1,\ldots ,K \end{aligned}$$

(20)

$$\begin{aligned}&p_j, A_{jk} \ge 0, j=1,\ldots ,m, k=1,\ldots ,K,\end{aligned}$$

(21)

$$\begin{aligned}&d_{rj}\in \{0,1\},\; r=1,\ldots ,N_j, \; j=1,\ldots ,m, \end{aligned}$$

(22)

$$\begin{aligned}&z_{kj}, \zeta _{jk}, w_{jk\ell }, \alpha _{jk\ell }, \eta _{jk\ell } \in \{0,1\}, \, j,\ell =1,\ldots ,m, \; k=1,\ldots ,K . \end{aligned}$$

(23)

The objective function (6) computes the revenue in the entire planning horizon which is compatible with customers’ utilities. Indeed, if a customer arrives at period k then the price paid will be $p_j$ with the highest utility ($p_j-v_{kj}$) among those which are attractive for this customer and with available items ($A_{jk}>0, \, \zeta _{jk}=1$). Constraints (7) set the prices of the different product types. It is based on the observation that $p_j$ is equal to the admissible price ${\hat{v}}_{rj}$ of some customer, otherwise we can increase $p_j$ without affecting the sales pattern. Constraints (8) state whether the price set for product type j makes it attractive for the different customer types. Indeed, customer type k is willing to buy it only if $p_j$ is set to a value less than or equal to the customer’s utility of product j ($v_{k j}$) or in other words, if some variable $d_{rj}$ with $r: {\hat{v}}_{rj}\le v_{kj}$ is set to 1. We note in passing that constraints (8) also guarantee that the sum of $d_{rj}$ variables over r is $\le 1$ which is necessary for (7) to make sense. Constraints (9) imply that if the custumer arriving at k does not buy product type j ($z_{kj}=0$) then the preference of customer k over product type j is also zero. Constraints (10) ensure that for each customer type i, the preference ranking $\ell$ is assigned to at most one product type. Constraints (11) state the ranking of the preference regions for the prices: for each customer k, if $w_{jk\ell }=1$ and $w_{j'k \ell +1}=1$ then $v_{kj}-p_j\ge v_{kj'}-p_{j'}$, and thus for customer k product type j is better than $j'$. We observe that for each k an assignment of compatible values to $w_{jk\ell }$ for all $j,\ell =1,\ldots ,m$ defines the correct ranking of products types for this customer type in a region. Next, constraints (12) define the availability of product type j after the k-th arrival: $A_{jk}$ must be equal to the amount available at the previous stage minus the item bought by the customer that arrives at the k-th stage. In addition, constraints (13) set the initial inventory levels of product types. Constraints (14) define that at most one product is bought at stage k among those which are available. Constraints (15) tell that product type j can be bought by customer k only if the customer that arrives at this stage is willing to buy product j. Constraints (16) and (17) state the inventory of product types that are available at stage k. Constraints (18) and (19) define, with (14) and (15), the correct values of the $\alpha$ variables. Finally, constraints (20) enforce that customer k would buy some product type of its $(\ell +1)$ most preferred type only if all those belonging to its $\ell$ most preferred are not available. Conditions (21)–(23) define the range of variables.

The above problem seems is a valid formulation although it contains nonlinearities due to products of variables. In order to get an MILP, one must linearize those products of variables. Products of variables that explicitly appear in the formulation are: $w_{jk\ell } p_j$, $\alpha _{jk\ell } p_j$ and $z_{kj}w_{jk\ell }\zeta _{jk}$. In the following we handle these terms.

$$\begin{aligned} q_{jk\ell }&= p_jw_{jk\ell } \Leftrightarrow \left\{ \begin{array}{l} q_{jk\ell }\le p_j \\ q_{jkk}\le w_{jk\ell } M_j \\ p_j -M_j(1-w_{jk\ell }) \le q_{jk\ell } \end{array} \right. \end{aligned}$$

(24)

$$\begin{aligned} \beta _{jk\ell }&=\alpha _{jk\ell } p_j \Leftrightarrow \left\{ \begin{array}{l} \beta _{jk\ell } \le p_j \\ \beta _{jk\ell } \le M_j \alpha _{jk\ell } \\ p_j -M_j(1-\alpha _{jk\ell }) \le \beta _{jk\ell } \end{array} \right. \end{aligned}$$

(25)

$$\begin{aligned} \eta _{jk\ell }&= z_{kj}w_{jk\ell }\zeta _{jk} \Leftrightarrow \left\{ \begin{array}{l} \eta _{jk\ell } \le w_{j\ell } \\ \eta _{jk\ell } \le z_{kj} \\ \eta _{jk\ell } \le \zeta _{jk} \\ z_{kj}+w_{jk\ell }+\zeta _{jk} \le 2 + \eta _{jk\ell } \end{array} \right. \end{aligned}$$

(26)

The reader may realize that $q_{jk\ell }$ stands for the price given to the product type j if it is the $\ell$-th most preferred in the list of preferences of the customer arriving at k; whereas $\beta _{jk\ell }$ is the price of product type j if $\alpha _{jk\ell }=1$. We observe that the third case in the definition of $\beta$ is not necessary in our case since we are maximizing these variables in the objective function. We also note in passing that the big $M_j$ bounds can be set to $\max _{k=1,\ldots ,K} v_{kj}$ since product type j will never be paid more than the maximum utility assigned by the customers to that product.

The linearized formulation is:

$$\begin{aligned} FO(I,\sigma ):=\max&\sum _{k=1}^K \sum _{j=1}^m \sum _{\ell =1}^m \beta _{jk\ell } \nonumber \\ \text{ s.t. }&(7)-(10), (12)-(19) \end{aligned}$$

(27)

$$\begin{aligned}&\sum _{j=1}^m (w_{jk\ell } v_{kj}-q_{jk\ell }) \ge \sum _{j=1}^m (w_{jk\ell +1} v_{kj}-q_{jk\ell +1}), \quad \nonumber \\ {}&\quad k=1,\ldots ,K, \; \ell =1,\ldots ,m \end{aligned}$$

(28)

$$\begin{aligned}&\sum _{j=1}^m \eta _{jk\ell } + \sum _{j=1}^m \sum _{\ell ' = \ell +1}^m \alpha _{jk\ell '} \le 1, \quad \forall k=1,\ldots ,K, \; \ell =1,\ldots ,m \end{aligned}$$

(29)

$$\begin{aligned}&q_{jk\ell }\le p_j, \quad j,\ell =1,\ldots ,m,\; k=1,\ldots ,K \end{aligned}$$

(30)

$$\begin{aligned}&q_{jk\ell }\le w_{jk\ell } M_j, \quad j,\ell =1,\ldots ,m,\; k=1,\ldots ,K \end{aligned}$$

(31)

$$\begin{aligned}&p_j -M_j(1-w_{jk\ell }) \le q_{jk\ell } \quad j,\ell =1,\ldots ,m,\; k=1,\ldots ,K \end{aligned}$$

(32)

$$\begin{aligned}&\beta _{jk\ell } \le p_j \quad j,\ell =1,\ldots ,m,\; k=1,\ldots ,K \end{aligned}$$

(33)

$$\begin{aligned}&\beta _{jk\ell } \le M_j \alpha _{jk\ell } \quad j, \ell =1,\ldots ,m, \; k=1,\ldots ,K \end{aligned}$$

(34)

$$\begin{aligned}&\eta _{jk\ell }\le w_{jk\ell }, \quad j, \ell =1,\ldots ,m, \; k=1,\ldots ,K \end{aligned}$$

(35)

$$\begin{aligned}&\eta _{jk\ell }\le z_{kj}, \quad j, \ell =1,\ldots ,m, \; k=1,\ldots ,K \end{aligned}$$

(36)

$$\begin{aligned}&\eta _{jk\ell }\le \zeta _{jk}, \quad j,\ell =1,\ldots ,m, \; k=1,\ldots ,K \end{aligned}$$

(37)

$$\begin{aligned}&z_{kj}+w_{jk\ell }+\zeta _{jk} \le 2 + \eta _{jk\ell }, \quad j, \ell =1,\ldots ,m, \; k=1,\ldots ,K \nonumber \\ {}&p_j, A_{jk}, q_{jk\ell }, \beta _{jk\ell } \ge 0, \; j,\ell =1,\ldots ,m,\; k=1,\ldots ,K, \nonumber \\ {}&d_{rj}\in \{0,1\},\; r=1,\ldots ,N_j, \; j=1,\ldots ,m, \nonumber \\ {}&z_{kj}, w_{jk\ell } , \zeta _{jk} , \alpha _{jk\ell }, \eta _{jk\ell }\in \{0,1\}, \, j,\ell =1,\ldots ,m, \, k=1,\ldots ,K. \end{aligned}$$

(38)

Remark 3.1

Variables $\alpha$ can be relaxed to be continuous without modifying the validity of the formulation. So far in the experiments this relaxation gives worse computing times increasing by a factor of 3. Some constraints can be strengthened improving the bound given by the linear relaxation and reducing the size of the formulation. Constraint (19) can by replaced by:

$$\begin{aligned} \sum _{\ell =1}^m \alpha _{jk\ell } \le \zeta _{jk}, \qquad j=1,\ldots ,m,k=1\ldots ,K. \end{aligned}$$

(39)

The same argument applies to replace constraints (36) and (37) by the following ones:

$$\begin{aligned} \sum _{\ell =1}^m \eta _{jk\ell } \le z_{kj}, \qquad j=1,\ldots ,m,\; k=1\ldots ,K. \end{aligned}$$

(40)

$$\begin{aligned} \sum _{\ell =1}^m \eta _{jk\ell } \le \zeta _{jk}, \qquad j=1,\ldots ,m,\; k=1\ldots ,K. \end{aligned}$$

(41)

Analogously, constraints (30) and (33) can be reinforced by:

$$\begin{aligned} \sum _{\ell =1}^m q_{jk\ell } \le p_j,&j=1,\ldots ,m, \end{aligned}$$

(42)

$$\begin{aligned} \sum _{\ell =1}^m \beta _{jk\ell } \le p_j,&j=1,\ldots ,m, \; k=1,\ldots ,K \end{aligned}$$

(43)

Implementing all those reinforcements reduces the computing time in instances with $K=12, n=4, m=6$ from 120 seconds to 20 seconds. Instances of size $K=16, n=8, m=7$ take around 300 seconds.

Example 3.2

We illustrate the model with a situation with two customers and three products types ($n=2$ and $m=3$) and $K=7$ arrivals of customers. Consider the following arrival pattern (1, 2, 2, 2, 1, 1, 2) and an availability of products given by $I=(1,3,3)$.

The utility of customers for product types appears in the table below.

$(v _{ij})$	1	2	3
1	4	4.5	5.25
2	5	4	6

The optimal prices are $p_1=5; \; p_2=4.5, \; p_3=6$ with an objective function of 36.5. Observe that with these prices type 1 customers (those that correspond with arrivals 1, 5, 6) only buy product type 2, whereas type 2 customers (those arriving at stages 2, 3, 4, 7) buy products 1 and 3. Therefore, product 2 is the most preferred for type 1 customers and product 1 and 3 are, respectively, the most and second most preferred products for type 2 customers (for these prices).

The solution is descried by the $\alpha$ variables: $\alpha _{211}=\alpha _{121}=\alpha _{332}=\alpha _{342}=\alpha _{241}=\alpha _{261}=\alpha _{372}=1$. Remember that, for instance, $\alpha _{342}=1$ means that customer type 2 ($i=2$) that arrives at the fourth stage ($k=4$) buys product type 3 ($j=3$) being this type its second most preferred one ($\ell = 2$).

Finally, the inventory of products types at each stage of the process is described by the A variables:

$(A _{jk})$	0	1	2	3	4	5	6	7
1	1	1	0	0	0	0	0	0
2	3	2	2	2	2	1	0	0
3	3	3	3	2	1	1	1	0

3.1 Computational experiments

In order to assess the usefulness of our MILP formulation for solving the deterministic version of the problem we have conducted a series of computational experiments. We have generated utilities $v_{ij}$ as random integers in the interval [0, 100] and considered for the experiments subsets of $O(K^m)$ admissible prices. In addition, we have organized the data according to four different factors: number of customers (K), number of products (m), number of different of customers (n) and the type of inventory: “short” for those scenarios where there are possibly not enough items to cover the demand of all arriving customers and “enough” for those scenarios where it is very likely to cover the demand of arriving customers.

Table 1 Instances with short inventory

Table 2 Instances with enough inventory

We have generated five instances of each combination of the following levels of the above factors: K ranges in $\{20, 30, 50, 100\}$, m ranges in $\{2,4,6\}$, n ranges in $\{2,4,6\}$, and type of inventory in $\{$short, enough$\}$. The inventory generation is done with the following process. For the “short” scenarios the inventory of each product is randomly generated as the rounding integer that results from $1.2 *random *K/m$, and for “enough” scenarios as the rounding integer that results from $2 *random *K/m$ (random is a uniform number in [0, 1]).

We have run the model in Xpress solver in a laptop with an I7 cpu processor and 8 Gb RAM memory with a time limit of 3600 seconds per instance, and we report averages of different results obtained. We report in Tables 1 and 2 the results of our computational experiments. The results are presented by rows and each row is the average of five instances. In each row we include: LP-GAP which reports the percentage gap of the best solution found with respect to the linear relaxation; $GAP={UB-LB\over LB}\cdot 100$, where UB and LB are, respectively, the value of best solution found and the value of the best lower bound termination; the percentage gap at termination (after the cpu time is finished); “Solved” indicates the number of instances out of 5 solved to optimality; CPU is the average time required to solve the instance or 3600 in case optimality cannot be proven; Surplus-I is the percentage of units not sold in the optimal solution and Utility is defined as the average difference between the value given by the customers to each item type and the price they paid for them under the profit-maximizing prices.

From the tables we observe that we can solve instances up to 100 customers and different distributions of types and number of products types. For the hardest combination, with 6 customers types and 6 products, optimality of the solution found could not be proven for $K=50,100$ in some cases. We also observe that the type of inventory (“enough” or “short”) does not seem to influence the difficulty of the problems. Actually, in both cases we could solve to optimality the same number of instances 167 out of 180. It is also very interesting to remark that in many cases not all product units are sold due to the preferences of the custumers and the policy of prices. We observe that for the short scenario instances the expected value of $1.2*random$ is 0.6 so we expect to have shortage generally which may be increased because the effect of the order of arrivals and choice rules. In this case the leftovers are 8.58% of the product units. In the other case, the expected value of $2*random$ is 1 but, by the effect of the order of arrivals and the choice rules, there is a 33.98% of leftovers.

Remark 3.3

It is interesting to note what may seem to be counter-intuitive, that from Utility we conclude that when we are concerned with social welfare, it is more important to control the prices when there is enough inventory that when there is short inventory!

4 Monte Carlo model for price selection

We illustrate the usefulness of our MILP formulation to solve actual problems with random arrivals based on simulations of customers’ arrival scenarios. The simulation consists of the following.

• 1. Instances generation

  • (a) We fix the number of customer types, n and product types m.

  • (b) We randomly generate the utilities $v_{ij}$ and fix the probabilities $q_1,\dots ,q_n$ of the different customer types.

  • (c) We fix the number of arrivals K and numbers of available items per product type, $I_1,\dots ,I_m$.

• 2. Solution approach

  • (a) We simulate a number N of arrival scenarios of customers with the above probabilities. Then, we apply our MILP to each of the N scenarios to get the optimal objective function values and set of prices $p_1,\dots ,p_m$. This way, we obtain N sets of prices for the products according with the different arrival scenarios.

  • (b) The simulation is used to fix a priori each one of the set of prices obtained as an optimal solution for each scenario: we compute for each one of these price sets the average profit obtained when this set is applied to all our N scenarios, and output the one which maximizes this average.

In Table 3 we report the result of a simulation with $N=200$ scenarios with the following characteristics: there are $n=5$ customers types and $m=6$ products. Each instance simulates the arrival of $K=45$ customers with probabilities for each customer type given by $q_1=0.1$, $q_2=0.3$, $q_3=0.25$, $q_4=0.15$, $q_5=0.2$. We consider the two types of inventory levels, “short” and “enough”. The inventory level and the number of each type of item is the same for all the instances. In the case of short level the inventory is $7,\ 1, \ 14,\ 1,\ 6,\ 1$, respectively, for each product type; whereas in the case of enough inventory is $7,\ 9,\ 15,\ 8,\ 6, \ 7$. The utilities have been generated as random numbers in [0,10] and cpu time is measured in seconds. The layout of the tables is as follows. By rows we report the average and standard deviation of the different indicators. By columns we report two different blocks, one for short inventory and another one for enough inventory. Each one of them reports the cpu time (cpu), the best objective value (Obj) and number of items not sold (Surplus-U).

Table 3 Simulation for 200 scenarios with 45 arrivals per scenario

Next, we show results of a Monte Carlo evaluation of the pricing policies found by the MILP on this simulation. Let us denote by $P^*_i$ the optimal pricing policy (obtained solving the MILP model) of the scenario $S_i$ for $i\in \{1,\ldots ,N\}$.

Then, for each $\ell \in \{20,40,\ldots ,200\}$, we evaluate the value of the optimal pricing policy $P^*_i$, for $i=\ell -19,\ldots ,\ell$, on each scenario $S_j$, for $j=\ell -19,\ldots ,\ell$, and call it $R_{ij}^\ell$. Then, we compute the average value $Aver_i^\ell :=\frac{1}{20} \sum _{j=\ell -19}^\ell R_{ij}^\ell$ obtained on these 20 scenarios with policy $P^*_i$. Let $A_{i^*}^\ell :=\max _{\ell -19\le i \le \ell } Aver_i^\ell$ and $P_{i^*}^\ell$ the best policy associated with our approximation.

We report the results in Table 4, with the following layout. There, $\ell$ refers to the last scenario used for the corresponding row, $A_{i^*}^\ell$ reports the best average value evaluated over the scenarios of the corresponding block with 20 scenarios $S_{\ell -19},\ldots , S_\ell$ and Surplus-U is the average number of items unsold using that policy.

The results show that the Monte Carlo method is rather stable in that the best pricing policy ensures very similar average values regardless the scenarios where it is applied, and also that the number of items unsold stabilizes rather quickly. These results are consistently reproduced over different simulations of different arrival processes and inventory levels. Thus showing that this methodology can be used to set prices in these problems.

Table 4 Simulation for 200 scenarios with 45 arrivals per scenario and short inventory

Figure 4 depicts some of these results. Each one of the $N=200$ price vector found by the solver on the MILP is evaluated on all the arrival scenarios and the values averaged. Then, we choose the price vector that returns the maximum average value as our best Monte Carlo (MC) policy. The histograms show the evaluation of the best price vector found by the solver in each scenario (Actual) and the values obtained by the best MC price vector obtained on all the N scenarios, (Ev. Best Policy) for the two types of inventory levels (short and enough). Looking at the distribution, for instance in the short inventory case (see Fig. 4-left), if we consider $\ge 185$, as the good region of values, just choosing 20 independent scenarios the probability that the best one of them goes in the good region ($\ge 185$) is: $1-(1-26/100)^{20}=0.938$. The same computation in the enough inventory case (see Fig. 4-right), to be in the good region ($\ge 230$) is: $1-(1-36/200)^{20}=0.981$.

Fig. 4

Distribution of actual objective values and best MC price vector values on 200 scenarios

Actually, one does not need to sample that many scenarios (200) to get a good approximation of the best MC price vector. Specifically, we claim that sampling ${\hat{N}}\ll N$ scenarios and taking the best one of them (with respect to its average value over these ${\hat{N}}$ scenarios) is sufficient.

To illustrate this question, we use as benchmark $A^*$, the value of the best MC price vector. In the above simulation the average and median values of the MC price vector in the short inventory case are 163.68 and 166. Similarly, the average and median values of the MC price vector in the case of enough inventory are 232, 1 and 232, 6, respectively.

Next, we obtain a number C of candidates, each resulting from a small sample of ${\hat{N}}$ scenarios, as in Table 4 (for ${\hat{N}}=20 \ll N=200$ and $C=10$ candidates). We run each of these candidates over the whole set of 200 scenarios and obtain their averages $A^{1},\dots ,A^{C}$ (see Tables 5 and 6).

Table 5 Approximation of MC price vector with blocks of ${\hat{N}} = 20$ scenarios and short inventory

Table 6 Approximation of MC price vector with blocks of ${\hat{N}} = 20$ scenarios and enough inventory

Let $f^{\ell } = 100 A^{\ell }/A^*$ be the percentage of approximation obtained by each of these candidates. We consider the distribution of $f^\ell$, specifically its average and median values. The distribution of the $f^\ell$ approximates by more than $98\%$ those values of the MC policy in both cases. Once again, this confirms the conclusion that with a reduced number of random scenarios (${\hat{N}} = 20$) we can easily obtain very good results using the MC approach, based on the deterministic MILP solutions, to set prices for the stochastic situation.

5 Concluding remarks

This paper considers optimal pricing in a system with limited substitutable resources, such as certain goods or services. Prices, chosen from a continuum set, for the different resources have to be set and then customers with heterogeneous preferences show up sequentially. Customers select an item from the available resources, depending of their valuations of the resources and the prices. We prove that this problem is NP-hard to approximate within a factor $O(n^{1-\varepsilon })$ for any fixed $\varepsilon >0$. In spite of that, we have characterized the set of candidates for optimal solutions as the finite set of vertices of a subdivision of ${\mathbb {R}}^m$ with cardinality $m^{m-2}n^m2^m$. Moreover, we provide a mathematical program that chooses the best set of prices among the continuum set, based on the above reduction result. We report extensive computational results showing the usefulness of our exact approach to solve medium size problems with up to 100 customers and different assortments of products and customer types.

There are some possible extensions of our work as for instance considering that the inventory levels of the different products are decision variables and assuming that the arrival process is stochastic rather than deterministic. Both extensions are interesting but they are beyond the scope of this paper and may be the content of a follow-up paper.

Appendix

1.1 $v_{j1}>v_{i1}$ and $v_{j2}-v_{j1}<v_{i2}-v_{i1}$

The preference space for the case $v_{j1}>v_{i1}$ and $v_{j2}-v_{j1}<v_{i2}-v_{i1}$ is shown in Fig. 6. Case 2(b) is similar except for that the pivot of customer type j moves to the right so that region (21,21) disappears. Again, there are thirteen regions and the candidates for optimal pricing are those at the upper-right corners of the inner regions. Also here, there are two candidates that can be approached from two regions. Specifically, $(v_{i1},v_{i2})$ is the upper-right point of both regions (12,12) and (21,12), while $(v_{j1},v_{j2})$ is the upper-right corner of regions (0,12) and (0,21). In the former case both customer types are flexible and items will be sold as long as the inventory is not depleted. Approaching from region (12,12) is preferred if and only if the revenue from product 1 is higher, i.e., $v_{i1}>v_{i2}$. In the latter case, only j-customers make a purchase, and approaching from region (0,12) is the preferred option if and only if $v_{j1}>v_{j2}$.

Fig. 5

Customer preferences: $v_{j1}>v_{i1}$ and $v_{j2}-v_{j1}>v_{i2}-v_{i1}$

1.2 $v_{j1}>v_{i1}$ and $v_{j2}-v_{j1}>v_{i2}-v_{i1}$

The preference space for the case $v_{j1}>v_{i1}$ and $v_{j2}-v_{j1}>v_{i2}-v_{i1}$ is shown in Fig. 5. Case 3(b) is similar except for that the pivot of customer type j moves up so that region (12,12) disappears. Again there are thirteen regions and six candidate points for optimal pricing, two of them can be approached from two regions, and the choice is very similar to the one corresponding to Fig. 6.

Fig. 6

Customer preferences: $v_{j1}>v_{i1}$ and $v_{j2}-v_{j1}<v_{i2}-v_{i1}$