# Share-of-Surplus Product Line Optimisation with Price Levels

Authors: X. G. Luo; Z. C. Zhang; C. K. Kwong; J. F. Tang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Kraus and Yano (2003) established the share-of-surplus product line optimisation model and developed a heuristic procedure for this nonlinear mixed-integer optimisation model. In their model, price of a product is defined as a continuous decision variable. However, because product line optimisation is a planning process in the early stage of product development, pricing decisions usually are not very precise. In this research, a nonlinear integer programming share-of-surplus product line optimization model that allows the selection of candidate price levels for products is established. The model is further transformed into an equivalent linear mixed-integer optimisation model by applying linearisation techniques. Experimental results in different market scenarios show that the computation time of the transformed model is much less than that of the original model.


---

## Body

## 1. Introduction

Today, many firms adopt the strategy of product line optimisation to satisfy diverse customer requirements and gain competitive advantages. There are already many product line optimisation models proposed by scholars, for example, buyers’ welfare [1], seller’s welfare [2], share-of-choice [3], and share-of-surplus [4]. The comprehensive descriptions on the classifications and limitations of product line optimisation can be found in the survey papers by Kaul and Rao [5] and Belloni and Freund [6].Kraus and Yano [4] established the share-of-surplus product line optimisation model. This model is nonconcave, which makes it very difficult to obtain the global optimal solution. To solve the model, they developed a heuristic algorithm based on simulated annealing to obtain the near-optimal solutions.In the Kraus and Yano [4] model, product prices are defined as continuous decision variables. However, product line optimisation is a decision process in the early stages of product development; in addition, although product pricing is involved in this process, it tends to be strategic and relatively rough. Precise product pricing is determined only after a product is available for sale. For example, when planning a product line, a company may price a product approximately (e.g., $12,000 or $13,000) rather than precisely (e.g., $12,399). Therefore, taking product price as a continuous decision variable and obtaining the precise optimal product price may not be necessary for most firms; an alternative approach is to select prices from the candidate price levels. This approach has been widely applied in many research papers related to other types of product line optimisation [7–11].In this research, the Kraus and Yano [4] model is extended as a nonlinear integer programming model that allows the selection of candidate price levels for products. The model is further transformed into an equivalent linear mixed-integer optimisation model by applying linearisation techniques. Because the transformed model can be solved by many well-developed algorithms, such as the simplex-based branch-and-bound algorithm, it can be handled by existing commercial optimisation software packages, for example, IBM ILOG and LINGO. In the numeric experiment section, the computation times of the original model and transformed model are compared in various market scenarios, and the results show that the transformed model is very effective.The rest of this paper is organised as follows: in Section2, an extended model for the share-of-surplus product line optimisation is established and further transformed into an equivalent linear model. In Section 3, simulation cases of product line optimisation in three market scenarios are generated, and numeric experiments are performed to empirically verify the effectiveness of the proposed approach. Characteristics of the linearised model are discussed and conclusions are drawn in Section 4.


## 2. Optimisation Model and Linearisation

### 2.1. The Extended Share-of-Surplus Product Line Optimisation Model

