On efficient solutions of 0-1 multi-objective linear programming problems

Abstract

An error in an algorithm, in Jahanshahloo et al. (Asia Pacific Journal of Operational Research 21(1):127–139, 2004), to generate efficient solutions to a 0-1 multi objective linear programming problems is detected and a modified algorithm is suggested. Further, an erroneous conclusion in the proof of the theorem, which states that at least one optimal solution among the optimal solutions of an individual 0-1 linear program is an efficient solution, is also corrected.

1 Introduction

A 0-1 multi-objective linear programming problem(0-1 MOLP) is defined as:

$$ \text{Max}\{C_{1}W, C_{2}W, {\ldots} , C_{r}W\}, \quad {\text{ subject to }}AW \leq b,\quad W\in \{0,1\}^{n} $$

(1.1)

where C _i = (c _i1, c _i2, … , c _{i n} ), i = 1, 2, … , r, A is m×n matrix, W = (w ₁, w ₂, … , w _n ), a column vector and b is a m component vector. Let C be a matrix whose rows are C _i . Let X be the set all feasible solutions of the 0-1 MOLP i.e.,

$$X=\{ W| AW \leq b, w_{j} \in \{0,1\}, j=1,2,{\ldots} , n\} $$

Consider the example given in [1] and in [2]:

$$ \begin{array}{rl} {\text{Max}} & 3w_{1}+6w_{2}+5w_{3}-2w_{4}+3w_{5}\\ {\text{Max}} & 6 w_{1}+7 w_{2}+4 w_{3}+3 w_{4}-8 w_{5}\\ {\text{Max}} & 5 w_{1}-3 w_{2}+8 w_{3}-4 w_{4}+3 w_{5}\\ {\text{Subject to}} & -2w_{1}+3w_{2}+8w_{3}-w_{4}+5w_{5} \leq 13\\ & 6w_{1}+2w_{2}+4w_{3}+4w_{4}-3w_{5} \leq 15\\ & 4w_{1}-2w_{2}+6w_{3}-2w_{4}+\ w_{5} \leq 11\\ & w_{1}, w_{2}, w_{3}, w_{4}, w_{5} \in \{0,1\} \end{array} $$

(1.2)

Simple calculations show that the example has one more efficient solution $W^{*}_{5}=(1,0,1,1,1)$. The efficient solutions calculated using the algorithm in [1] are $W^{*}_{1}=(1,1,1,0,0)$, $W^{*}_{2}=(1,0,1,0,1)$, $W^{*}_{3}=(1,1,1,1,1)$, $W^{*}_{4}=(1,0,1,0,0)$. In fact, the optimal solution of the first objective function is (1, 1, 1, 1, 1) with optimum value 15 but in [1] the optimal solution is taken as (1, 1, 1, 0, 0).

Definition 1.1

W ^∗ ∈ X is an efficient solution of the problem (1.1) if and only if there does not exist a point point W ∈ X, such that

$$(C_{1}W,C_{2}W, {\ldots} , C_{r}W) \geq (C_{1}W^{*},C_{2}W^{*}, {\ldots} , C_{r}W^{*}) $$

and the inequality holds strictly for at least one index i.e., for any point W ∈ X, either

$$ (C_{1}W,C_{2}W, {\ldots} , C_{r}W) \leq (C_{1}W^{*},C_{2}W^{*}, {\ldots} , C_{r}W^{*}) $$

(1.3)

or there are indices i ₁, i ₂(i ₁ ≠ i ₂),

$$ C_{i_{1}}W > C_{i_{1}}W^{*} {\text{ and }} C_{i_{2}}W < C_{i_{2}}W^{*} $$

(1.4)

Remark 1.2

In case (1.4), we say that W and W ^∗ are not comparable with respect to C and in case (1.3), we say W ^∗ dominates W with respect to C.

If W ^∗ is an efficient solution and for a W ∈ X, C W = C W ^∗ then we shall consider W also an efficient solution.

