header
Testing Effectiveness:KNAPSACK

Tag:
Edit edit   Starstar

Program Information

Name: Testing Effectiveness:KNAPSACK
Domain: Optimization algorithms
Functionality: The KNAPSACK program attempts to calculate the optimal solution and thus to maximize the total profit.
Input: The KNAPSACK program accepts three sets of integers.Two $n$-tuple sets $P = \{p_1 , p_2 ,\cdots , p_n\}$ and $W = \{w_1 , w_2 ,\cdots , w_n \}$ represent the profits and the weights of $n$ items, respectively; while another $m$-tuple set $C = \{c_1 , c_2 , \cdots , c_m \}$ contains the capacities of m knapsacks. In the following, the source test case is denoted as $T = \{P, W, C\}$, where $P = \{p_1 , p_2 , \cdots , p_n \}, W = \{w_1 , w_2 , \cdots , w_n \}, C = \{c_1 , c_2 , \cdots , c_m \}$. 
Output: The outputs of KNAPSACK are one $n$-tuple set $Y = \{y_1 , y_2 , \cdots , y_n \}$ and one positive integer $TP$. $y_i = j$ (where $i = 1, 2, \ldots , n$ and $j = 0, 1, \ldots , m)$ represents that the $i^{th}$ item should be put into the $j^{th}$ knapsack. If $y_i = 0$, it means that the $i^{th}$ item will not be selected into any knapsack. $TP$ represents the total profit of the picked items. The output of the source test case is denoted as $O = \{Y, TP\}$. 

Reference

 On Testing Effectiveness of Metamorphic Relations:A Case Study https://doi.org/10.1109/SSIRI.2011.21 

MR Information

MR1------

Description:
Property: Swap the $k^{th}$ and the $l^{th}$ items, where $1 \leq k < l \leq n$, and $p_k \neq p_l$ or $w_k \neq w_l \Rightarrow Y'= \{y_1 , y_2 , \cdots , y_l , \cdots , y_k , \cdots , y_n\}$ and $TP' = TP$.
Source input:  $T=\{P,W,C\} $  
Source output:  $O=\{Y,TP\}$ 
Follow-up input: $T'=\{P',W',C\}$ 
Follow-up output: $O'=\{Y',TP'\}$
Input relation: $T \Rightarrow T'$ where $P' = \{p_1 , p_2 , \cdots , p_l , \cdots , p_k , \cdots , p_n \}$ and $W' = \{w_1 , w_2 , \cdots , w_l , \cdots , w_k , \cdots , w_n \}$; And $T'$ is construted by swapping the $k^{th}$ and the $l^{th}$ items, where $1 \leq k < l \leq n$, and $p_k \neq p_l$ or $w_k \neq w_l$
Output relation: $Y'= \{y_1 , y_2 , \cdots , y_l , \cdots , y_k , \cdots , y_n\}$ and $TP' = TP$ 
Pattern:

MR2------