The optimisation problem is described as follows. A firm is going to develop a product line. There areI market segments for the product, each of which contains customers with homogeneous preferences. The size (or the number of expected consumers) of the ith segment is denoted as Di. A reference set containing J candidate products has been generated for further selection. The utility (measured in dollars) of the customers in the ith market segment towards the jth product is denoted as Uij. The variable cost of the jth product is denoted as cj. There are Kj product price levels for the jth product, and the kth price level of the jth product is denoted by pjk. The purpose of the problem is to determine which products from the reference set should be included in the product line and which price level to choose for each product of the product line to maximise the company’s total profit.Assumptions of the optimisation problem include [4] the following. (1) Customers choose product by following the share-of-surplus choice rule. Kraus and Yano [4] explained the rule as follows. “The share-of-surplus choice rule defines the probability that a customer in a segment selects a certain product as the ratio of the segment’s surplus from this particular product to the segment’s total surplus across all products with positive surplus (for that customer or segment).” (2) competitive companies do not respond to the company’s moves (i.e., not a game). (3) The prices of the competitive products are given constants. (4) Price discrimination is not allowed. (5) Customers have complete information regarding the available products and their prices.Letyij be a binary decision variable such that yij=1 if all or a portion of customers in the ith segment choose the jth product and yij=0 otherwise, and let xjk be a binary decision variable such that xjk=1 if the kth price level is selected for the jth product and xjk=0 otherwise; the optimisation problem can be formulated as the following nonlinear integer programming model (Model A):
(1)Max⁡∑i=1I∑j=1JDi(∑k=1Kjxjkpjk-cj)mmmmlmmm×[(Uij-∑k=1Kjxjkpjk)yij∑j′=1J[(Uij′-∑k=1Kj′xj′kpj′k)yij′]](2)s.t.∑j′=1J[(Uij′-∑k=1Kj′xj′kpj′k)yij′]>0,mmmmmmmmmmmmnmmlli=1,2,…,I(3)mmmm(Uij-∑k=1Kjxjkpjk)yij≥0,i=1,2,…,I;mmmmlmmmmmmmmmmmlmmj=1,2,…,J(4)mmmm(Uij-∑k=1Kjxjkpjk)(1-yij)≤0,mmmnmmi=1,2,…,I;j=1,2,…,J(5)mmmm∑k=1Kjxjk=1,j=1,2,…,J(6)mmmmyij,xjk∈{0,1},i=1,2,…,I;mmmmj=1,2,…,J;k=1,2,…,Kj.The objective function of the model is to maximise the total profit (revenue minus cost) of the product line in all segments. The expression∑k=1Kjxjkpjk-cj in the objective function represents the marginal profit of the jth product. The expression (Uij-∑k=1Kjxjkpjk)yij/∑j′=1J[(Uij′-∑k=1Kjxj′kpj′k)yij′] represents the choice probability of customers in the ith market segment towards the jth product by following the share-of-surplus purchase choice rule. Constraint (2) can avoid the case that the denominator part is equal to zero. Constraint (3) ensures that a product’s utility surplus must be nonnegative if the product is selected by customers. Constraint (4) guarantees that a product’s utility surplus must be nonpositive if the product is not selected by customers. Constraint (5) ensures that only one price level is selected for a specific product. Constraint (6) confines the decision variables yij and xjk as binary ones.


### 2.2. Linearisation Approach

Consider the following linear mixed-integer programming model (Model B):(7)Max⁡∑i=1I∑j=1JDi[(Uij+cj)∑k=1Kjpjkz2ijkmmmmmmmmm-Uijcjz1ij-∑k=1Kj∑k′=1Kjpjkpjk′z3ijkk′](8)s.t.∑j′=1J(Uij′z1ij′-∑k=1Kj′pj′kz2ij′k)=1,mmmmmmmmmmmmimi=1,2,…,I(9)mmmmz1ij≤Myij,i=1,2,…,I;j=1,2,…,J(10)mmmmz1ij≤zideno+M(1-yij),i=1,2,…,I;mmmmmmmmmmmimmmmmmmj=1,2,…,J(11)mmmmz1ij≥zideno+M(yij-1),i=1,2,…,I;mmmnmmmmmmmmmimmmmmj=1,2,…,J(12)mmmmz2ijk≤Mz4ijk,i=1,2,…,I;j=1,2,…,J;mmmmmmmmLmimmmmmmmmk=1,2,…,Kj(13)mmmmz2ijk≤zideno+M(1-z4ijk),i=1,2,…,I;mmmmmLlmmmmmlj=1,2,…,J;k=1,2,…,Kj(14)mmmmz2ijk≥zideno+M(z4ijk-1),i=1,2,…,I;mmmmimmmmmnmj=1,2,…,J;k=1,2,…,Kj(15)mmmmz4ijk≤xjk,i=1,2,…,I;j=1,2,…,J;mmmmmmmmmmmmmmmLmmlk=1,2,…,Kj(16)mmmmz4ijk≤yij,i=1,2,…,I;j=1,2,…,J;mmmnmmmmmmmmnmnmmmmk=1,2,…,Kj(17)mmmmz4ijk≥1+M(xjk+yij-2),i=1,2,…,I;mmmmmmnmmimmj=1,2,…,J;k=1,2,…,Kj(18)mmmmz3ijkk′≥zideno+M(xjk+xjk′+yij-3),mmmmnnmimmmi=1,2,…,I;j=1,2,…,J;mmmmnnmmk=1,2,…,Kj;k′=1,2,…,Kj(19)mmmm∑j′=1J(Uij′yij′-∑k=1Kj′pj′kz4ij′k)>0,i=1,2,…,I(20)mmmmUijyij-∑k=1Kjpjkz4ijk≥0,i=1,2,…,I;mmmmmmmmlmmmmmmmmmj=1,2,…,J(21)mmmmUij-∑k=1Kjpjkxjk-Uijyij+∑k=1Kjpjkz4ijk≤0,mnmmnmimmmmi=1,2,…,I;j=1,2,…,J(22)mmmm∑k=1Kjxjk=1,j=1,2,…,J(23)mmmmyij,xjk∈{0,1},i=1,2,…,I;mmlmmj=1,2,…,J;k=1,2,…,Kj(24)mmmmz1ij,z2ijk,z3ijkk′,z4ijk,zideno≥0,mnnmmmi=1,2,…,I;j=1,2,…,J;mlnmk=1,2,…,Kj;k′=1,2,…,Kj,
where M is a large positive number.Theorem 1.
Model B has the same optimisation result as that of Model A.Proof of Theorem1 is given in Appendix.Compared with Model A, Model B is a mixed-linear model and thus can be solved by many well-developed algorithms integrating mature linear programming methods (e.g., simplex, barrier). Most of the commercial optimisation software packages, such as IBM ILOG and LINGO, provide modules for solving this type of problem.The cost of the transformation lies in the extra intermediate variables and constraints appended to the model. Model B hasIJK2+2IJK+IJ more continuous variables and IJK2+6IJK+3IJ+I more constraints than Model A. However, the results of the experiments show that the transformation is still quite efficient.