Denote by P _i the 0-1 linear program with i ^th objective function (i ^th row of C) subject to X with the set of optimal solutions $\mathcal {O}_{i}$. Let $\mathcal {O}_{i_{1} i_{2} {\ldots } i_{t}}$ (i ₁ < i ₂ < ⋯ < i _t ) be the set of all common optimal feasible solutions of P$_{i_{1}}$, P$_{i_{2}}$, …, P$_{i_{t}}$. Clearly,

$$\mathcal{O}_{i_{1} i_{2} {\ldots} i_{t}} = \bigcap\limits_{k=i_{1}}^{i_{t}}\mathcal{O}_{k} $$

There are 2^r−1 such sets. The following lemma is immediate.

Lemma 1.3

If $\mathcal {O}_{12{\cdots } r}$ is non-empty then $\mathcal {O}_{12{\cdots } r}$ is the set of all efficient solutions.

Remark 1.4

In view of above lemma, henceforth, we shall assume that $\mathcal {O}_{12{\cdots } r} = \phi$.

Remark 1.5

In the example (1.2), the vector $W_{5}^{*} = (1,0,1,1,1)$ gives $CW_{5}^{*} = (9,5,12)$ which is not comparable with $CW_{1}^{*} = (14,17,10)$, $CW_{2}^{*} = (11,2,16)$, $CW_{3}^{*} = (15,12,9)$ and $CW_{4}^{*} = (8,10,13)$. Hence it is also an efficient solution. Hence the algorithm in [1] does not find all efficient solutions. The proposed algorithm also finds this efficient solution.

2 Some basic results

The statement of the theorem 2.1 in [1]:

Theorem 2.1

If $\mathcal {O}_{l}= \left \{W_{1l}^{*},W_{2l}^{*}, {\ldots } , W_{fl}^{*} \right \}$ be the set of optimal solutions of P _l then at least one vector in $\mathcal {O}_{l}$ is an efficient solution of the problem (1.1).

First, we prove the case $\left | \mathcal {O}_{l}\right | =1$ which is also proved in [1].

Lemma 2.2

Suppose $\mathcal {O}_{12{\cdots } r} = \phi$ . If $\left | \mathcal {O}_{i}\right | =1$ then the vector in $\mathcal {O}_{i}$ is an efficient solution of the problem (1.1).

Proof

Let $\mathcal {O}_{i} =\{ W^{*}\}$. Hence for any W ∈ X − {W ^∗},

$$C_{i}W < C_{i} W^{*} $$

and for k ≠ i,

$$C_{k}W \leq C_{k} W^{*} \text{ or } C_{k}W > C_{k} W^{*} $$

If C _k W ≤ C _k W ^∗ for all k ≠ i, then W ^∗ dominates W with respect to C. If there is k(≠ i), such that C _k W > C _k W ^∗ then W ^∗ and W are not comparable with respect to C. In both cases, W ^∗ is an efficient solution of the problem (1.1). □

While proving the theorem we must also consider a case whether $\mathcal {O}_{l}\cap \mathcal {O}_{i} = \phi$ for each $\mathcal {O}_{i},\left | \mathcal {O}_{i}\right | =1$, other wise elements in these intersections are efficient solutions by above lemma. The following statement is also proved in the proof of the theorem 2.1 in [1].

Lemma 2.3

No vector in $X-\mathcal {O}_{l}$ dominates vectors in $\mathcal {O}_{l}$.

Proof

Let $W^{0} \in X-\mathcal {O}_{l}$ and $W_{ql}^{*}$ be such that

$$C_{i}W^{0} \geq C_{i}W_{ql}^{*}, i=1,2, {\ldots} , r {\text{ and there exists }} k, C_{k}W^{0} > C_{k}W_{ql}^{*}. $$

Clearly k ≠ l as $W_{ql}^{*}$ is optimal. At i = l, we must have $C_{l}W^{0} = C_{l}W_{ql}^{*}$ i.e., $W^{0} \in \mathcal {O}_{l}$ which is not true. □

