Internet shopping with price sensitive discounts

Let us consider a subproblem of problem IS, in which \(p_{ij}=p_j, j=1,\ldots ,n, i=1,\ldots ,m\). We denote it as IS-Same-Prices. This problem has the following useful property.

Theorem 2 is a basis of the following solution approach for problem IS-Same-Prices. Construct all shop sequences \((i_1,\ldots ,i_m)\) and corresponding solutions \((S_{i_1},\ldots ,S_{i_k}), k\le m\), such that \(S_{i_1}=N_{i_1}, S_{i_r}=N_{i_r}\backslash (\cup _{l=1}^{r-1} S_{i_l}), r=1,\ldots ,k\), and \(N=\cup _{l=1}^k S_{i_l}\). The number of these sequences does not exceed \(m!\). In \(O(n)\) time calculate solution value (final total price) for every sequence and choose solution corresponding to the best sequence as an optimal solution.

The time complexity of this approach is \(O(nm!)\), which is better than the previous \(O(nm^n)\) time solution approach. This approach is linear in \(n\), and it can be acceptable for real-life computations if there are thousands of products and tens of shops. It can be used as a heuristic for a more general case of problem IS, in which prices of the same product are slightly different in different shops. It can also be adapted to solve the following realistic special case of problem IS-Same-Prices in a polynomial time.

Problem IS-Same-Prices-Subsets: \(p_{ij}=p_j, j=1,\ldots ,n, i=1,\ldots ,m\), and \(N\) is partitioned into subsets \(N^{(0)}, N^{(1)}\) and \(N^{(2)}\) such that all products of the set \(N^{(0)}\) are present in each shop, each product of the set \(N^{(1)}\) is present in one shop, and \(|N^{(2)}|\le c\), where \(c\) is a given constant.

Theorem 3 and an observation that the shop to buy a product of the set \(N^{(1)}\) is determined uniquely justify the following solution algorithm for problem IS-Same-Prices-Subsets. Consider candidate shops \(l=1,\ldots ,m\) to buy all products of the set \(N^{(0)}\) in one shop. For each \(l\), perform the following computations. Assign products of the set \(N^{(0)}\) to shop \(l\). Assign each product \(j\in N^{(1)}\) to its unique eligible shop. Let \(N^{(2)}=\{1,\ldots ,c\}\). Enumerate all feasible assignments of products \(1,\ldots ,c\) to the shops, which is equivalent to enumerating shop sequences \((i_1,i_2,\ldots ,i_c)\) such that product \(j\) is assigned to shop \(i_j\in M_j, |M_j|\le m, j=1,\ldots ,c\). The number of these sequences does not exceed \(m^c\). For each \(l\) and the above mentioned shop sequence \((i_1,i_2,\ldots ,i_c)\), calculate the value of the corresponding solution. Select a solution with the minimum value as an optimal solution. The run time of this algorithm is \(O(nm^{c+1})\).

In this subsection we consider a subproblem of problem IS, in which \(f_i(T)=T, i=1,\ldots ,m\). We denote it as IS-No-Discounts. This problem is equivalent to the well known Facility Location Problem (FLP). Main characteristics of the FLP are a space, a metric, given customer locations and given or not positions for facility locations. A traditional FLP is to open a number of facilities in arbitrary positions of the space (continuous problem) or in a subset of the given positions (discrete problem) and to assign customers to the opened facilities such that the sum of opening costs and costs related to the distances between customer locations and their corresponding facility locations is minimized. The equivalence of the traditional discrete FLP and problem IS-No-Discounts is easy to see if customers are treated as products, positions for facility locations as shops, opening costs as delivery prices, and cost related to the distance between position \(i\) and customer \(j\) as the price \(p_{ij}\) of product \(j\) in shop \(i\). Note, however, that the general problem IS with price sensitive discounts cannot be treated as a traditional discrete FLP because there is no evident motivation for a discount on the cumulative cost in the sense of distances.

Discussions of FLPs can be found in Eiselt and Sandblom (2004), Iyigun and Ben-Israel (2010), Krarup et al. (2002), Melo et al. (2009), Revelle et al. (2008), Stratila (2009). The traditional discrete FLP is NP-hard in the strong sense, so is the problem IS-No-Discounts. Solution approaches for discrete FLPs include Integer Programming formulations, Lagrangian relaxations, Linear Programming relaxations, Genetic Algorithms, graph-theoretical approaches, and Tabu Search, whose descriptions can by found in Revelle et al. (2008) and Stratila (2009). All these approaches can be used to solve problem IS-No-Discounts.