## 2.1. The Extended Share-of-Surplus Product Line Optimisation Model

The optimisation problem is described as follows. A firm is going to develop a product line. There areI market segments for the product, each of which contains customers with homogeneous preferences. The size (or the number of expected consumers) of the ith segment is denoted as Di. A reference set containing J candidate products has been generated for further selection. The utility (measured in dollars) of the customers in the ith market segment towards the jth product is denoted as Uij. The variable cost of the jth product is denoted as cj. There are Kj product price levels for the jth product, and the kth price level of the jth product is denoted by pjk. The purpose of the problem is to determine which products from the reference set should be included in the product line and which price level to choose for each product of the product line to maximise the company’s total profit.Assumptions of the optimisation problem include [4] the following. (1) Customers choose product by following the share-of-surplus choice rule. Kraus and Yano [4] explained the rule as follows. “The share-of-surplus choice rule defines the probability that a customer in a segment selects a certain product as the ratio of the segment’s surplus from this particular product to the segment’s total surplus across all products with positive surplus (for that customer or segment).” (2) competitive companies do not respond to the company’s moves (i.e., not a game). (3) The prices of the competitive products are given constants. (4) Price discrimination is not allowed. (5) Customers have complete information regarding the available products and their prices.Letyij be a binary decision variable such that yij=1 if all or a portion of customers in the ith segment choose the jth product and yij=0 otherwise, and let xjk be a binary decision variable such that xjk=1 if the kth price level is selected for the jth product and xjk=0 otherwise; the optimisation problem can be formulated as the following nonlinear integer programming model (Model A):
(1)Max⁡∑i=1I∑j=1JDi(∑k=1Kjxjkpjk-cj)mmmmlmmm×[(Uij-∑k=1Kjxjkpjk)yij∑j′=1J[(Uij′-∑k=1Kj′xj′kpj′k)yij′]](2)s.t.∑j′=1J[(Uij′-∑k=1Kj′xj′kpj′k)yij′]>0,mmmmmmmmmmmmnmmlli=1,2,…,I(3)mmmm(Uij-∑k=1Kjxjkpjk)yij≥0,i=1,2,…,I;mmmmlmmmmmmmmmmmlmmj=1,2,…,J(4)mmmm(Uij-∑k=1Kjxjkpjk)(1-yij)≤0,mmmnmmi=1,2,…,I;j=1,2,…,J(5)mmmm∑k=1Kjxjk=1,j=1,2,…,J(6)mmmmyij,xjk∈{0,1},i=1,2,…,I;mmmmj=1,2,…,J;k=1,2,…,Kj.The objective function of the model is to maximise the total profit (revenue minus cost) of the product line in all segments. The expression∑k=1Kjxjkpjk-cj in the objective function represents the marginal profit of the jth product. The expression (Uij-∑k=1Kjxjkpjk)yij/∑j′=1J[(Uij′-∑k=1Kjxj′kpj′k)yij′] represents the choice probability of customers in the ith market segment towards the jth product by following the share-of-surplus purchase choice rule. Constraint (2) can avoid the case that the denominator part is equal to zero. Constraint (3) ensures that a product’s utility surplus must be nonnegative if the product is selected by customers. Constraint (4) guarantees that a product’s utility surplus must be nonpositive if the product is not selected by customers. Constraint (5) ensures that only one price level is selected for a specific product. Constraint (6) confines the decision variables yij and xjk as binary ones.