Corollary 2.4

If the vector in $X-\mathcal {O}_{l}$ is not dominated by vectors in $\mathcal {O}_{l}$ then it is non-comparable with vectors in $\mathcal {O}_{l}$.

Proof

At i = l, we must have $C_{l}W^{0} < C_{l}W_{ql}^{*}$. Since the vector is not dominated by vectors in $\mathcal {O}_{l}$ there is k ≠ l such that $C_{k}W^{0} > C_{k}W_{ql}^{*}$. i.e., W ⁰ and $W_{ql}^{*}$ are not comparable. □

Remark 2.5

For the case $\left | \mathcal {O}_{l}\right | > 1$ the proof in [1] uses the relation ≤ on vectors which is a partial order and not a linear. The conclusion drawn: Y _{k l} ≤ Y _{k l} and Y _{k l} ≠ Y _{k l} is because of the assumption that the relation ≤ is linear. It may happen that for some vectors $W_{i_{1}l}^{*}, W_{i_{2}l}^{*}, {\ldots } , W_{i_{t}l}^{*}$ in $\mathcal {O}_{l}$,

$$CW_{i_{1}l}^{*} = CW_{i_{2}l}^{*} = {\cdots} = CW_{i_{t}l}^{*} $$

Hence the correction in the proof is required.

Proof

[Theorem (2.1)] when $\left | \mathcal {O}_{l}\right | > 1$:

Define a mapping $C:\mathcal {O}_{l} \longrightarrow {I\!\!R}^{r}$ such that W ↦ C W. Consider, the range of the map

$$\mathcal{R}(C) = \left\{ CW | W \in \mathcal{O}_{l} \right\}. $$

Suppose

$$\mathcal{R} (C) = \left\{ K_{1}, K_{2}, {\ldots} , K_{z}\right\} $$

We have K _i ≠ K _j for all i ≠ j. Now, we define a directed graph on $\mathcal {R} (C)$ using the partial ordering ≤ on the vectors. We say there is a directed edge between K _i to K _j if and only if K _i ≤ K _j . Since all K _i ’s are distinct there are no directed cycles. (A directed cycle means a few K _i ’s are equal.)

Therefore, a component of the graph of $\mathcal {R} (C)$ is a directed tree. Hence there is at least one vertex, say K _t with out-degree zero. Clearly, in view of the lemma (2.3), inverse image of this K _t contains efficient solutions as image of no vector in $\mathcal {O}_{l}$ dominates K _t . □

Remark 2.6

Note that above proof also works for $\left | \mathcal {O}_{i}\right | = 1$. Further we can also define a directed graph(Hasse diagram [3]) on $\mathcal {O}_{l}$ using the partial ordering ≤ on the vectors.

Remark 2.7

The observation in above corollary 2.4 is used in the proposed algorithm to find efficient solutions. Consider P₀ as the 0-1 LP:

$$ {\text{ Max} } \sum\limits_{i=1}^{r}C_{i}W, \quad {\text{ subject to }}AW \leq b,\quad W\in \{0,1\}^{n} $$

(2.1)

It is proved in [1] (Theorem 2.3) that each optimal solution of the problem (2.1) is an efficient solution for the problem (1.1). Thus, in view of corollary 2.4, in order to find efficient solutions other than optimal solutions of P ₀ and the unique optimal solutions of P _i , we must find non-comparable vectors with respect to these vectors.

Let $\widetilde {G_{0}}$ be the set of optimal feasible solutions of the problem (2.1). Let optimal value of P₀ be z ^∗. Put

$$ G_{0} =\widetilde{G_{0}} \cup \left(\cup_{\alpha=1}^{t} \mathcal{O}_{i_{\alpha}}\right)\text{ where } \left| \mathcal{O}_{i_{\alpha}}\right| =1. $$

(2.2)

In [1], in the beginning of the algorithm, in order to find other efficient solutions of the problem (1.1), not in G ₀, it has been observed that following inequalities