Description:
Property: Select the $k^{th}$ item where $y_k=1$, and then increase its profit by a positive integer c,that is $p_k'=p_k+c$ $\Rightarrow y_j \cdot y_j'=0$ iff $y_j=y_j'=0$ and $TP'=TP+c$ 
Source input:  $T=\{P,W,C\} $   
Source output:   $O=\{Y,TP\}$ 
Follow-up input: $T'=\{P',W,C\}$  
Follow-up output:  $O'=\{Y',TP'\}$ where $Y'=\{y_1',y_2',\cdots ,y_n'\}$
Input relation: $T \Rightarrow T'$ where $P' = \{p_1 , p_2 , \cdots , p_k' , \cdots , p_n \}$; And $T'$ is construted by selecting the $k^{th}$ item where $y_k=1$, and then increase its profit by a positive integer c,that is $p_k'=p_k+c$
Output relation: $y_j \cdot y_j'=0$ iff $y_j=y_j'=0$ and $TP'=TP+c$ 
Pattern:

MR3------

Description:
Property: Select the $k^{th}$ item where $y_k=0$, and then increase its weight by a positive integer c,that is $w_k'=w_k+c$ $\Rightarrow y_j \cdot y_j'=0$ iff $y_j=y_j'=0$ and $TP'=TP$ 
Source input:  $T=\{P,W,C\} $   
Source output:   $O=\{Y,TP\}$ 
Follow-up input: $T'=\{P,W',C\}$  
Follow-up output:  $O'=\{Y',TP'\}$ where $Y'=\{y_1',y_2',\cdots ,y_n'\}$
Input relation: $T \Rightarrow T'$where $W' = \{w_1 , w_2 , \cdots , w_k' , \cdots , w_n \}$; And $T'$ is construted by selecting the $k^{th}$ item where $y_k=0$, and then increase its weight by a positive integer c,that is $w_k'=w_k+c$
Output relation: $y_j \cdot y_j'=0$ iff $y_j=y_j'=0$ and $TP'=TP$ 
Pattern:

MR4------

Description:
Property: Select the $k^{th}$ item where $y_k=0$, and then decrease its profit by a positive integer c,that is $p_k'=p_k-c$ $\Rightarrow y_j \cdot y_j'=0$ iff $y_j=y_j'=0$ and $TP'=TP$ 
Source input:  $T=\{P,W,C\} $   
Source output:   $O=\{Y,TP\}$ 
Follow-up input: $T'=\{P',W,C\}$ 
Follow-up output: $O'=\{Y',TP'\}$ where $Y'=\{y_1',y_2',\cdots ,y_n'\}$ 
Input relation: $T \Rightarrow T'$ where $P' = \{p_1 , p_2 , \cdots , p_k' , \cdots , p_n \}$ ; And $T'$ is construted by selecting the $k^{th}$ item where $y_k=0$, and then decrease its profit by a positive integer c,that is $p_k'=p_k-c$
Output relation: $y_j \cdot y_j'=0$ iff $y_j=y_j'=0$ and $TP'=TP$ 
Pattern:

MR5------

Description:
Property: Change the capacity of the $1^{st}$ knapsack to a new value $c_1'$,where $c_1'$ is equal to the summary of the weights of all items put into the $1^{st}$ knapsack. $\Rightarrow Y'=Y$ and $TP'=TP$ 
Source input:  $T=\{P,W,C\} $   
Source output:   $O=\{Y,TP\}$ 
Follow-up input: $T'=\{P,W,C'\}$ 
Follow-up output:  $O'=\{Y',TP'\}$
Input relation: $T \Rightarrow T'$ where $C' = \{c_1' , c_2 , \cdots ,c_m\}$; And $T'$ is construted by changing the capacity of the $1^{st}$ knapsack to a new value $c_1'$,where $c_1'$ is equal to the summary of the weights of all items put into the $1^{st}$ knapsack.
Output relation: $Y'=Y$ and $TP'=TP$ 
Pattern:

MR6------

Description:
Property: Add a new item at the position $n+1$,where $p_{n+1}=min(p_j)$ and $w_{n+1}=max(w_j)$ for all $j$ such that $y_j \neq 0 \Rightarrow Y'=\{y_1,y_2,\cdots ,y_n,0\}$ and $TP'=TP$ 
Source input:  $T=\{P,W,C\} $   
Source output:   $O=\{Y,TP\}$ 
Follow-up input: $T'=\{P',W',C\}$ 
Follow-up output:  $O'=\{Y',TP'\}$
Input relation: $T \Rightarrow T'$ where $P'=\{p_1,p_2,\cdots ,p_n,p_{n+1}\}$ and $W'=\{w_1,w_2,\cdots ,w_n,w_{n+1}\}$; And $T'$ is construted by adding a new item at the position $n+1$,where $p_{n+1}=min(p_j)$ and $w_{n+1}=max(w_j)$ for all $j$ such that $y_j \neq 0$
Output relation: $Y'=\{y_1,y_2,\cdots ,y_n,0\}$ and $TP'=TP$ 
Pattern:

MR7------

Description:
Property: Select the $k^{th}$ item where $y_k=0$,and then delete it.$\Rightarrow y_j\cdot y_j'=0$ iff $y_j=y_j'=0(j\neq k)$ and $TP'=TP$ 
Source input:  $T=\{P,W,C\} $   
Source output:   $O=\{Y,TP\}$ 
Follow-up input: $T'=\{P',W',C\}$  
Follow-up output: $O'=\{Y',TP'\}$ where $Y'=\{y_1',y_2',\cdots ,y_{k-1}',y_{k+1}',\cdots ,y_n'\}$ 
Input relation: $T \Rightarrow T'$ where $P'=\{p_1,p_2,\cdots,p_{k-1},p_{k+1},\cdots ,p_n\}$ and $W'=\{w_1,w_2,\cdots w_{k-1},w_{k+1},\cdots ,w_n\}$; And $T'$ is construted by selecting the $k^{th}$ item where $y_k=0$,and then delete it.
Output relation: $y_j\cdot y_j'=0$ iff $y_j=y_j'=0(j\neq k)$ and $TP'=TP$ 
Pattern:

MR8------

Description:
Property: Select the $k^{th}$ item where $y_k=1$, delete it,and then decrease the capacity of the $1^{st}$ knapsack by $w_k$ that is $c_1'=c_1-w_k \Rightarrow y_j\cdot y_j'=0$ iff $y_j=y_j'=0(j\neq k)$ and $TP'=TP-p_k$ 
Source input:  $T=\{P,W,C\} $   
Source output:   $O=\{Y,TP\}$ 
Follow-up input: $T'=\{P',W',C'\}$ 
Follow-up output: $O'=\{Y',TP'\}$ where $Y'=\{y_1',y_2',\cdots ,y_{k-1}',y_{k+1}',\cdots ,y_n'\}$ 
Input relation: $T \Rightarrow T'$ where $P'=\{p_1,p_2,\cdots,p_{k-1},p_{k+1},\cdots ,p_n\}$ and $W'=\{w_1,w_2,\cdots w_{k-1},w_{k+1},\cdots ,w_n\}$ and $C'=\{c_1-w_k,c_2,\cdots ,c_m\}$; And $T'$ is construted by selecting the $k^{th}$ item where $y_k=1$, delete it,and then decrease the capacity of the $1^{st}$ knapsack by $w_k$ that is $c_1'=c_1-w_k$
Output relation: $y_j\cdot y_j'=0$ iff $y_j=y_j'=0(j\neq k)$ and $TP'=TP-p_k$ 
Pattern:

MR9------

Description:
Property: Select the $k^{th}$ and $l^{th}$item where $1 \leq k <l \leq n$ and $y_k=y_l=i \neq 0 $ delete the $l^{th}$ item ,and then create a new $k^{th}$ where $p_k'=p_k+p_l$ and $w_k'=w_k+w_l \Rightarrow TP'=TP$ 
Source input:  $T=\{P,W,C\} $   
Source output:   $O=\{Y,TP\}$ 
Follow-up input: $T'=\{P',W',C'\}$ 
Follow-up output: $O'=\{Y',TP'\}$  
Input relation: $T \Rightarrow T'$ where $P'=\{p_1,p_2,\cdots,p_k+p_l,\cdots ,p_{l-1},p_{l+1},\cdots ,p_n\}$ and $W'=\{w_1,w_2,\cdots w_k+w_l,\cdots ,w_{l-1},w_{l+1},\cdots ,w_n\}$ and $C'=\{c_1-w_k,c_2,\cdots ,c_m\}$; And $T'$ is construted by selecting the $k^{th}$ and $l^{th}$item where $1 \leq k <l \leq n$ and $y_k=y_l=i \neq 0 $ delete the $l^{th}$ item ,and then create a new $k^{th}$ where $p_k'=p_k+p_l$ and $w_k'=w_k+w_l$
Output relation: $TP'=TP$ 
Pattern:

MR10------

Description:
Property: Delete all items put into the $1^{st}$ knapsack and delete the $1^{st}$ knapsack. Given that $\eta$ items were in the $1^{st}$ knapsack and their total profit is $v$ $\Rightarrow TP'=TP-v$ 
Source input:  $T=\{P,W,C\} $   
Source output:   $O=\{Y,TP\}$ 
Follow-up input: $T'=\{P',W',C'\}$ 
Follow-up output: $O'=\{Y',TP'\}$  
Input relation: $T \Rightarrow T'$ where $P'=\{p_1',p_2',\cdots,p_{n-\eta}'\}$ and $W'=\{w_1',w_2',\cdots ,w_{n-\eta}'\}$ and $C'=\{c_2,c_3,\cdots ,c_m\}$; And $T'$ is construted by deleting all items put into the $1^{st}$ knapsack and delete the $1^{st}$ knapsack. Given that $\eta$ items were in the $1^{st}$ knapsack and their total profit is $v$
Output relation: $TP'=TP-v$ 
Pattern:
Insert title here