## 2.2. Linearisation Approach

Consider the following linear mixed-integer programming model (Model B):(7)Max⁡∑i=1I∑j=1JDi[(Uij+cj)∑k=1Kjpjkz2ijkmmmmmmmmm-Uijcjz1ij-∑k=1Kj∑k′=1Kjpjkpjk′z3ijkk′](8)s.t.∑j′=1J(Uij′z1ij′-∑k=1Kj′pj′kz2ij′k)=1,mmmmmmmmmmmmimi=1,2,…,I(9)mmmmz1ij≤Myij,i=1,2,…,I;j=1,2,…,J(10)mmmmz1ij≤zideno+M(1-yij),i=1,2,…,I;mmmmmmmmmmmimmmmmmmj=1,2,…,J(11)mmmmz1ij≥zideno+M(yij-1),i=1,2,…,I;mmmnmmmmmmmmmimmmmmj=1,2,…,J(12)mmmmz2ijk≤Mz4ijk,i=1,2,…,I;j=1,2,…,J;mmmmmmmmLmimmmmmmmmk=1,2,…,Kj(13)mmmmz2ijk≤zideno+M(1-z4ijk),i=1,2,…,I;mmmmmLlmmmmmlj=1,2,…,J;k=1,2,…,Kj(14)mmmmz2ijk≥zideno+M(z4ijk-1),i=1,2,…,I;mmmmimmmmmnmj=1,2,…,J;k=1,2,…,Kj(15)mmmmz4ijk≤xjk,i=1,2,…,I;j=1,2,…,J;mmmmmmmmmmmmmmmLmmlk=1,2,…,Kj(16)mmmmz4ijk≤yij,i=1,2,…,I;j=1,2,…,J;mmmnmmmmmmmmnmnmmmmk=1,2,…,Kj(17)mmmmz4ijk≥1+M(xjk+yij-2),i=1,2,…,I;mmmmmmnmmimmj=1,2,…,J;k=1,2,…,Kj(18)mmmmz3ijkk′≥zideno+M(xjk+xjk′+yij-3),mmmmnnmimmmi=1,2,…,I;j=1,2,…,J;mmmmnnmmk=1,2,…,Kj;k′=1,2,…,Kj(19)mmmm∑j′=1J(Uij′yij′-∑k=1Kj′pj′kz4ij′k)>0,i=1,2,…,I(20)mmmmUijyij-∑k=1Kjpjkz4ijk≥0,i=1,2,…,I;mmmmmmmmlmmmmmmmmmj=1,2,…,J(21)mmmmUij-∑k=1Kjpjkxjk-Uijyij+∑k=1Kjpjkz4ijk≤0,mnmmnmimmmmi=1,2,…,I;j=1,2,…,J(22)mmmm∑k=1Kjxjk=1,j=1,2,…,J(23)mmmmyij,xjk∈{0,1},i=1,2,…,I;mmlmmj=1,2,…,J;k=1,2,…,Kj(24)mmmmz1ij,z2ijk,z3ijkk′,z4ijk,zideno≥0,mnnmmmi=1,2,…,I;j=1,2,…,J;mlnmk=1,2,…,Kj;k′=1,2,…,Kj,
where M is a large positive number.Theorem 1.
Model B has the same optimisation result as that of Model A.Proof of Theorem1 is given in Appendix.Compared with Model A, Model B is a mixed-linear model and thus can be solved by many well-developed algorithms integrating mature linear programming methods (e.g., simplex, barrier). Most of the commercial optimisation software packages, such as IBM ILOG and LINGO, provide modules for solving this type of problem.The cost of the transformation lies in the extra intermediate variables and constraints appended to the model. Model B hasIJK2+2IJK+IJ more continuous variables and IJK2+6IJK+3IJ+I more constraints than Model A. However, the results of the experiments show that the transformation is still quite efficient.