$$C_{i}W \leq C_{i}W_{j}^{*} \quad i=1,2, {\ldots} , r $$

are not satisfied simultaneously. The conclusion deducted is that for each $W_{j}^{*} \in G_{0}$ there is k such that

$$C_{k}W > C_{k}W_{j}^{*} $$

But, if $C_{i}W = C_{i}W_{j}^{*}$ for all i ≠ k, we get

$$C_{i}W \geq C_{i}W_{j}^{*} \quad i=1,2, {\ldots} , r $$

This is not expected as $W_{j}^{*}$ is an efficient solution. Therefore, we must ensure that for each $W_{j}^{*} \in G_{0}$ there are t, i, t ≠ i such that

$$C_{i}W > C_{i}W_{j}^{*} \text{ and } C_{t}W < C_{t}W_{j}^{*} $$

i.e., W would be non comparable with each vector in G ₀.

3 The algorithm

We shall find efficient solutions of the problem (1.1) in X − G ₀ when $\mathcal {O}_{12{\cdots } r} = \phi$. Suppose

$$G_{0} = \{ W_{1}^{*}, W_{2}^{*}, {\ldots} ,W_{p}^{*}\}. $$

Obviously for any W ∈ X − G ₀

$$\sum\limits_{i=1}^{r}C_{i}W < z^{*} $$

As a first step we add a constraint in the problem (2.1),

$$ \sum\limits_{i=1}^{r}C_{i}W < z^{*}-\epsilon $$

(3.1)

where 𝜖 ∈ (0, 1). We denote this new 0-1 LP by P₀(𝜖). We take 𝜖 such that optimal feasible solutions of P₀(𝜖) are not in $\widetilde {G_{0}}$. To get a new vector non-comparable with all vectors in G ₀, in view of remark 2.7, we add following constraints to P₀(𝜖) to get an extended version of P₀, denoted by P$_{0}^{E}(\epsilon )$.

$$\begin{array}{@{}rcl@{}} C_{i}W & > & C_{i}W_{j}^{*}-Mt_{ij}\\ C_{i}W -Ms_{ij}& < & C_{i}W_{j}^{*} \\ t_{ij} + s_{ij} & \leq & 1\\ t_{1j}+t_{2j}+ {\cdots} + t_{rj} & \leq & r-1\\ s_{1j}+s_{2j}+ {\cdots} + s_{rj} & \leq & r-1\\ s_{1j}+s_{2j}+ {\cdots} + s_{rj} & > & 0 \end{array} $$

(3.2)

where i = 1, 2, … , r, j = 1, 2, … , p, t _{i j} , s _{i j} ∈ {0, 1} and M is a positive large number.

We solve P$_{0}^{E}(\epsilon )$ to get all optimal feasible solutions $W_{p+l}^{*}$, l = 1, 2, … , p ₁. Put

$$\mathcal{O}_{0}^{\prime\prime} = \left\{W_{p+1}^{*},W_{p+2}^{*}, {\ldots} ,W_{p+p_{1}}^{*}\right\} $$

Let $z_{0}^{*}$ be an optimum value of P$_{0}^{E}(\epsilon )$. If P$_{0}^{E}(\epsilon )$ is infeasible we stop. Otherwise, since $z_{0}^{*}<z^{*}$, we modify the constraint (3.1) as

$$ \sum\limits_{i=1}^{r}C_{i}W < z_{0}^{*}-\epsilon $$

(3.3)

where 𝜖 ∈ (0, 1). Choose 𝜖 such that optimal feasible solutions are not in $G_{1}=G_{0} \cup \mathcal {O}_{0}^{\prime \prime }$. Denote the problem by P₁(𝜖). To get P$_{1}^{E}(\epsilon )$ add constraints like Eq. 3.2 in P₁(𝜖) for j = p + 1, … , p + p ₁. Let $\mathcal {O}_{1}^{\prime \prime }$ be the set of optimal solutions to P$_{1}^{E}(\epsilon )$ with optimum value $z_{1}^{*}$. Write $G_{2} = G_{1} \cup \mathcal {O}_{1}^{\prime \prime }$. In general, P$_{k}^{E}(\epsilon )$ is