Stratila (2009) studied a concave cost facility location problem, whose mathematical program can be written aswhere \(\phi _i\) are concave nondecreasing functions. It can be noticed that this problem and problem IS are not sub-cases of one another, while the traditional discrete FLP is a special case of any of these problems.

Let us consider a subproblem of problem IS, in which \(N_i=N\) and \(p_{ij}=p_j, j=1,\ldots ,n, i=1,\ldots ,m\). We denote it as IS-Same-Products-And-Prices. In this subproblem, total standard price of all products does not depend on the solution. Denote it by \(P=\sum _{j=1}^n p_j\).

Problem IS-Same-Products-And-Prices can be solved as follows. Determine shop \(i^0=\arg \min \{f_i(d_i+P)\mid i=1,\ldots ,m\}\). Construct optimal solution, in which all products are selected in shop \(i^0\). The time complexity of this approach is \(O(n+m)\).

In this subsection we assume that \(N_i=N\), discounting functions are concave piecewise linear: \(f_i(T)=a^{(r)}_i+b^{(r)}_iT\) for \(T\in (T_{r-1},T_r], r\in \{1,\ldots ,k\}, 0=T_0<T_1<T_2<\cdots <T_k\), and standard prices in different shops are proportional: \(p_{ij}=h_ip_j\). Here \(a^{(r)}_i\ge 0, b^{(r)}_i>0\) and \(h_i>0, r=1,\ldots ,k, i=1,\ldots ,m\). This structure of standard prices often happens in reality, when shops with well established reputation apply extra charges to the product price comparing to that in shops with ordinary reputation. We denote corresponding subproblem as IS-Same-Products-Linear-Charges. For this subproblem, final total price of the products selected in shop \(i\) can be calculated as follows:This formula shows that problem IS-Same-Products-Linear-Charges reduces to the problem IS-Same-Products-And-Prices with convex piecewise linear discounting functions \(g_i(T)=a^{(r)}_i+b^{(r)}_ih_iT\) for \(T\in (\frac{T_{r-1}}{h_i},\frac{T_r}{h_i}], r\in \{1,\ldots ,k\}\), and delivery prices \(d_i/h_i\). Therefore, it can be solved in \(O(n+m)\) time by the approach in Sect. 3.1.

Since Location Problems are well known for dozens of years we analyze literature and provide a descripiton on some papers that could be relevant to the IS topic. First of all, it is worth noticing that a publication by Soland (1974) describes Facility Location Problem with concave costs of the transport of goods. However, the two problems differ significantly. Main formulation of the Soland’s problem is as follows: There is a company which wants to sell a number of units \(r_j\) of a given (one) product. Assumption is that the period is one year. Clients are the cities \(j, j=1,\ldots ,n\). All production in the ammount of \(r\) units is distributed from the plants \(i, i=1,\ldots ,m\). \(x_{ij}\) is the annual amount to be shipped from plant \(i\) to the city \(j\), and \(y_i=\sum _{j=1}^n x_{ij}\) is the annual production in plant \(i\). Let \(a_i, a_i=1,\ldots ,m\) be the maximum capacity of plant \(i\) and \(t_{ij}(x_{ij})\) be the total discounted cost over the T-year period of shipping \(x_ij\). Mathematical programming formulation can be written asNonetheless, even if this problem contains discounting function, it can be noticed that this problem and problem IS are not sub-cases of one another.

Another interesting, somehow similar to IS, is Facility location problem with staircase costs. As an example we can define a staircase cost function as a finite piecewise linear increasing function with a finite set of discontinuities, each corresponding to a certain size of a facility. A formulation of the problem (see Holmberg (1994) for the details) is a linear MIP-problem formulation with \(mn+mq\) continuous variables and \(mq\) integer variables. In the paper by Holmberg (1994) authors investigated solution methods based on convex piecewise linearization and Benders decomposition. Using convex piecewise linearization, only the integer variables that are needed to improve the approximation are introduced, and computational tests show that in average only a few are needed. Authors show that Benders decomposition can be used to solve the resulting problem. Moreover, Holmberg and Ling (1997) developed and compared heuristic solution methods for the capacitated facility location problem with staircase shaped production cost functions, a linear mixed integer programming problem with a large proportion of integer variables. In the same paper authors (Holmberg and Ling) proposed a Lagrangean heuristic, including Lagrangean relaxation and subgradient optimization as a base for an efficient primal heuristic. They showed also how to use convex piecewise linearization of the staircase shaped cost functions to get good initial upper and lower bounds as well as initial dual solutions. Based on the solution of the Lagrangean relaxation, a transportation problem which yields primal feasible solutions, was constructed.

However, it can be seen that staircase costs are somewhat different than pricewise sensitive discounts described within the problem IS, so in our case different approaches are needed.