## 3. Numeric Experiments

All the experiments in this section were run on a personal computer (4 GB RAM, 3.30 GHz CPU, Windows 7). The IBM ILOG software package is version 12.4. The LINGO software package is version 11.0. All the generated cases, modelling files, and computational results can be found at:http://faculty.neu.edu.cn/ise/luoxinggang/paper16/data&code.htm.


### 3.1. Case Generation

Three types of product line design problems, that is, “random,” “rich-poor,” and “quality”, applied in Kraus and Yano [4], were generated for numeric experiments. The first type, “random,” corresponds to the practical scenario where consumers in different market segments have idiosyncratic preferences towards a product and there is no obvious relationship between the preferences. The second type, “rich-poor,” simulates the scenario where the number of rich consumers with higher utility is small while the number of poor consumers with lower utility is large. The third type, “quality,” is designed for representing the scenario where all consumers prefer products with high production cost and tend to have higher utilities for products with higher variable costs.For the first scenario “random,” as the name implies, all the parameters of the model, includingUij, cj, and Di, are generated randomly with a uniform distribution. However, because cj is the product variable cost, which is smaller than the utility of the product, it is generated according to the formula cj=U[0.05,0.2]*max⁡i=1IUij, which implies that the value of cost is a small percentage of maxi{Uij}.For the second scenario “rich-poor,” it shows the situation where there are a few “rich” consumers who prefer high-price products and a lot of “poor” consumers who prefer low-price products. The formulaUij=(bij+100)*i/I indicates that a market segment with small i represents “poor” consumers and a market with large i represents “rich” consumers. Correspondently, Di=[fij*(I-i)/I]+50 indicates that a market segment with small i has a large number of consumers and a market with large i has a small number of consumers.For the third scenario “quality,” it assumes that the cost is the most important influential factor for product quality and higher costs ensure better quality. According to the formulaUij=bij*cj and the range of bij (bij is generated randomly with the range of [1.0, 1.5]), it can be inferred that cj=(1/bij)*Uij and the range of 1/bij is [2/3, 1]. In other words, the ratio of cost to utility in this scenario is much higher than those of the previous two scenarios, and the cost has great influence on consumer’s utility towards a product.Table1 shows the settings of the model parameters for generating the cases.Table 1
Parameter settings for case generation.
Type
Parameter generation
Random
U
i
j
=
U
[
0,100
]
c
j
=
U
[
0.05,0.2
]
*
max
⁡
i
=
1
I
U
i
j
D
i
=
U
[
50,100
]
Rich-poor
U
i
j
=
(
b
i
j
+
100
)
*
i
/
I, bij=U[0,100]
c
j
=
U
[
0.05,0.2
]
*
max
⁡
i
=
1
I
U
i
j
D
i
=
[
f
i
j
*
(
I
-
i
)
/
I
]
+
50, fij=U[0,100]
Quality
U
i
j
=
b
i
j
*
c
j, bij=U[1.0,1.5]
c
j
=
U
[
5,20
]
D
i
=
U
[
50,100
]
Note:U[a,b] represents a stochastic variable following a uniform distribution on [a,b].


### 3.2. Experiment Results