$$\begin{array}{@{}rcl@{}} {\text{ Max} } &&\sum\limits_{i=1}^{r}C_{i}W, \\ {\text{ subject to }}&&AW \leq b,\\ \sum\limits_{i=1}^{r}C_{i}W & < & z_{k-1}^{*}-\epsilon\\ C_{i}W & > & C_{i}W_{j}^{*}-Mt_{ij}\\ C_{i}W -Ms_{ij}& < & C_{i}W_{j}^{*}\\ t_{ij} + s_{ij} & \leq & 1\\ t_{1j}+t_{2j}+ {\cdots} + t_{rj} & \leq & r-1\\ s_{1j}+s_{2j}+ {\cdots} + s_{rj} & \leq & r-1\\ s_{1j}+s_{2j}+ {\cdots} + s_{rj} & > & 0 \end{array} $$

(3.4)

where i = 1, 2, … , r; j = 1, 2, … , p, p + 1, … , p + p ₁, … , p + p ₁ + p ₂ + ⋯ + p _{k − 1} and w _j , t _{i j} , s _{i j} ∈ {0, 1}. Observe that

$$ {\cdots} < z_{k}^{*}<z_{k-1}^{*}< {\cdots} z_{1}^{*}<z_{0}^{*}< z^{*}. $$

(3.5)

Put

$$ G_{k} = G_{k-1} \cup \mathcal{O}_{k}^{\prime\prime} $$

(3.6)

Theorem 3.1

An optimum solution of Eq. 3.4 is an efficient solution of the problem (1.1). In particular, an optimal solution of Eq. 3.4 is not comparable with vectors in G _{k − 1}.

Proof

Let W ^∗ be an optimal solution of P$_{k}^{E}(\epsilon )$. Let $W_{j}^{*} \in G_{k-1}$. If for all i, t _{i j} = 0 then

$$ \begin{array}{rl} & C_{i}W^{*} > C_{i}W_{j}^{*} \quad\text{ for all } i\\ \Rightarrow & {\sum}_{i=1}^{r} C_{i}W^{*} > {\sum}_{i=1}^{r} C_{i}W_{j}^{*} = z_{t}^{*}\text{ for some } t \in \{0,1,\ldots , k-1\} \text{ or } z^{*} \end{array} $$

(3.6)

which is not true, because ${\sum }_{i=1}^{r} C_{i}W^{*} < z_{k-1}^{*} < z_{0}^{*} < z^{*}$. Hence there is i ₁ such that

$$\begin{array}{rl} & t_{i_{1} j} = 1\\ \Rightarrow & s_{i_{1} j} = 0\\ \Rightarrow & C_{i_{1}}W^{*} < C_{i_{1}}W_{j}^{*} \end{array} $$

Now, Since ${\sum }_{i=1}^{r}s_{ij} > 0$, there is i ₂ such that $s_{i_{2} j} = 1(\Rightarrow t_{i_{2} j} = 0$). Clearly i ₁ ≠ i ₂, otherwise $t_{i_{1} j} + s_{i_{1} j} > 1$. Thus, for i ₁ ≠ i ₂,

$$C_{i_{1}}W^{*} < C_{i_{1}}W_{j}^{*} \text{ and } C_{i_{2}}W^{*} > C_{i_{2}}W_{j}^{*} $$

i.e., W ^∗ is not comparable with vectors in G _{k − 1}. □

Theorem 3.2

(Theorem 2.5 [1]) Each efficient solution of the problem (1.1) not in G ₀ is an optimal solution of P $_{k}^{E}(\epsilon )$ for some k.

Proof