Because all parameters of the cases are randomly generated, for a specific type of product line design problem at given size of market segment (I), number of candidate products (J), and numbers of price levels (K), 100 cases are randomly generated. The presented computational time for each type is the average of computation times of the 100 homogeneous cases. The number of price levels is set as a fixed value for all products in a product line in the experiments for simplicity. Experiments with different values of I, J, and K are performed to show the influence of problem size on average computation time. Table 2 shows the average computation time of Models A and B under the three different types of scenarios in three sets of different values of parameters I, J, and K. Some of the cells in the table are marked as “N/A”, indicating that the computation time is not available because the computation time of a case group (100 cases) is over 24 hours. In the following three experiments, IBM ILOG software package was applied to solve Models A and B.Table 2
Average computation time (second) of Models A and B.
Random
Rich-poor
Quality
Model A
Model B
Model A
Model B
Model A
Model B
I
=
5
,
J
=
5
,
K
=
5
4.51
2.96
5.09
2.87
9.50
3.23
I
=
6
,
J
=
5
,
K
=
5
5.19
3.19
5.91
3.09
13.20
3.26
I
=
7
,
J
=
5
,
K
=
5
6.68
3.21
7.39
3.28
15.34
3.42
I
=
8
,
J
=
5
,
K
=
5
7.87
3.64
8.60
3.66
17.62
3.47
I
=
9
,
J
=
5
,
K
=
5
8.60
3.73
9.65
3.79
19.84
3.78
I
=
10
,
J
=
5
,
K
=
5
10.31
3.92
14.05
4.34
24.45
3.81
I
=
5
,
J
=
5
,
K
=
5
4.51
2.96
5.09
2.87
9.50
3.23
I
=
5
,
J
=
6
,
K
=
5
33.78
4.25
49.93
7.26
63.47
3.74
I
=
5
,
J
=
7
,
K
=
5
173.91
9.72
282.09
16.22
340.62
7.37
I
=
5
,
J
=
8
,
K
=
5
838.31
19.06
N/A
50.32
N/A
14.97
I
=
5
,
J
=
9
,
K
=
5
N/A
77.33
N/A
215.81
N/A
35.42
I
=
5
,
J
=
10
,
K
=
5
N/A
291.77
N/A
951.90
N/A
132
I
=
5
,
J
=
5
,
K
=
5
4.51
2.96
5.09
2.87
9.50
3.23
I
=
5
,
J
=
5
,
K
=
6
13.86
3.38
17.37
3.83
28.52
4.43
I
=
5
,
J
=
5
,
K
=
7
35.14
5.35
43.29
7.10
66.62
5.62
I
=
5
,
J
=
5
,
K
=
8
81.09
6.97
76.66
9.39
129.07
7.13
I
=
5
,
J
=
5
,
K
=
9
146.08
13.86
125.8
11.64
226.33
9.73
I
=
5
,
J
=
5
,
K
=
10
244.59
20.61
189.3
16.69
354.34
14.85In the first experiment, Models A and B under the three scenarios were solved when the size of market segment (I) is set as different values. A comparison of Models A and B under the three scenarios is shown in Figure 1. The computation time of Model B is much less than that of Model A. From the trend line of data points, it can be inferred that the computation time is almost linearly related to the size of market segment, although the shapes of data points under the three scenarios are slightly different. A triangle marker in Figure 1 represents the difference of Model B’s computation time and Model A’s computation time. With the increase of the size of market segment, the value of the difference is also enhanced rapidly, indicating that Model B can save more computation time.Comparison of Models A and B whenI is changed.
(a)
Random
(b)
Rich-poor
(c)
QualityIn the second experiment, the average computation times of Models A and B under the three scenarios were compared when the number of products (J) is changed. Figure 2 shows that (1) the computation time of Model B is much less than that of Model A, (2) computation times of Models A and B are enhanced nonlinearly (probably exponentially) with the increase of the number of products, and (3) the number of products heavily influences the computational efficiency of Models A and B.Comparison of Models A and B whenJ is changed.
(a)
Random
(b)
Rich-poor
(c)
qualityIn the third experiment, Models A and B under the three scenarios are solved when the number of price levels(K) is increased. The results are depicted in Figure 3. The results also show that Model B has increasingly better computation efficiency over Model A as the number of price levels increases.Comparison of Models A and B whenK is changed.
(a)
Random
(b)
Rich-poor
(c)
QualityThe value ofM in Model B should be positive and very large in order to keep the constraints effective. In the above-mentioned three experiments, M is set as (min⁡i,j,k⁡Uij-pk)-1+1 because it can ensure that constraint (9)–(14), (17), and (18) work properly. For example, this setting of M of constraint (11) can ensure that the constraint always holds (i.e., no effect) when yij=0 since M is larger than zideno.The above-mentioned three experiments were also performed by LINGO. The comparison between computation time results of Models A and B has similar trends and conclusions as those by IBM ILOG, except that the computation time of LINGO is much longer than IBM ILOG. The computation results using LINGO can be found at the URL mentioned in the first paragraph of this section.


## 3.1. Case Generation

Three types of product line design problems, that is, “random,” “rich-poor,” and “quality”, applied in Kraus and Yano [4], were generated for numeric experiments. The first type, “random,” corresponds to the practical scenario where consumers in different market segments have idiosyncratic preferences towards a product and there is no obvious relationship between the preferences. The second type, “rich-poor,” simulates the scenario where the number of rich consumers with higher utility is small while the number of poor consumers with lower utility is large. The third type, “quality,” is designed for representing the scenario where all consumers prefer products with high production cost and tend to have higher utilities for products with higher variable costs.For the first scenario “random,” as the name implies, all the parameters of the model, includingUij, cj, and Di, are generated randomly with a uniform distribution. However, because cj is the product variable cost, which is smaller than the utility of the product, it is generated according to the formula cj=U[0.05,0.2]*max⁡i=1IUij, which implies that the value of cost is a small percentage of maxi{Uij}.For the second scenario “rich-poor,” it shows the situation where there are a few “rich” consumers who prefer high-price products and a lot of “poor” consumers who prefer low-price products. The formulaUij=(bij+100)*i/I indicates that a market segment with small i represents “poor” consumers and a market with large i represents “rich” consumers. Correspondently, Di=[fij*(I-i)/I]+50 indicates that a market segment with small i has a large number of consumers and a market with large i has a small number of consumers.For the third scenario “quality,” it assumes that the cost is the most important influential factor for product quality and higher costs ensure better quality. According to the formulaUij=bij*cj and the range of bij (bij is generated randomly with the range of [1.0, 1.5]), it can be inferred that cj=(1/bij)*Uij and the range of 1/bij is [2/3, 1]. In other words, the ratio of cost to utility in this scenario is much higher than those of the previous two scenarios, and the cost has great influence on consumer’s utility towards a product.Table1 shows the settings of the model parameters for generating the cases.Table 1
Parameter settings for case generation.
Type
Parameter generation
Random
U
i
j
=
U
[
0,100
]
c
j
=
U
[
0.05,0.2
]
*
max
⁡
i
=
1
I
U
i
j
D
i
=
U
[
50,100
]
Rich-poor
U
i
j
=
(
b
i
j
+
100
)
*
i
/
I, bij=U[0,100]
c
j
=
U
[
0.05,0.2
]
*
max
⁡
i
=
1
I
U
i
j
D
i
=
[
f
i
j
*
(
I
-
i
)
/
I
]
+
50, fij=U[0,100]
Quality
U
i
j
=
b
i
j
*
c
j, bij=U[1.0,1.5]
c
j
=
U
[
5,20
]
D
i
=
U
[
50,100
]
Note:U[a,b] represents a stochastic variable following a uniform distribution on [a,b].


## 3.2. Experiment Results