Suppose algorithm stops at k = N i.e, P$_{N}^{E}(\epsilon )$ is infeasible. This means there is no vector left in X − G _{N − 1} which is non-comparable with vectors in G _{N − 1}. Let W ^∗ be an efficient solution of the problem (1.1) not in G ₀ and let $z = {\sum }_{i=1}^{r} C_{i}W^{*}$.

Since W ^∗ is an efficient solution, it is non-comparable with vectors in G _{N − 1}. If $z < z_{N-1}^{*}$ then in view of Eq. 3.4, W ^∗ would satisfy constraints of P$_{N}^{E}(\epsilon )$, but P$_{N}^{E}(\epsilon )$ is infeasible. Therefore, $z\geq z_{N-1}^{*}$. Suppose

$$z_{k}^{*} \leq z \leq z_{k-1}^{*} \text{ for some } k=1,2{\ldots} , N-1$$

Since W ^∗ is an efficient solution, it is not comparable with vectors in G _k i.e., constraints of P$_{k}^{E}(\epsilon )$ are satisfied by W ^∗. This implies z = z ^∗ and hence W ^∗ ∈ G _k . □

Remark 3.3

The constraints

$$t_{1j}+t_{2j}+ {\cdots} + t_{rj} \leq r-1 \text{ and } s_{1j}+s_{2j}+ {\cdots} + s_{rj} \leq r-1 $$

are redundant.

We have

$$\begin{array}{rl} & t_{ij} + s_{ij} \leq 1\\ \Rightarrow & {\sum}_{i=1}^{r} (t_{ij} + s_{ij}) \leq r \end{array} $$

Since s _1j +s _2j +⋯+s _{r j} > 0 there is at least one s _{i j} > 0, hence ${\sum }_{i=1}^{r} s_{ij} \geq 1$. Thus

$$\sum\limits_{i=1}^{r} t_{ij} \leq r - \sum\limits_{i=1}^{r} s_{ij} \leq r - 1 $$

If s _{i j} = 1 for all i, t _{i j} = 0 for all i. We get

$$ C_{i}W > C_{i} W_{j}^{*} \quad \text{ for all } i $$

(3.7)

Note that $W_{j}^{*} \in G_{k}$. If $W_{j}^{*} \in \cup _{i=1}^{r} \mathcal {O}_{i}$ then $W_{j}^{*} \in \mathcal {O}_{k}$ for some k such that $\left | \mathcal {O}_{k}\right | =1$. Clearly Eq. 3.7 is not true for i = k. Further, if $W_{j}^{*} \in G_{k}-\left (\cup _{i=1}^{r} \mathcal {O}_{i}\right )$, then Eq. 3.7 implies

$$z_{k-1}^{*} > \sum\limits_{i=1}^{r} C_{i} W > \sum\limits_{i=1}^{r} C_{i} W_{j}^{*} = z_{t}^{*}\text{ for some } t \in \{0,1,{\ldots} , k-1\} \text{ or } z^{*} $$

which is not true in view of Eq. 3.5.

4 The example

Now, we consider the example (1.2) which originally from [2]. Note that, in this example C ₁ = (3, 6, 5, −2, 3), C ₂ = (6, 7, 4, 3, −8), C ₃ = (5, −3, 8, −4, 3). The unique optimum solutions of P₁, P₂, P₃ are $W_{1}^{*}=(1,1,1,1,1)$, $W_{2}^{*}=(1,1,1,0,0)$, $W_{3}^{*}=(1,0,1,0,1)$ respectively. In this case, P₀ is

$$ \begin{array}{rl} {\text{Max}} & 14w_{1}+10w_{2}+17w_{3}-3w_{4}-2w_{5}\\ {\text{Subject to}} & -2w_{1}+3w_{2}+8w_{3}-w_{4}+5w_{5} \leq 13\\ & 4w_{1}-2w_{2}+6w_{3}-2w_{4}+w_{5} \leq 11\\ & 6w_{1}+2w_{2}+4w_{3}+4w_{4}-3w_{5} \leq 15 \end{array} $$