Because all parameters of the cases are randomly generated, for a specific type of product line design problem at given size of market segment (I), number of candidate products (J), and numbers of price levels (K), 100 cases are randomly generated. The presented computational time for each type is the average of computation times of the 100 homogeneous cases. The number of price levels is set as a fixed value for all products in a product line in the experiments for simplicity. Experiments with different values of I, J, and K are performed to show the influence of problem size on average computation time. Table 2 shows the average computation time of Models A and B under the three different types of scenarios in three sets of different values of parameters I, J, and K. Some of the cells in the table are marked as “N/A”, indicating that the computation time is not available because the computation time of a case group (100 cases) is over 24 hours. In the following three experiments, IBM ILOG software package was applied to solve Models A and B.Table 2
Average computation time (second) of Models A and B.
Random
Rich-poor
Quality
Model A
Model B
Model A
Model B
Model A
Model B
I
=
5
,
J
=
5
,
K
=
5
4.51
2.96
5.09
2.87
9.50
3.23
I
=
6
,
J
=
5
,
K
=
5
5.19
3.19
5.91
3.09
13.20
3.26
I
=
7
,
J
=
5
,
K
=
5
6.68
3.21
7.39
3.28
15.34
3.42
I
=
8
,
J
=
5
,
K
=
5
7.87
3.64
8.60
3.66
17.62
3.47
I
=
9
,
J
=
5
,
K
=
5
8.60
3.73
9.65
3.79
19.84
3.78
I
=
10
,
J
=
5
,
K
=
5
10.31
3.92
14.05
4.34
24.45
3.81
I
=
5
,
J
=
5
,
K
=
5
4.51
2.96
5.09
2.87
9.50
3.23
I
=
5
,
J
=
6
,
K
=
5
33.78
4.25
49.93
7.26
63.47
3.74
I
=
5
,
J
=
7
,
K
=
5
173.91
9.72
282.09
16.22
340.62
7.37
I
=
5
,
J
=
8
,
K
=
5
838.31
19.06
N/A
50.32
N/A
14.97
I
=
5
,
J
=
9
,
K
=
5
N/A
77.33
N/A
215.81
N/A
35.42
I
=
5
,
J
=
10
,
K
=
5
N/A
291.77
N/A
951.90
N/A
132
I
=
5
,
J
=
5
,
K
=
5
4.51
2.96
5.09
2.87
9.50
3.23
I
=
5
,
J
=
5
,
K
=
6
13.86
3.38
17.37
3.83
28.52
4.43
I
=
5
,
J
=
5
,
K
=
7
35.14
5.35
43.29
7.10
66.62
5.62
I
=
5
,
J
=
5
,
K
=
8
81.09
6.97
76.66
9.39
129.07
7.13
I
=
5
,
J
=
5
,
K
=
9
146.08
13.86
125.8
11.64
226.33
9.73
I
=
5
,
J
=
5
,
K
=
10
244.59
20.61
189.3
16.69
354.34
14.85In the first experiment, Models A and B under the three scenarios were solved when the size of market segment (I) is set as different values. A comparison of Models A and B under the three scenarios is shown in Figure 1. The computation time of Model B is much less than that of Model A. From the trend line of data points, it can be inferred that the computation time is almost linearly related to the size of market segment, although the shapes of data points under the three scenarios are slightly different. A triangle marker in Figure 1 represents the difference of Model B’s computation time and Model A’s computation time. With the increase of the size of market segment, the value of the difference is also enhanced rapidly, indicating that Model B can save more computation time.Comparison of Models A and B whenI is changed.
(a)
Random
(b)
Rich-poor
(c)
QualityIn the second experiment, the average computation times of Models A and B under the three scenarios were compared when the number of products (J) is changed. Figure 2 shows that (1) the computation time of Model B is much less than that of Model A, (2) computation times of Models A and B are enhanced nonlinearly (probably exponentially) with the increase of the number of products, and (3) the number of products heavily influences the computational efficiency of Models A and B.Comparison of Models A and B whenJ is changed.
(a)
Random
(b)
Rich-poor
(c)
qualityIn the third experiment, Models A and B under the three scenarios are solved when the number of price levels(K) is increased. The results are depicted in Figure 3. The results also show that Model B has increasingly better computation efficiency over Model A as the number of price levels increases.Comparison of Models A and B whenK is changed.
(a)
Random
(b)
Rich-poor
(c)
QualityThe value ofM in Model B should be positive and very large in order to keep the constraints effective. In the above-mentioned three experiments, M is set as (min⁡i,j,k⁡Uij-pk)-1+1 because it can ensure that constraint (9)–(14), (17), and (18) work properly. For example, this setting of M of constraint (11) can ensure that the constraint always holds (i.e., no effect) when yij=0 since M is larger than zideno.The above-mentioned three experiments were also performed by LINGO. The comparison between computation time results of Models A and B has similar trends and conclusions as those by IBM ILOG, except that the computation time of LINGO is much longer than IBM ILOG. The computation results using LINGO can be found at the URL mentioned in the first paragraph of this section.


## 4. Discussion and Conclusions

In this study, the share-of-surplus product line optimisation model by Kraus and Yano [4] is extended to allow the selection of candidate price levels for products, which is more realistic and has been used in other product line models. The proposed model is further transformed into an equivalent linear mixed-integer programming model.The transformed linear model adds a number of extra auxiliary continuous variables and linear constraints to the original model. However, the numeric experiments show that the computation time of the transformed model is much less than that of the original one in different market scenarios, and the efficiency of the transformed model increases with the scale of the problem.It must be noted that for large-scale problems, the computation time of the transformed linear model is still too long due to the integer variables, and a metaheuristic algorithm such as evolutionary computation is probably a better choice. However, exact approaches can achieve the global optimal solutions and thus are attractive to small-scale practical problems (e.g., service products, some products of SME). In addition, global optimal solutions can also be used to evaluate the performance of heuristic or metaheuristic algorithms because they can provide a base line for comparison.



---

*Source: 389749-2014-04-01.xml*