(4.1)

Further, also note that the optimum solution for P₀ is $W_{2}^{*}$ with optimum value 41. Hence

$$G_{0} = \{ W_{1}^{*},W_{2}^{*},W_{3}^{*}\}. $$

To get P₀(𝜖) we add following constraint in P₀

$$ 14w_{1}+10w_{2}+17w_{3}-3w_{4}-2w_{5} < 41-\epsilon $$

(4.2)

Then, to get P$_{0}^{E}(\epsilon )$, we add following constraints

$$\begin{array}{@{}rcl@{}} (C_{1}W,C_{2}W,C_{3}W)& > & (15-Mt_{11},12-Mt_{21},9-Mt_{31})\\ (C_{1}W,C_{2}W,C_{3}W)& > & (14-Mt_{11},17-Mt_{21},10-Mt_{31})\\ (C_{1}W,C_{2}W,C_{3}W)& > &(11-Mt_{11},2-Mt_{21},16-Mt_{31})\\ (C_{1}W,C_{2}W,C_{3}W)& < & (15+Ms_{11},12+Ms_{21}, 9+Ms_{31})\\ (C_{1}W,C_{2}W,C_{3}W) &<& (14+Ms_{12},17+Ms_{22}, 10+Ms_{32})\\ (C_{1}W,C_{2}W,C_{3}W)& < &(11+Ms_{13},2+Ms_{23}, 16+Ms_{33})\\ t_{ij} + s_{ij} & \leq & 1\\ t_{1j}+t_{2j}+ t_{3j} &\leq & 2\\ s_{1j}+s_{2j}+ s_{3j} & \leq & 2\\ s_{1j}+s_{2j}+ s_{3j} & > & 0 \end{array} $$

(4.3)

where i = 1, 2, 3, j = 1, 2, 3.

The unique optimum solution is $W_{4}^{*} = (1,0,1,0,0)$ with optimum value 31. Next, we modify the constraint (4.2) as

$$ 14w_{1}+10w_{2}+17w_{3}-3w_{4}-2w_{5} < 31-\epsilon $$

(4.4)

and add the following constraints in Eq. 4.3 to get P$_{1}^{E}(\epsilon )$

$$\begin{array}{@{}rcl@{}} (C_{1}W,C_{2}W,C_{3}W)& > & (8-Mt_{14},10-Mt_{24},13-Mt_{34})\\ (C_{1}W,C_{2}W,C_{3}W)& < & (8+Ms_{14},10+Ms_{24}, 13+Ms_{34})\\ t_{i4} + s_{i4} & \leq & 1\\ t_{14}+t_{24}+ t_{34} & \leq & 2\\ s_{14}+s_{24}+ s_{34} & \leq & 2\\ s_{14}+s_{24}+ s_{34} & > & 0 \end{array} $$

(4.5)

The unique optimum solution of P$_{1}^{E}(\epsilon )$ is $W_{5}^{*} = (1,0,1,1,1)$ with optimum value 26. now, we modify (4.4) as

$$ 14w_{1}+10w_{2}+17w_{3}-3w_{4}-2w_{5} < 26-\epsilon $$

and add again following constraints in Eq. 4.5 to get P$_{2}^{E}(\epsilon )$

$$\begin{array}{@{}rcl@{}} (C_{1}W,C_{2}W,C_{3}W)& > & (9-Mt_{14},5-Mt_{24},12-Mt_{34})\\ (C_{1}W,C_{2}W,C_{3}W)& < & (9+Ms_{14},5+Ms_{24}, 12+Ms_{34})\\ t_{i5} + s_{i5} & \leq & 1\\ t_{15}+t_{25}+ t_{35} & \leq & 2\\ s_{15}+s_{25}+ s_{35} & \leq & 2\\ s_{15}+s_{25}+ s_{35} & > & 0 \end{array} $$

P$_{2}^{E}(\epsilon )$ is infeasible. Hence there are no efficient solutions left.