<figure><img src="image_1.png" /></figure>

HAL
open science

Two-stage solution-based tabu search for the
multidemand multidimensional knapsack problem

Xiangjing Lai, Jin-Kao Hao, Dong Yue

► To cite this version:

Xiangjing Lai, Jin-Kao Hao, Dong Yue. Two-stage solution-based tabu search for the multidemand multidimensional knapsack problem. European Journal of Operational Research, 2019, 274 (1), pp.35-48. 10.1016/j.ejor.2018.10.001. hal-02309992

HAL Id: hal-02309992

https://hal.science/hal-02309992

Submitted on 23 Sep 2021

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Two-stage solution-based tabu search for the multidemand multidimensional knapsack problem

Xiangjing Lai<sup>a</sup>, Jin-Kao Hao<sup>b,c,*</sup>, Dong Yue<sup>a</sup>

<sup>a</sup>Institute of Advanced Technology, Nanjing University of Posts and Telecommunications, Nanjing 210023, China

<sup>b</sup>LERIA, Université d'Angers, 2 Boulevard Lavoisier, 49045 Angers, France

<sup>c</sup>Institut Universitaire de France, 1 Rue Descartes, 75231 Paris, France

## Abstract

The multidemand multidimensional knapsack problem (MDMKP) is a significant generalization of the popular multidimensional knapsack problem with relevant applications. In this work we investigate for the first time how solution-based tabu search can be used to solve this computationally challenging problem. For this purpose, we propose a two-stage search algorithm, where the first stage aims to locate a promising hyperplane within the whole search space and the second stage tries to find improved solutions by exploring the reduced subspace defined by the hyperplane. Computational experiments on 156 benchmark instances commonly used in the literature show that the proposed algorithm competes favorably with the state-of-the-art results. We analyze several key components of the algorithm to highlight their impacts on the performance of the algorithm.

**Keywords:** Metaheuristics; Multidemand multidimensional knapsack problem; Two-stage optimization; Solution-based tabu search; Combinatorial optimization.

## 1 Introduction

Given a set $V = \{1, 2, \dots, n\}$ of $n$ items, a set $R = \{r_1, r_2, \dots, r_m\}$ of $m$ resources with a capacity upper limit $b_i$ for resource $r_i$ ($1 \le i \le m$), where

<footnote>* Corresponding author.</footnote>

<footnote>Email addresses: laixiangjing@gmail.com (Xiangjing Lai), jin-kao.hao@univ-angers.fr (Jin-Kao Hao), medongy@vip.163.com (Dong Yue).</footnote>
each item $j$ of $V$ is associated with a profit $c_j$ and consumes a given quantity $a_{ij}$ for each resource $r_i$ ($i \in \{1, 2, \dots, m\}$), the popular NP-hard 0–1 multidimensional knapsack problem (MKP) involves selecting a subset of items from $V$ such that the resource consummation of the selected items does not exceed the given capacity upper limit for each resource in $R$ (knapsack constraints), while maximizing the total profit of the selected items. Formally, the MKP can be written as follows:

$$ (MKP) \quad \text{Maximize} \quad z = \sum_{j=1}^{n} c_j x_j \qquad (1) $$

$$ \text{s.t.} \quad \sum_{j=1}^{n} a_{ij}x_j \le b_i, \forall i \in \{1, 2, \dots, m\} \qquad (2) $$

$$ x_j \in \{0, 1\}, \forall j \in \{1, 2, \dots, n\} \qquad (3) $$

where $c_j \ge 0$, $a_{ij} > 0$, $b_i > 0$, $\forall i \in \{1, 2, \dots, m\}$, $\forall j \in \{1, 2, \dots, n\}$ and Eq. (3) indicates that the binary decision variable $x_j$ ($1 \le j \le n$) takes the value of 1 if the item $j$ is selected, 0 otherwise.

The multidemand multidimensional knapsack problem (MDMKP) studied in this work is an important extension of the MKP, where $q$ greater-than-or-equal-to constraints are imposed, in addition to $m$ less-than-or-equal-to constraints (Eq. (2)). Moreover, unlike the MKP, the profit $c_j$ in the MDMKP can take a positive, negative or zero value for each item $j$ ($j \in V$). Formally, the MDMKP can be formulated as follows [1,5]:

$$ (MDMKP) \quad \text{Maximize} \quad z = \sum_{j=1}^{n} c_j x_j \qquad (4) $$

$$ \text{s.t.} \quad \sum_{j=1}^{n} a_{ij}x_j \le b_i, \forall i \in \{1, 2, \dots, m\} \qquad (5) $$

$$ \sum_{j=1}^{n} a_{ij}x_j \ge b_i, \forall i \in \{m+1, m+2, \dots, m+q\} \qquad (6) $$

$$ x_j \in \{0, 1\}, \forall j \in \{1, 2, \dots, n\} \qquad (7) $$

where the following conditions are assumed:

$$ b_i > 0, a_{ij} \ge 0 \quad \forall i \in \{1, 2, \dots, m+q\}, \forall j \in \{1, 2, \dots, n\} \qquad (8) $$

$$ \sum_{j=1}^{n} a_{ij} > b_i \quad \forall i \in \{1, 2, \dots, m+q\} \qquad (9) $$

$$ \max_{j} \{a_{ij}\} \le b_i \quad \forall i \in \{1, 2, \dots, m\} \qquad (10) $$

$$ \min_{j} \{a_{ij}\} < b_i \quad \forall i \in \{m+1, 2, \dots, m+q\} \qquad (11) $$
In above formulas, the inequalities in Eq. (5) are called the knapsack con-
straints, and those in Eq. (6) are called the demand constraints.

Clearly, the classic MKP is a special case of the MDMKP when $q$ equals 0 and the profit $c_j$ of item $j$ takes a nonnegative value (i.e., $c_j \ge 0$, $\forall j \in V$).

Like the MKP, the MDMKP has a number of practical applications [5] like ob-
noxious and semiobnoxious facility location [4,22,24], capital-budgeting, and
portfolio-selection [3], among others. On the other hand, the MDMKP is com-
putationally challenging, given that it generalizes the NP-hard multidimen-
sional knapsack problem. Consequently, there is no polynomial-time algorithm
for the MDMKP, unless $P = NP$.

Unlike the MKP that has been subject of intensive studies in the past decades
(see e.g., [9,11,13,15,20,21,23,25–28]), the MDMKP receives much less atten-
tion until now. Still, there exist several exact and heuristic approaches in
the literature. For example, general mixed integer programming solvers like
CPLEX can be used to solve instances with $n \le 100$ to optimality within an ac-
ceptable time. However, it is usually difficult for the existing exact approaches
to find an optimal solution for larger instances. As a result, several heuristic
algorithms have been proposed to solve large instances approximately.

Specifically, in 2005, Cappanera and Trubian presented a nested-tabu-search
heuristic [5], which combines a standard attribute-based tabu search with
an oscillation method presented in [13]. In 2006, Arntzen et al. proposed an
adaptive memory search method called Almha in [1], which uses a dynami-
cal tabu search mechanism and a weighting scheme to handle infeasible solu-
tions. Their computational results show the Almha algorithm outperforms the
previous best MDMKP methods and can be viewed as one of the best per-
forming MDMKP algorithms in the literature. In 2007, Hvattum and Løkke-
tangen investigated the behavior of scatter search on the MDMKP [16]. In
2009, Gortázar et al. introduced a black box scatter search method for general
classes of binary optimization problems, and assessed their method on the
MDMKP and some other binary problems [14]. In particular, their method
uses a static penalty approach proposed in [32] to handle the constraints of
the MDMKP. In 2010, Hvattum et al. proposed an alternating control tree
(ACT) search framework for the MDMKP [17], which can lead to an exact al-
gorithm or heuristic algorithm by choosing the routine of solving subproblems.
Their computational results show that the associated ACT algorithms have
a high performance compared to a previous tabu search algorithm and scat-
ter search algorithm. At the same year, Balachandar proposed a dominance
principle based heuristic for the MDMKP [2].

In addition to these studies, there exist some theoretical investigations dedi-
cated to the MDMKP in the literature. For example, Delissa investigated the
existence and usefulness of equality cuts for the MDMKP [10], while Wishon and Villalobos studied robust efficiency measures for the MDMKP [30].

To enrich the solution arsenal for the MDMKP, we present in this work the first study of using solution-based tabu search [6,7,31] to effectively solve the MDMKP. Actually, unlike the popular attribute-based tabu search approach [12], solution-based tabu search began to attract attention only very recently. Interestingly, this approach already showed excellent performances on several binary optimization problems as reported in [19,20,29]. This work aims thus to investigate the interest of the solution-based tabu search approach for the MDMKP. Compared to attribute-based tabu search, solution-based tabu search has at least two appealing features. First, this approach ensures a stronger intensification ability, which is crucial for locating good local optima. Second, this approach makes the notion of tabu tenure irrelevant, thus simplifying the design of the algorithm and reducing the number of required parameters.

We summarize the contributions of this work as follows. First, based on the solution-based tabu search approach, we introduce an effective two-stage search algorithm for the MDMKP. The first search stage aims to identify a promising hyperplane within the whole search space while the second search stage tries to find improved solutions by examining both feasible and infeasible solutions on the identified hyperplane. For both stages, the solution-based tabu search strategy is employed, which relies on a one-flip and swap neighborhoods and a hash-based mechanism to efficiently determine the tabu status of neighbor solutions. Second, we assess the performance of the proposed algorithm based on 96 benchmark instances commonly used in the literature ($n = 100, 250, m = 5, 10$ and $q = 2, 5, 10$). The computational results show that the algorithm improves and matches the best known solutions for 17 and 71 instances respectively. Moreover, we report detailed computational results of the proposed algorithm for 60 additional instances with a large number of constraints (with $n = 100, 500, m = q = 30$). Third, given that the ideas of the two-stage search framework and solution-based tabu search developed in this work are quite general, they could be applied to solve other related binary optimization problems.

The remaining parts of the paper are structured as follows. In the next section, the proposed two-stage tabu search algorithm is described. In Section 3, we present the computational assessment of the proposed algorithm and report experimental results on the well-known benchmark instances. In Section 4, several essential ingredients of the algorithm are investigated to show how they affect the performance of the algorithm. In the last section, we summarize the present work and provide research perspectives.
## 2 Two-stage tabu search algorithm for the MDMKP

Our two-stage solution-based tabu search (TSTS) algorithm combines two search procedures working on two different search spaces. The first stage of the algorithm performs an exploratory search within the whole search space to find a feasible solution as good as possible. Starting from this solution, the second stage carries out a focused exploitation within the reduced space composed of candidate solutions with exactly *k* selected items (*k* being identified by the final solution of the first search stage). To explore both search spaces, TSTS relies on two solution-based tabu search procedures guided by a penalty-based evaluation function. One notices that the two-stage search strategy has been used with success to solve other knapsack problems like the Quadratic Knapsack Problem [8] and the classic MKP [26].

### 2.1 General Procedure

<table><caption>**Algorithm 1:** General procedure of two-stage tabu search algorithm for the MDMKP</caption><thead><tr><th></th><th></th><th></th></tr></thead><tbody><tr><td>1</td><td>Function TSTS()</td><td></td></tr><tr><td></td><td>Input: Instance I, time limit t<sub>max</sub></td><td></td></tr><tr><td></td><td>Output: The best solution s* found</td><td></td></tr><tr><td>2</td><td>begin</td><td></td></tr><tr><td>3</td><td>/* Initialization of solution</td><td>*/</td></tr><tr><td>3</td><td>s &larr; InitialSolution(I)</td><td>/* Sections 2.2 */</td></tr><tr><td></td><td>/* Optimization of the first stage</td><td>*/</td></tr><tr><td>4</td><td>{s, t} &larr; TabuSearch<sub>1</sub>(s)</td><td>/* Sections 2.3 */</td></tr><tr><td></td><td>/* Optimization of the second stage</td><td>*/</td></tr><tr><td>5</td><td>s &larr; TabuSearch<sub>2</sub>(s, t, t<sub>max</sub>)</td><td>/* Sections 2.4 */</td></tr><tr><td>6</td><td>return s</td><td></td></tr><tr><td>7</td><td>end</td><td></td></tr></tbody></table>

The proposed TSTS algorithm is thus composed of two optimization stages, where the first stage identifies a suitable hyperplane $\Omega_{[k]}$ (see Section 2.4.2 for the definition of hyperplane) that is exploited intensively during the second optimization stage to locate improved solutions (see Algorithm 1).

Specifically, the TSTS algorithm first generates randomly an initial solution by its initialization procedure (Section 2.2). Then the algorithm enters the first search stage where the initial solution is improved by the solution-based tabu search procedure presented in Sections 2.3 (line 4). During this search stage, the algorithm explores both feasible and infeasible solutions within the whole search space to find a high-quality feasible solution. At the end of its search stage, the best (feasible) solution found and the consumed time *t* are returned. At this point, the second search stage is triggered, which starts from
the solution returned by the first stage and uses another solution-based tabu search procedure (Section 2.4) to seek improved solutions (line 5). During this stage, the search is limited to the hyperplane $\Omega_{[k]}$ ($k$ being the number of the selected items in the returned solution of the first stage, see Section 2.4.1). Finally, the whole algorithm terminates when a given time limit $t_{max}$ is met, and the best solution found during the search process is returned as the final result of the algorithm (line 6).

## 2.2 Initial Solution

<table><caption>**Algorithm 2:** Procedure of Generating Initial Solution</caption><tr><td>1</td><td>Function <i>InitialSolution()</i></td></tr><tr><td></td><td><b>Input:</b> An instance <i>I</i>, the size of instance (<i>n</i>)</td></tr><tr><td></td><td><b>Output:</b> An initial solution <i>s</i> = (<i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, ..., <i>x</i><sub>n</sub>)</td></tr><tr><td>2</td><td><b>begin</b></td></tr><tr><td>3</td><td>&nbsp;&nbsp;&nbsp;&nbsp;<b>for</b> <i>i</i> &lt; 1 <b>to</b> <i>n</i> <b>do</b></td></tr><tr><td>4</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<i>x</i><sub><i>j</i></sub> &lt;&lt; <i>rand()</i> mod 2 /* <i>rand()</i> denotes a random integer */</td></tr><tr><td>5</td><td>&nbsp;&nbsp;&nbsp;&nbsp;<b>end</b></td></tr><tr><td>6</td><td>&nbsp;&nbsp;&nbsp;&nbsp;<i>s</i> &lt;&lt; (<i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, ..., <i>x</i><sub>n</sub>)</td></tr><tr><td>7</td><td><b>return</b> <i>s</i></td></tr><tr><td>8</td><td><b>end</b></td></tr></table>

The initial solution of the TSTS algorithm is generated by a randomized procedure whose pseudo-code is given in Algorithm 2. Specifically, given an instance with $n$ items, the initialization procedure assigns randomly a value from the set $\{0, 1\}$ to each component $x_i$ ($i = 1, 2, ..., n$) to obtain an initial solution $s = (x_1, x_2, ..., x_n)$. This random initialization has the advantage of being simple and fast. However, an initial solution generated in this way can be infeasible. If this is the case, its feasibility will be established during the first search stage described below.

## 2.3 Tabu Search Method of the First Search Stage

The first search stage is ensured by a solution-based tabu search algorithm (denoted by $TabuSearch_1$()), whose pseudo-code is given in Algorithm 3. After initiating its tabu lists (lines 3–5), $TabuSearch_1$() performs a number of iterations to improve the current solution until 1) a feasible solution is found and no improvement can be observed during $\alpha$ consecutive iterations, where $\alpha$ is a parameter called the depth of tabu search, or 2) the allowed maximum time limit $t_{max}$ is reached (lines 8–17). At each iteration, according to the tabu rule and the penalty-based evaluation function defined in Sections 2.3.2 and
<caption>**Algorithm 3:** Tabu search method used in the first search stage</caption>

1 **Function** TabuSearch<sub>1</sub>(*)
2 **Begin**
3     **Initialization of hash vectors (i.e., tabu lists)**
4     **for** i ← 0 **to** L − 1 **do**
5         $H_1[i] ← 0; H_2[i] ← 0; H_3[i] ← 0;$
6     **end**
7     $s^* ← s;$
8     **NoImprove ← 0**
9     **Main search procedure**
10     **while** (time() < $t_{max}$) ∧ ((NoImprove < $\alpha$) ∨ ($s^*$ is infeasible)) **do**
11         Find in $N_1(s) \cup N_2(s)$ a best non-tabu solution $s'$ in terms of the
12         extended evaluation function $F$ in Eq. (17)
13         /* $N_1(s)$ and $N_2(s)$ are defined in Eqs. (13) and (14), and
14         the tabu rule is given in Section 2.3.2
15         $s \leftarrow s'$
16         /* Update the current solution */
17         **if** ($F(s) > F(s^*)$ **then**
18             $s^* \leftarrow s$
19             **NoImprove ← 0**
20         **end**
21         /* Update the hash vectors (i.e., tabu lists) with $s$ */
22         $H_1[h_1(s)] ← 1; H_2[h_2(s)] ← 1; H_3[h_3(s)] ← 1$;
23         **NoImprove ← NoImprove + 1**
24     **end**
25     $t \leftarrow time()$
26     **return** {$s^*, t$}
27 **end**

2.3.3, a best non-tabu neighbor solution is selected to replace the current solu-
tion, and then the tabu lists are accordingly updated. Finally, the best feasible
solution found $s^*$ during this search stage and the computation time elapsed
t are returned as the results of the first search stage. As our experiments in
Section 3 show, the first search stage always ends up with a feasible solution
for all tested instances, including those with 30 demand constraints and 30
knapsack constraints. In other words, the first solution-based tabu search al-
gorithm is typically able to locate a promising valid hyperplane for the second
search stage.

The ingredients of this tabu search algorithm, including the search space, the
neighborhood structures and the tabu strategy, are respectively described in
the following subsections.

### 2.3.1 Search Space and Neighborhood

The search space $\Omega$ explored by the TabuSearch$_1()$ procedure is composed of all feasible and infeasible solutions of the given problem instance, i.e.,

$$ \Omega = \{(x_1, x_2, \dots, x_n) | x_i \in \{0, 1\}, 1 \le i \le n\} \quad (12) $$

The neighborhood used by TabuSearch$_1()$ is a combined neighborhood composed of two basic neighborhoods, namely the one-flip neighborhood $N_1$ and the swap neighborhood $N_2$. The one-flip neighborhood $N_1$ is defined by the one-flip operator (denoted by Flip($\cdot$)). Given a solution $s = (x_1, x_2, \dots, x_n)$, a one-flip move Flip($q$) consists of changing the value of a variable $x_q$ to its complementary value $1 - x_q$. As such, the neighborhood $N_1(s)$ of solution $s$ includes all possible solutions that can be obtained by applying the one-flip operator to $s$. Formally, the $N_1(s)$ can be written as follows:

$$ N_1(s) = \{s \oplus \text{Flip}(q) : 1 \le q \le n\} \quad (13) $$

The neighborhood $N_2$ is defined by the swap operator (denoted by Swap($\cdot, \cdot$)). Given a solution $s = (x_1, x_2, \dots, x_n)$, let $I^1 = \{q : x_q = 1 \text{ in } s\}$ and $I^0 = \{q : x_q = 0 \text{ in } s\}$, the swap neighborhood $N_2(s)$ can be written as follows:

$$ N_2(s) = \{s \oplus \text{Swap}(i, j) : i \in I^1, j \in I^0; \} \quad (14) $$

The first tabu search algorithm explores the union of these two neighborhoods, i.e., $N(s) = N_1(s) \cup N_2(s)$, whose size equals to $n + |I^1| \times |I^0|$. At each iteration of the algorithm, a best non-tabu solution from $N(s)$ according to the extended evaluation function defined by Eq. (17) in Section 2.3.3 and the tabu strategy explained in Section 2.3.2 is selected to replace the current solution $s$.

### 2.3.2 Tabu Strategy

In the present tabu search method, we adopt the solution-based tabu strategy to determine the tabu status of neighbor solutions. Specifically, the tabu lists are based on three hash vectors $H_1, H_2$, and $H_3$ of length of $L$, where each position of them represents a binary variable, and each hash vector $H_t$ is associated with a hash function $h_t$. In particular, the effect of hash functions is to map a candidate solution of the search space $\Omega$ to an index of $H_t$, i.e., $h_t : \Omega \to \{0, 1, 2, \dots, L-1\}$.
Based on these hash vectors and the associated hash functions, we determine the tabu status of candidate solutions by the following rule. Given a candidate solution $s$, the hash vectors $H_t$ ($t = 1, 2, 3$) and the associated hash functions $h_t$, $s$ is identified as a tabu solution if $H_1(h_1(s)) \land H_2(h_2(s)) \land H_3(h_3(s)) = 1$. Otherwise, $s$ is determined as a non-tabu solution.

Following previous studies [6,29,31], we define our hash functions as follows. Let $s = (x_1, x_2, \dots, x_n)$ be a candidate solution, our hash functions $h_t$ ($t = 1, 2, 3$) are given by:

$$h_t(s) = \left( \sum_{i=1}^{n} \lfloor i^{\gamma_t} \rfloor \times x_i \right) \mod L \quad (15)$$

where $\gamma_t$ is a parameter that is used to define each hash function and $L$ is the length of hash vectors that is empirically set to $10^8$ in this work.

Given a solution $s$ and its hash value $h(s)$, the hash value of its neighbor solutions can be determined in $O(1)$ according to Eq. (15). Thus, the time complexity of determining the tabu status of a neighbor solution is $O(1)$.

### 2.3.3 Extended Evaluation Function

Since the search space explored by the first tabu search algorithm contains both feasible and infeasible solutions, we devise an extended evaluation function $F$ which uses a penalty function $P$ to assess constraint violations.

Let $s$ be a candidate solution in $\Omega$, the penalty value $P(s)$ is defined as the summation of all constraint violations, i.e.,

$$P(s) = \sum_{i=1}^{m} \mathrm{Max}\{0, \sum_{j=1}^{n} a_{ij}x_j - b_i\} + \sum_{i=q+1}^{q+m} \mathrm{Max}\{0, b_i - \sum_{j=1}^{n} a_{ij}x_j\} \quad (16)$$

Thus, a small (large) function value $P(s)$ means a weak (strong) constraint violation in $s$. In particular, $P(s) = 0$ means that $s$ is a feasible solution.

Given this penalty function, the extended evaluation function $F(s)$ is defined as a linear combination of the objective function $f(s)$ in Eq. (4) and $P(s)$:

$$F(s) = \sum_{j=1}^{n} c_j x_j - \lambda \times P(s) \quad (17)$$

where $\lambda$ is a weighting factor that is empirically set to $10^2$ in this work.
For any two solutions $s'$ and $s''$ in $\Omega_{[k]}$, $s'$ is considered to be better than $s''$ if $F(s') > F(s'')$.

As shown in our experimental results (Section 3, Section 4.2 and the Appendix), the first search stage equipped with the extended evaluation function always ends up with a feasible solution for all tested instances, including those with 30 demand constraints and 30 knapsack constraints. In other words, the first solution-based tabu search algorithm is typically able to locate a promising valid hyperplane that is further explored by the second search stage.

## 2.4 Tabu Search Method of the Second Search Stage

The second optimization stage of the TSTS algorithm uses another tabu search algorithm (denoted by TabuSearch₂(), Algorithm 4) to examine candidate solutions of a given hyperplane $\Omega_{[k]}$ (see below). Unlike the first tabu search algorithm, TabuSearch₂() explores only solutions that contain exactly *k* selected items. TabuSearch₂() first initializes the hash vectors (lines 3–5), and then performs a number of iterations to improve the current solution (lines 7–14). At each iteration, the algorithm replaces the current solution by a best non-tabu neighbor solution $s'$ in terms of the evaluation function in Eq. (17). During the search, the best feasible solution encountered $s^*$ is updated each time a better feasible solution is found, and the hash vectors are accordingly updated by the new solution (line 13). Finally, the algorithm terminates if the time limit $t_{max}$ is reached, and then returns the best feasible solution $s^*$ found during the search process.

### 2.4.1 Search Space, Tabu Strategy and Evaluation Function

The search space $\Omega_{[k]}$ explored by TabuSearch₂() is composed of both feasible and infeasible solutions with a fixed number of *k* selected items. In other words, $\Omega_{[k]}$ contains all *n*-dimensional 0–1 vectors with $\sum_{i=1}^n x_i = k$, i.e., $\Omega_{[k]} = \{x \in \{0, 1\}^n | \sum_{i=1}^n x_i = k\}$. $\Omega_{[k]}$ is also called a hyperplane of the search space $\Omega$ defined in Section 2.3.1, i.e., $\Omega = \cup_{k=1}^n \Omega_{[k]}$.

Additionally, like the first tabu search algorithm, TabuSearch₂() uses the solution-based tabu strategy described in Section 2.3.2 to determine the tabu status of neighbor solutions, and employs the extended evaluation function in Eq. (17) to evaluate the solutions in the search space $\Omega_{[k]}$.
<caption>**Algorithm 4:** The tabu search method used in the second search stage</caption>

1 **Function** TabuSearch<sub>2</sub>(*)
2 **Begin**
3     **Initialization of hash vectors (i.e., tabu lists)**
4     for *i* ← 0 to *L* − 1 do
5         *H*<sub>1</sub>[*i*] ← 0; *H*<sub>2</sub>[*i*] ← 0; *H*<sub>3</sub>[*i*] ← 0
6     end
7     **s* ← *s*
8     **Main search procedure**
9     **while** *time*() < *t*<sub>max</sub> − *t* do
10         Find in *N*<sub>3</sub>(*s*) a best non-tabu solution *s*′ in terms of the extended evaluation function *F* in Eq. (17) **N**<sub>3</sub>(*s*) is defined in Eq. (18), and the tabu rule is given in Section 2.4.1. ***/
11         *s* ← *s*′
12         **Update the current solution**
13         **if** *F*(*s*) > *F*(*s*<sup>*</sup>) ∧ *P*(*s*) = 0 **then**
14             **s* ← *s*
15         end
16         **Update the hash vectors (i.e., tabu lists) with** *s*
17         *H*<sub>1</sub>[*h*<sub>1</sub>(*s*)] ← 1; *H*<sub>2</sub>[*h*<sub>2</sub>(*s*)] ← 1; *H*<sub>3</sub>[*h*<sub>3</sub>(*s*)] ← 1
18     end
19     **return** *s*<sup>*</sup>
20 **end**

2.4.2 Neighborhood Structure

To search effectively the hyperplane Ω<sub>[k]</sub>, TabuSearch<sub>2</sub>() uses a constrained
swap neighborhood N<sub>3</sub>(s). Formally, given a solution s = (x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>n</sub>), the
neighborhood N<sub>3</sub>(s) is given by:

$$
N_3(s) = \{s \oplus \text{Swap}(i, j) : i \in I^1, j \in I^0; f(s \oplus \text{Swap}(i, j)) > f(s^*)\} \quad (18)
$$

where *f*(.) is the objective function of the MDMKP in Eq. (4), *s*\* is the best
feasible solution found so far in the current tabu search run, *I*<sup>1</sup> and *I*<sup>0</sup> denote
respectively the sets of indices having the value of 1 (selected items) and 0
(non selected items) in *s*. Clearly, the size of this neighborhood is bounded
by *O*(|*I*<sup>1</sup>| × |*I*<sup>0</sup>|). It is worth noting that we constraint the neighborhood
by *f*(*s* ⊕ *Swap*(*i*, *j*)) > *f*(*s*\*) to eliminate non-promising neighbor solutions.
Similar idea was previously investigated for the related MKP in [26].
## 2.5 Space and Time Complexities of the Algorithm

At each stage of our TSTS algorithm, in addition to three hash vectors (i.e., $H_1$, $H_2$ and $H_3$) with a length of $L$, we maintain three solutions (i.e., $s, s',$ and $s^*$) to follow the search process, where each solution is stored by two vectors (i.e., $I^1$ and $I^0$) with a maximum length of $n$ and a vector $W = (w_1, w_2, ..., w_{m+q})$ where $w_i = \sum_{j=1}^{n} a_{ij}x_j$ ($j \in V$) holds. Thus, the space complexity of our TSTS algorithm is bounded by $O(n + m + q + L)$.

In addition, for each neighbor solution in the search space, the time complexity of evaluating its quality is bounded by $O(m+q)$, since there are $m+q$ constraints needed to be checked. Hence, for each iteration, the time complexities of the first and second tabu search stages are respectively bounded by $O((m+q) \times (n + |I^1| \times |I^0|))$ and $O((m+q) \times (|I^1| \times |I^0|))$ according to the size of neighborhoods explored by the algorithm (see Sections 2.3.1 and 2.4.2).

# 3 Experimental Results and Comparisons

We evaluate the proposed TSTS algorithm by conducting extensive computational experiments based on four sets of benchmark instances commonly used in the literature and by making a comparison between our results and the state-of-the-art results in the literature.

## 3.1 Benchmark Instances

In this study, we employed four sets of benchmark instances to assess the performance of our TSTS algorithm, where the first two sets of benchmark instances are available at http://www.optsicom.es/binaryss, and the third and fourth sets of benchmark instances are available in OR-Library<fnref n="1" />. The first set contains 48 small instances with $n = 100$, and the second set contains 48 larger instances with $n = 250$. In addition, for the instances in the first two sets, the number of knapsack constrains $m$ varies from 5 to 10, and the number of demand constraints $q$ belongs to {2, 5, 10}. The third set includes 30 instances with $n = 100$, where both the number of knapsack constrains $m$ and the number of demand constraints $q$ equal to 30. The fourth set is composed of 30 large instances with $n = 500, m = 30$ and $q = 30$.

<footnote n="1">¹ http://people.brunel.ac.uk/~mastjjb/jeb/info.html</footnote>
## 3.2 Parameter Settings and Experimental Protocol

<table><caption>Table 1
Settings of parameters</caption><thead><tr><td>Parameters</td><td>Section</td><td>Description</td><td>Values</td></tr></thead><tbody><tr><td>α</td><td>2.3</td><td>tabu depth of TabuSearch<sub>1</sub>()</td><td>5 × 10<sup>3</sup></td></tr><tr><td>γ<sub>1</sub></td><td>2.3</td><td>parameter used in the hash function</td><td>1.9</td></tr><tr><td>γ<sub>2</sub></td><td>2.3</td><td>parameter used in the hash function</td><td>2.1</td></tr><tr><td>γ<sub>3</sub></td><td>2.3</td><td>parameter used in the hash function</td><td>2.3</td></tr></tbody></table>

Our TSTS algorithm employs four parameters, including $γ_1$, $γ_2$ and $γ_3$ that are used to define the hash functions, and the depth $α$ of tabu search used in the first search stage. The parameters $γ_1$, $γ_2$ and $γ_3$ are set as in Table 1 according to the analysis shown in Section 4.3 while $α$ is empirically set to $5 \times 10^3$.

In addition, our algorithm was implemented in C++ and compiled by g++ compiler with -O3 option<fnref n="2" />. All computational experiments were carried out on a computer with an Intel E5-2670 processor (2.5 GHz and 2G RAM), running the Linux operating system. Moreover, when running the DIMACS machine benchmark procedure dmclique<fnref n="3" />, our processor requires 0.19, 1.17, and 4.54 seconds to solve the graphs r300.5, r400.5, and r500.5, respectively. Finally, due to the stochastic nature of the algorithm, we independently ran the algorithm 30 times to solve each instance, where the time limit $t_{max}$ for each run was set to 60 seconds for instances with $n \le 250$ according to [14]. For the large instances with $n = 500$, the time limit $t_{max}$ was set to $n$ seconds, where $n$ is the size of instances.

## 3.3 Computational Results and Comparison

In this section, we report the computational results of our TSTS algorithm on the first two sets of benchmark instances. We provide in the Appendix the computational results of TSTS on the third and fourth sets of benchmark instances for which no detailed results are available for existing algorithms in the literature.

The computational results of our TSTS algorithm on the first set of benchmark instances with $n = 100$ are summarized in Table 2, together with the results of the Almha algorithm implemented in [14]. Column 1 gives the names of instances. Columns 2 and 3 indicate respectively the best known objective

<footnote n="2">² The source code of our TSTS algorithm will be available at our website: http://www.info.univ-angers.fr/pub/hao/mdmkp.html</footnote>

<footnote n="3">³ ftp://dimacs.rutgers.edu/pub/dsj/clique</footnote>
<caption>Table 2</caption>

Computational results and comparison on the 48 instances with $n = 100$. In terms of $f_{best}$, the improved results are indicated in bold compared to the best known objective values (BKV).

<table><thead><tr><th rowspan="2">Instance</th><th rowspan="2">BKV</th><th rowspan="2">Almha</th><th colspan="4">TSTS (this work)</th></tr><tr><th>f<sub>best</sub></th><th>f<sub>avg</sub></th><th>f<sub>worst</sub></th><th>σ<sub>f</sub></th></tr></thead><tbody><tr><td>100-5-2-0-0</td><td>28384</td><td>28384</td><td>28384</td><td>28374.63</td><td>28103</td><td>50.44</td></tr><tr><td>100-5-2-0-1</td><td>26386</td><td>26386</td><td>26386</td><td>26386.00</td><td>26386</td><td>0.00</td></tr><tr><td>100-5-2-0-2</td><td>23484</td><td>23424</td><td>23484</td><td>23450.83</td><td>23285</td><td>74.16</td></tr><tr><td>100-5-2-0-3</td><td>27374</td><td>27374</td><td>27374</td><td>27365.33</td><td>27290</td><td>20.45</td></tr><tr><td>100-5-2-0-4</td><td>30632</td><td>30632</td><td>30632</td><td>30632.00</td><td>30632</td><td>0.00</td></tr><tr><td>100-5-2-0-5</td><td>44674</td><td>44614</td><td>44674</td><td>44650.93</td><td>44518</td><td>51.70</td></tr><tr><td>100-5-2-1-0</td><td>10379</td><td>10307</td><td>10379</td><td>10359.13</td><td>10276</td><td>22.53</td></tr><tr><td>100-5-2-1-1</td><td>11114</td><td>11074</td><td>11114</td><td>11114.00</td><td>11114</td><td>0.00</td></tr><tr><td>100-5-2-1-2</td><td>10124</td><td>10022</td><td>10124</td><td>10108.53</td><td>10066</td><td>25.65</td></tr><tr><td>100-5-2-1-3</td><td>10567</td><td>10559</td><td>10567</td><td>10567.00</td><td>10567</td><td>0.00</td></tr><tr><td>100-5-2-1-4</td><td>10658</td><td>10658</td><td>10658</td><td>10566.00</td><td>10451</td><td>49.10</td></tr><tr><td>100-5-2-1-5</td><td>17550</td><td>17550</td><td>17550</td><td>17540.30</td><td>17494</td><td>14.72</td></tr><tr><td>100-5-5-0-0</td><td>21892</td><td>21892</td><td>21892</td><td>21831.20</td><td>21740</td><td>74.46</td></tr><tr><td>100-5-5-0-1</td><td>26280</td><td>26280</td><td>26280</td><td>26280.00</td><td>26280</td><td>0.00</td></tr><tr><td>100-5-5-0-2</td><td>20628</td><td>20628</td><td>20628</td><td>20628.00</td><td>20628</td><td>0.00</td></tr><tr><td>100-5-5-0-3</td><td>21547</td><td>21547</td><td>21547</td><td>21547.00</td><td>21547</td><td>0.00</td></tr><tr><td>100-5-5-0-4</td><td>25074</td><td>25067</td><td>25074</td><td>25074.00</td><td>25074</td><td>0.00</td></tr><tr><td>100-5-5-0-5</td><td>40327</td><td>40327</td><td>40327</td><td>40320.47</td><td>40272</td><td>16.80</td></tr><tr><td>100-5-5-1-0</td><td>10263</td><td>10263</td><td>10263</td><td>10248.87</td><td>10210</td><td>23.44</td></tr><tr><td>100-5-5-1-1</td><td>10625</td><td>10625</td><td>10625</td><td>10625.00</td><td>10625</td><td>0.00</td></tr><tr><td>100-5-5-1-2</td><td>10198</td><td>10126</td><td>10198</td><td>10149.27</td><td>10124</td><td>34.47</td></tr><tr><td>100-5-5-1-3</td><td>10030</td><td>9959</td><td>10030</td><td>10019.60</td><td>9874</td><td>38.91</td></tr><tr><td>100-5-5-1-4</td><td>9964</td><td>9838</td><td>9964</td><td>9926.20</td><td>9775</td><td>64.25</td></tr><tr><td>100-5-5-1-5</td><td>15603</td><td>15591</td><td>15603</td><td>15603.00</td><td>15603</td><td>0.00</td></tr><tr><td>100-10-5-0-0</td><td>21852</td><td>21843</td><td>21852</td><td>21852.00</td><td>21852</td><td>0.00</td></tr><tr><td>100-10-5-0-1</td><td>20645</td><td>20586</td><td>20645</td><td>20593.10</td><td>20514</td><td>45.39</td></tr><tr><td>100-10-5-0-2</td><td>19517</td><td>19517</td><td>19517</td><td>19507.37</td><td>19228</td><td>51.88</td></tr><tr><td>100-10-5-0-3</td><td>20596</td><td>20556</td><td>20596</td><td>20514.20</td><td>20454</td><td>69.20</td></tr><tr><td>100-10-5-0-4</td><td>19423</td><td>19278</td><td>19423</td><td>19248.37</td><td>19218</td><td>41.68</td></tr><tr><td>100-10-5-0-5</td><td>35933</td><td>35903</td><td>35933</td><td>35856.00</td><td>35743</td><td>92.42</td></tr><tr><td>100-10-5-1-0</td><td>10018</td><td>10000</td><td>10018</td><td>10018.00</td><td>10018</td><td>0.00</td></tr><tr><td>100-10-5-1-1</td><td>9839</td><td>9839</td><td>9839</td><td>9837.83</td><td>9804</td><td>6.28</td></tr><tr><td>100-10-5-1-2</td><td>10000</td><td>10000</td><td>10000</td><td>9989.60</td><td>9688</td><td>56.01</td></tr><tr><td>100-10-5-1-3</td><td>10544</td><td>10544</td><td>10544</td><td>10535.33</td><td>10479</td><td>22.10</td></tr><tr><td>100-10-5-1-4</td><td>10011</td><td>9878</td><td>10011</td><td>9961.57</td><td>9908</td><td>46.28</td></tr><tr><td>100-10-5-1-5</td><td>16230</td><td>16210</td><td>16230</td><td>16220.33</td><td>16095</td><td>33.69</td></tr><tr><td>100-10-10-0-0</td><td>22054</td><td>22054</td><td>22054</td><td>22054.00</td><td>22054</td><td>0.00</td></tr><tr><td>100-10-10-0-1</td><td>20103</td><td>20103</td><td>20103</td><td>20103.00</td><td>20103</td><td>0.00</td></tr><tr><td>100-10-10-0-2</td><td>19381</td><td>19312</td><td>19381</td><td>19371.80</td><td>19312</td><td>23.46</td></tr><tr><td>100-10-10-0-3</td><td>17434</td><td>17434</td><td>17434</td><td>17434.00</td><td>17434</td><td>0.00</td></tr><tr><td>100-10-10-0-4</td><td>18792</td><td>18792</td><td>18833</td><td>18794.73</td><td>18792</td><td>10.23</td></tr><tr><td>100-10-10-0-5</td><td>33837</td><td>33833</td><td>33837</td><td>33832.23</td><td>33702</td><td>24.20</td></tr><tr><td>100-10-10-1-0</td><td>8560</td><td>8560</td><td>8560</td><td>8513.17</td><td>8475</td><td>26.22</td></tr><tr><td>100-10-10-1-1</td><td>8493</td><td>8493</td><td>8493</td><td>8489.80</td><td>8397</td><td>17.23</td></tr><tr><td>100-10-10-1-2</td><td>9266</td><td>9227</td><td>9266</td><td>9266.00</td><td>9266</td><td>0.00</td></tr><tr><td>100-10-10-1-3</td><td>9823</td><td>9823</td><td>9823</td><td>9819.13</td><td>9707</td><td>20.82</td></tr><tr><td>100-10-10-1-4</td><td>8929</td><td>8929</td><td>8929</td><td>8914.00</td><td>8839</td><td>33.54</td></tr><tr><td>100-10-10-1-5</td><td>14152</td><td>14151</td><td>14152</td><td>14144.33</td><td>14106</td><td>17.14</td></tr><tr><td>Avg.</td><td>18108.10</td><td>18083.17</td><td>18108.96</td><td>18088.27</td><td>18023.38</td><td>24.98</td></tr><tr><td>#Better</td><td></td><td></td><td>1</td><td></td><td></td><td></td></tr><tr><td>#Equal</td><td></td><td></td><td>47</td><td></td><td></td><td></td></tr><tr><td>#Worse</td><td></td><td></td><td>0</td><td></td><td></td><td></td></tr><tr><td>p-value</td><td></td><td></td><td>3.2e-1</td><td></td><td>8.7e-1</td><td></td></tr></tbody></table>
<caption>Table 3</caption>

Computational results and comparison on the 48 instances with $n = 250$. In terms of $f_{best}$, the improved results are indicated in bold and the worse results are indicated in italic compared to the best known objective value (BKV).

<table><thead><tr><th rowspan="2">Instance</th><th rowspan="2">BKV</th><th rowspan="2">Almha</th><th colspan="4">TSTS (this work)</th></tr><tr><th>f<sub>best</sub></th><th>f<sub>avg</sub></th><th>f<sub>worst</sub></th><th>σ<sub>f</sub></th></tr></thead><tbody><tr><td>250-5-2-0-0</td><td>78486</td><td>78413</td><td>78486</td><td>78289.00</td><td>77644</td><td>146.76</td></tr><tr><td>250-5-2-0-1</td><td>75132</td><td>75086</td><td>75132</td><td>74833.33</td><td>73702</td><td>269.45</td></tr><tr><td>250-5-2-0-2</td><td>71003</td><td>70895</td><td>70898</td><td>70674.93</td><td>69762</td><td>285.03</td></tr><tr><td>250-5-2-0-3</td><td>80311</td><td>80227</td><td>80311</td><td>80206.57</td><td>80065</td><td>51.12</td></tr><tr><td>250-5-2-0-4</td><td>70935</td><td>70918</td><td>70935</td><td>70834.30</td><td>70583</td><td>70.55</td></tr><tr><td>250-5-2-0-5</td><td>130981</td><td>130863</td><td>130191</td><td>129271.40</td><td>127061</td><td>780.97</td></tr><tr><td>250-5-2-1-0</td><td>26666</td><td>26529</td><td>26666</td><td>26573.83</td><td>26457</td><td>54.46</td></tr><tr><td>250-5-2-1-1</td><td>26864</td><td>26778</td><td>26864</td><td>26806.77</td><td>26690</td><td>46.08</td></tr><tr><td>250-5-2-1-2</td><td>27280</td><td>27158</td><td>27280</td><td>27235.83</td><td>27109</td><td>47.32</td></tr><tr><td>250-5-2-1-3</td><td>26269</td><td>26160</td><td>26250</td><td>26173.90</td><td>26098</td><td>37.88</td></tr><tr><td>250-5-2-1-4</td><td>27293</td><td>27149</td><td>27287</td><td>27204.13</td><td>27131</td><td>25.01</td></tr><tr><td>250-5-2-1-5</td><td>44419</td><td>44216</td><td>44395</td><td>44302.57</td><td>44163</td><td>58.29</td></tr><tr><td>250-5-5-0-0</td><td>68026</td><td>68000</td><td>68026</td><td>68017.03</td><td>67978</td><td>15.64</td></tr><tr><td>250-5-5-0-1</td><td>60795</td><td>60727</td><td>60766</td><td>60627.90</td><td>60258</td><td>141.78</td></tr><tr><td>250-5-5-0-2</td><td>62093</td><td>62093</td><td>62093</td><td>62072.57</td><td>61960</td><td>28.50</td></tr><tr><td>250-5-5-0-3</td><td>66567</td><td>66513</td><td>66567</td><td>66519.80</td><td>66384</td><td>42.28</td></tr><tr><td>250-5-5-0-4</td><td>61929</td><td>61929</td><td>61929</td><td>61925.90</td><td>61878</td><td>11.66</td></tr><tr><td>250-5-5-0-5</td><td>127934</td><td>127890</td><td>127922</td><td>127708.10</td><td>127211</td><td>181.12</td></tr><tr><td>250-5-5-1-0</td><td>26966</td><td>26898</td><td>26973</td><td>26918.43</td><td>26853</td><td>31.01</td></tr><tr><td>250-5-5-1-1</td><td>26665</td><td>26520</td><td>26665</td><td>26576.10</td><td>26462</td><td>54.58</td></tr><tr><td>250-5-5-1-2</td><td>26648</td><td>26468</td><td>26648</td><td>26556.97</td><td>26403</td><td>49.58</td></tr><tr><td>250-5-5-1-3</td><td>25923</td><td>25701</td><td>25885</td><td>25784.30</td><td>25695</td><td>38.65</td></tr><tr><td>250-5-5-1-4</td><td>26021</td><td>25931</td><td>26060</td><td>25992.03</td><td>25882</td><td>41.71</td></tr><tr><td>250-5-5-1-5</td><td>41372</td><td>41131</td><td>41338</td><td>41237.67</td><td>41104</td><td>49.44</td></tr><tr><td>250-10-5-0-0</td><td>56306</td><td>56142</td><td>56260</td><td>55900.43</td><td>55344</td><td>274.20</td></tr><tr><td>250-10-5-0-1</td><td>59564</td><td>59504</td><td>59619</td><td>59551.47</td><td>59330</td><td>64.43</td></tr><tr><td>250-10-5-0-2</td><td>54898</td><td>54817</td><td>54890</td><td>54657.33</td><td>54367</td><td>109.54</td></tr><tr><td>250-10-5-0-3</td><td>52399</td><td>51987</td><td>52249</td><td>52105.73</td><td>51588</td><td>155.34</td></tr><tr><td>250-10-5-0-4</td><td>58234</td><td>57970</td><td>58119</td><td>57750.73</td><td>57113</td><td>291.28</td></tr><tr><td>250-10-5-0-5</td><td>99682</td><td>99452</td><td>99512</td><td>99201.73</td><td>98604</td><td>213.06</td></tr><tr><td>250-10-5-1-0</td><td>26867</td><td>26845</td><td>26961</td><td>26866.77</td><td>26716</td><td>59.78</td></tr><tr><td>250-10-5-1-1</td><td>26585</td><td>26441</td><td>26658</td><td>26538.87</td><td>26390</td><td>62.11</td></tr><tr><td>250-10-5-1-2</td><td>25737</td><td>25543</td><td>25737</td><td>25598.13</td><td>25322</td><td>83.93</td></tr><tr><td>250-10-5-1-3</td><td>27162</td><td>26982</td><td>27159</td><td>27089.60</td><td>26952</td><td>60.98</td></tr><tr><td>250-10-5-1-4</td><td>26816</td><td>26774</td><td>26815</td><td>26729.87</td><td>26635</td><td>46.01</td></tr><tr><td>250-10-5-1-5</td><td>46244</td><td>46087</td><td>46244</td><td>46145.40</td><td>46112</td><td>18.18</td></tr><tr><td>250-10-10-0-0</td><td>52441</td><td>52343</td><td>52407</td><td>52326.03</td><td>52045</td><td>113.59</td></tr><tr><td>250-10-10-0-1</td><td>53720</td><td>53603</td><td>53745</td><td>53663.80</td><td>53493</td><td>48.05</td></tr><tr><td>250-10-10-0-2</td><td>46927</td><td>46703</td><td>46927</td><td>46770.97</td><td>46487</td><td>81.50</td></tr><tr><td>250-10-10-0-3</td><td>54782</td><td>54779</td><td>54831</td><td>54745.93</td><td>54441</td><td>84.37</td></tr><tr><td>250-10-10-0-4</td><td>49675</td><td>49562</td><td>49660</td><td>49575.43</td><td>49327</td><td>72.88</td></tr><tr><td>250-10-10-0-5</td><td>92959</td><td>92792</td><td>92975</td><td>92821.53</td><td>92473</td><td>98.62</td></tr><tr><td>250-10-10-1-0</td><td>26696</td><td>26651</td><td>26696</td><td>26667.67</td><td>26564</td><td>40.85</td></tr><tr><td>250-10-10-1-1</td><td>25757</td><td>25692</td><td>25876</td><td>25786.43</td><td>25721</td><td>28.17</td></tr><tr><td>250-10-10-1-2</td><td>26356</td><td>26438</td><td>26517</td><td>26470.70</td><td>26418</td><td>32.17</td></tr><tr><td>250-10-10-1-3</td><td>26684</td><td>26443</td><td>26684</td><td>26614.77</td><td>26518</td><td>50.58</td></tr><tr><td>250-10-10-1-4</td><td>26554</td><td>26428</td><td>26676</td><td>26617.33</td><td>26511</td><td>28.13</td></tr><tr><td>250-10-10-1-5</td><td>42528</td><td>42284</td><td>42629</td><td>42464.80</td><td>42376</td><td>64.06</td></tr><tr><td>Avg.</td><td>49836.48</td><td>49717.81</td><td>49821.10</td><td>49687.60</td><td>49403.75</td><td>98.76</td></tr><tr><td>#Better</td><td></td><td></td><td>12</td><td></td><td></td><td></td></tr><tr><td>#Equal</td><td></td><td></td><td>18</td><td></td><td></td><td></td></tr><tr><td>#Worse</td><td></td><td></td><td>18</td><td></td><td></td><td></td></tr><tr><td>p-value</td><td></td><td></td><td>2.7e-1</td><td>4.0e-2</td><td></td><td></td></tr></tbody></table>
values (BKV) and the results of the Almha algorithm, which were reported
in [14] and available at http://www.optsicom.es/binaryss. The results of
our TSTS algorithm are reported in columns 4–7, including the best objective
value obtained over 30 runs ($f_{best}$), the average objective value ($f_{avg}$), the
worst objective value ($f_{worst}$), and the standard deviation ($\sigma_{f}$) of objective
values. The row Avg. shows the average result over all instances tested for
each column. The rows #Better, #Equal, and #Worse respectively show
the number of instances for which our best result $f_{best}$ is better than, equal to,
worse than the BKV. Moreover, in terms of $f_{best}$, our improved results (new
lower bounds) are indicated in bold and our worse results are indicated in italic
compared to the BKV. Finally, to verify whether there exists a significant
difference between our best results ($f_{best}$) and the BKV, we provide in the
last row the p-values ($\in [0, 1]$) from the non-parametric Friedman test, where
a p-value less than 0.05 means a significant difference between the compared
results. This test was also performed to compare the results of the Almha
algorithm and our average results ($f_{avg}$) $^4$.

Table 2 shows that our TSTS algorithm matches the best known results for 47 out of 48 instances, and improves the best known result for the remaining one instance, leading to an improved *Avg.* value compared to the averaged *BKV* (18108.96 vs. 18108.10). When comparing the average objective values *f*<sub>avg</sub> of our TSTS algorithm with the results of the Almba algorithm, one can find that both algorithms have a very similar performance, which is confirmed by a large *p*-value of 0.87. In addition, regarding the average results over all instances (*Avg.*), the value of *f*<sub>avg</sub> of our TSTS algorithm is 18088.27, which is slightly better than that of Almba (i.e., 18083.17). These outcomes show that our TSTS algorithm performs similarly on these small instances *n* = 100 compared to the state-of-the-art Almba algorithm.

The second experiment aims to evaluate our TSTS algorithm on the set of 48
larger instances with *n* = 250, and the computational results are summarized
in Table 3, where we report the same statistics as in Table 2. We observe
from Table 3 that our algorithm matches the best known results for 18 out
of 48 instances, improves the best known results for 12 instances, and misses
the best known results for the remaining 18 instances. In terms of *Avg.*, the
value of *f*<sub>best</sub> of TSTS is slightly worse than the value of *BKV* (i.e., 49821.10
vs. 49836.48), and slightly better than the result of Almha (i.e., 49821.10 vs.
49717.81), which is however slightly better than the value of *f*<sub>avg</sub> of TSTS (i.e.,
49687.60 vs. 49717.81). This experiment indicates that under the short time
limit *t*<sub>max</sub> = 60 seconds, TSTS performs globally well on these larger instance
with *n* = 250 especially by finding 12 improved best solutions. Additionally, we
observe from Table 3 that TSTS performs particularly well for instances with

<footnote n="4">⁴ Since the results of Almha are based on only one run, we mainly use our average
results for this comparison.</footnote>
a large number of constraints and achieves a better result than Almha for most
of the 12 instances with 10 demand constraints and 10 knapsack constraints.
Finally, we mention that the results of TSTS can be further improved by
increasing the time limit (see the detailed results in the Appendix), implying
that the current time limit ($t_{max}$ = 60) is too short for the TSTS algorithm
on these instances.

# 4 Analysis and Discussions

To shed light on the functioning of the proposed algorithm, we now analyze
and discuss several essential components of the TSTS algorithm.

## 4.1 *Effectiveness and Robustness Analysis for Two-Stage Strategy*

To study the effectiveness of the underlying two-stage search strategy, we
summarize in Table 4 the computational results about the *k* values returned
by the TSTS algorithm, where the results are based on the experiments in
Section 3.3 and the value of *k* represents the number of selected items in
the solution found. It is worth noting that the purpose of the first search
stage is just to discover a promising hyperplane Ω[*k*] that contains high quality
solutions, and the second search stage aims to locate improved solutions in
the given hyperplane. Hence, the two-stage search strategy can be considered
to be relevant and robust if the first search stage is able to reach very stably
the identical or close hyperplane to the best known solution (i.e., Ω[*k*<sub>best</sub>]).

The results of small instances with *n* = 100 are reported in the first 4 columns
of Table 4, including the name of instances, the *k* value of the best solution
obtained over 30 runs (*k*<sub>best</sub>), the average *k* value of solutions obtained, and the
standard deviation of *k* values obtained (*σ*<sub>*k*</sub>). The results of larger instances
with *n* = 250 are reported in columns 5–8, with the same statistics as in
columns 1–4. In addition, the row *Avg.* shows the average results of standard
deviations *σ*<sub>*k*</sub> of *k* values over all tested instances of each test set.

Table 4 shows that the value of *k*<sub>avg</sub> is very close to that of *k*<sub>best</sub> for most tested
instances, which means that the first search stage of the TSTS algorithm is
able to find a hyperplane that is very close to the best hyperplane containing
the current best known solution. On the other hand, we observe that the
standard deviations *σ*<sub>*k*</sub> of *k* values obtained are very small for most instances.
In particular, the average standard deviations of *k* values are respectively 0.22
and 0.66 for the set of small instances with *n* = 100 and the set of larger
instances with *n* = 250. Hence, this experiment confirms to some extend the
<table><caption>Table 4
Statistical results over 30 runs in terms of the number *k* of items in the obtained solutions.</caption><thead><tr><th colspan="4">n=100</th><th colspan="4">n=250</th></tr><tr><th>Instance</th><th>k<sub>best</sub></th><th>k<sub>avg</sub></th><th>σ<sub>k</sub></th><th>Instance</th><th>k<sub>best</sub></th><th>k<sub>avg</sub></th><th>σ<sub>k</sub></th></tr></thead><tbody><tr><td>100-5-2-0-0</td><td>30</td><td>29.97</td><td>0.30</td><td>250-5-2-0-0</td><td>79</td><td>78.47</td><td>0.85</td></tr><tr><td>100-5-2-0-1</td><td>31</td><td>31.00</td><td>0.34</td><td>250-5-2-0-1</td><td>78</td><td>76.00</td><td>0.89</td></tr><tr><td>100-5-2-0-2</td><td>31</td><td>30.83</td><td>0.34</td><td>250-5-2-0-2</td><td>78</td><td>77.03</td><td>1.08</td></tr><tr><td>100-5-2-0-3</td><td>32</td><td>31.83</td><td>0.42</td><td>250-5-2-0-3</td><td>79</td><td>79.07</td><td>0.44</td></tr><tr><td>100-5-2-0-4</td><td>31</td><td>31.00</td><td>0.00</td><td>250-5-2-0-4</td><td>79</td><td>78.33</td><td>0.54</td></tr><tr><td>100-5-2-0-5</td><td>56</td><td>55.83</td><td>0.40</td><td>250-5-2-0-5</td><td>137</td><td>134.87</td><td>1.50</td></tr><tr><td>100-5-2-1-0</td><td>28</td><td>27.00</td><td>0.30</td><td>250-5-2-1-0</td><td>71</td><td>70.03</td><td>0.66</td></tr><tr><td>100-5-2-1-1</td><td>29</td><td>29.00</td><td>0.00</td><td>250-5-2-1-1</td><td>69</td><td>69.23</td><td>0.67</td></tr><tr><td>100-5-2-1-2</td><td>27</td><td>27.27</td><td>0.34</td><td>250-5-2-1-2</td><td>72</td><td>72.07</td><td>0.63</td></tr><tr><td>100-5-2-1-3</td><td>29</td><td>29.00</td><td>0.00</td><td>250-5-2-1-3</td><td>69</td><td>68.57</td><td>0.72</td></tr><tr><td>100-5-2-1-4</td><td>29</td><td>28.17</td><td>0.44</td><td>250-5-2-1-4</td><td>70</td><td>70.67</td><td>0.83</td></tr><tr><td>100-5-2-1-5</td><td>54</td><td>53.00</td><td>0.31</td><td>250-5-2-1-5</td><td>129</td><td>127.70</td><td>1.07</td></tr><tr><td>100-5-5-0-0</td><td>28</td><td>28.40</td><td>0.46</td><td>250-5-5-0-0</td><td>76</td><td>75.50</td><td>0.50</td></tr><tr><td>100-5-5-0-1</td><td>30</td><td>30.00</td><td>0.00</td><td>250-5-5-0-1</td><td>74</td><td>71.87</td><td>1.02</td></tr><tr><td>100-5-5-0-2</td><td>30</td><td>30.00</td><td>0.00</td><td>250-5-5-0-2</td><td>74</td><td>74.37</td><td>0.55</td></tr><tr><td>100-5-5-0-3</td><td>30</td><td>30.00</td><td>0.00</td><td>250-5-5-0-3</td><td>76</td><td>75.40</td><td>0.66</td></tr><tr><td>100-5-5-0-4</td><td>29</td><td>29.00</td><td>0.00</td><td>250-5-5-0-4</td><td>76</td><td>76.00</td><td>0.26</td></tr><tr><td>100-5-5-0-5</td><td>54</td><td>54.00</td><td>0.18</td><td>250-5-5-0-5</td><td>136</td><td>134.60</td><td>0.80</td></tr><tr><td>100-5-5-1-0</td><td>27</td><td>26.73</td><td>0.48</td><td>250-5-5-1-0</td><td>68</td><td>66.90</td><td>0.65</td></tr><tr><td>100-5-5-1-1</td><td>28</td><td>28.00</td><td>0.00</td><td>250-5-5-1-1</td><td>66</td><td>65.40</td><td>0.55</td></tr><tr><td>100-5-5-1-2</td><td>27</td><td>27.37</td><td>0.47</td><td>250-5-5-1-2</td><td>65</td><td>65.53</td><td>0.62</td></tr><tr><td>100-5-5-1-3</td><td>28</td><td>27.93</td><td>0.34</td><td>250-5-5-1-3</td><td>65</td><td>65.80</td><td>0.65</td></tr><tr><td>100-5-5-1-4</td><td>27</td><td>27.07</td><td>0.18</td><td>250-5-5-1-4</td><td>66</td><td>66.90</td><td>0.60</td></tr><tr><td>100-5-5-1-5</td><td>52</td><td>52.00</td><td>0.00</td><td>250-5-5-1-5</td><td>126</td><td>126.23</td><td>0.80</td></tr><tr><td>100-10-5-0-0</td><td>28</td><td>28.00</td><td>0.00</td><td>250-10-5-0-0</td><td>69</td><td>67.20</td><td>1.05</td></tr><tr><td>100-10-5-0-1</td><td>28</td><td>27.40</td><td>0.50</td><td>250-10-5-0-1</td><td>71</td><td>71.07</td><td>0.44</td></tr><tr><td>100-10-5-0-2</td><td>27</td><td>26.97</td><td>0.00</td><td>250-10-5-0-2</td><td>70</td><td>69.23</td><td>0.56</td></tr><tr><td>100-10-5-0-3</td><td>28</td><td>27.43</td><td>0.42</td><td>250-10-5-0-3</td><td>68</td><td>67.33</td><td>0.94</td></tr><tr><td>100-10-5-0-4</td><td>28</td><td>27.07</td><td>0.25</td><td>250-10-5-0-4</td><td>69</td><td>67.53</td><td>0.96</td></tr><tr><td>100-10-5-0-5</td><td>53</td><td>52.60</td><td>0.47</td><td>250-10-5-0-5</td><td>130</td><td>128.93</td><td>0.81</td></tr><tr><td>100-10-5-1-0</td><td>26</td><td>26.00</td><td>0.18</td><td>250-10-5-1-0</td><td>65</td><td>65.13</td><td>0.62</td></tr><tr><td>100-10-5-1-1</td><td>26</td><td>26.03</td><td>0.00</td><td>250-10-5-1-1</td><td>67</td><td>66.73</td><td>0.63</td></tr><tr><td>100-10-5-1-2</td><td>26</td><td>26.03</td><td>0.25</td><td>250-10-5-1-2</td><td>65</td><td>63.97</td><td>0.71</td></tr><tr><td>100-10-5-1-3</td><td>26</td><td>26.13</td><td>0.30</td><td>250-10-5-1-3</td><td>65</td><td>65.03</td><td>0.60</td></tr><tr><td>100-10-5-1-4</td><td>27</td><td>26.47</td><td>0.50</td><td>250-10-5-1-4</td><td>66</td><td>65.43</td><td>0.50</td></tr><tr><td>100-10-5-1-5</td><td>51</td><td>50.93</td><td>0.18</td><td>250-10-5-1-5</td><td>128</td><td>127.20</td><td>0.40</td></tr><tr><td>100-10-10-0-0</td><td>28</td><td>28.00</td><td>0.00</td><td>250-10-10-0-0</td><td>68</td><td>66.83</td><td>0.58</td></tr><tr><td>100-10-10-0-1</td><td>27</td><td>27.00</td><td>0.00</td><td>250-10-10-0-1</td><td>68</td><td>68.47</td><td>0.56</td></tr><tr><td>100-10-10-0-2</td><td>27</td><td>27.00</td><td>0.00</td><td>250-10-10-0-2</td><td>67</td><td>66.70</td><td>0.64</td></tr><tr><td>100-10-10-0-3</td><td>27</td><td>27.00</td><td>0.26</td><td>250-10-10-0-3</td><td>68</td><td>67.30</td><td>0.59</td></tr><tr><td>100-10-10-0-4</td><td>28</td><td>27.30</td><td>0.45</td><td>250-10-10-0-4</td><td>67</td><td>66.13</td><td>0.56</td></tr><tr><td>100-10-10-0-5</td><td>53</td><td>52.97</td><td>0.00</td><td>250-10-10-0-5</td><td>130</td><td>129.53</td><td>0.56</td></tr><tr><td>100-10-10-1-0</td><td>24</td><td>24.77</td><td>0.42</td><td>250-10-10-1-0</td><td>64</td><td>63.70</td><td>0.46</td></tr><tr><td>100-10-10-1-1</td><td>25</td><td>25.03</td><td>0.00</td><td>250-10-10-1-1</td><td>63</td><td>63.03</td><td>0.18</td></tr><tr><td>100-10-10-1-2</td><td>26</td><td>26.00</td><td>0.00</td><td>250-10-10-1-2</td><td>64</td><td>63.63</td><td>0.48</td></tr><tr><td>100-10-10-1-3</td><td>25</td><td>25.03</td><td>0.37</td><td>250-10-10-1-3</td><td>63</td><td>63.40</td><td>0.49</td></tr><tr><td>100-10-10-1-4</td><td>25</td><td>25.17</td><td>0.30</td><td>250-10-10-1-4</td><td>65</td><td>64.00</td><td>0.37</td></tr><tr><td>100-10-10-1-5</td><td>50</td><td>49.83</td><td>0.30</td><td>250-10-10-1-5</td><td>123</td><td>123.70</td><td>0.46</td></tr><tr><td>Avg.</td><td></td><td></td><td>0.22</td><td></td><td></td><td></td><td>0.66</td></tr></tbody></table>
effectiveness and robustness of the two-stage search strategy employed by the TSTS algorithm.

## 4.2 Effects of Two Stages on the Performance of Algorithm

<caption>Table 5</caption>

Comparison between the two search stages on the instances with $n = 250$.

<table><thead><tr><th>Instance</th><th>f<sub>1</sub></th><th>t<sub>1</sub>(s)</th><th>f<sub>2</sub></th><th>t<sub>2</sub>(s)</th><th>f<sub>2</sub> - f<sub>1</sub></th><th>ρ</th></tr></thead><tbody><tr><td>250-5-2-0-0</td><td>78029.83</td><td>9.60</td><td>78289.00</td><td>31.53</td><td>259.17</td><td>0.33</td></tr><tr><td>250-5-2-0-1</td><td>74599.40</td><td>11.44</td><td>74833.33</td><td>25.52</td><td>233.93</td><td>0.31</td></tr><tr><td>250-5-2-0-2</td><td>70402.30</td><td>13.79</td><td>70674.93</td><td>34.09</td><td>272.63</td><td>0.39</td></tr><tr><td>250-5-2-0-3</td><td>79927.80</td><td>4.89</td><td>80206.57</td><td>32.33</td><td>278.77</td><td>0.35</td></tr><tr><td>250-5-2-0-4</td><td>70555.47</td><td>2.91</td><td>70834.30</td><td>24.41</td><td>278.83</td><td>0.40</td></tr><tr><td>250-5-2-0-5</td><td>128985.57</td><td>11.40</td><td>129271.40</td><td>28.83</td><td>285.83</td><td>0.22</td></tr><tr><td>250-5-2-1-0</td><td>26322.20</td><td>3.98</td><td>26573.83</td><td>37.52</td><td>251.63</td><td>0.96</td></tr><tr><td>250-5-2-1-1</td><td>26522.33</td><td>4.43</td><td>26806.77</td><td>30.21</td><td>284.43</td><td>1.07</td></tr><tr><td>250-5-2-1-2</td><td>26945.23</td><td>4.75</td><td>27235.83</td><td>31.91</td><td>290.60</td><td>1.08</td></tr><tr><td>250-5-2-1-3</td><td>25892.27</td><td>4.91</td><td>26173.90</td><td>38.03</td><td>281.63</td><td>1.09</td></tr><tr><td>250-5-2-1-4</td><td>26997.30</td><td>5.39</td><td>27204.13</td><td>39.99</td><td>206.83</td><td>0.77</td></tr><tr><td>250-5-2-1-5</td><td>44068.70</td><td>5.99</td><td>44302.57</td><td>28.11</td><td>233.87</td><td>0.53</td></tr><tr><td>250-5-5-0-0</td><td>67902.80</td><td>7.89</td><td>68017.03</td><td>10.63</td><td>114.23</td><td>0.17</td></tr><tr><td>250-5-5-0-1</td><td>60341.40</td><td>7.58</td><td>60627.90</td><td>37.09</td><td>286.50</td><td>0.47</td></tr><tr><td>250-5-5-0-2</td><td>61948.87</td><td>5.17</td><td>62072.57</td><td>16.03</td><td>123.70</td><td>0.20</td></tr><tr><td>250-5-5-0-3</td><td>66363.73</td><td>7.16</td><td>66519.80</td><td>16.84</td><td>156.07</td><td>0.24</td></tr><tr><td>250-5-5-0-4</td><td>61803.67</td><td>3.57</td><td>61925.90</td><td>4.69</td><td>122.23</td><td>0.20</td></tr><tr><td>250-5-5-0-5</td><td>127473.87</td><td>10.57</td><td>127708.10</td><td>26.23</td><td>234.23</td><td>0.18</td></tr><tr><td>250-5-5-1-0</td><td>26574.67</td><td>2.38</td><td>26918.43</td><td>35.36</td><td>343.77</td><td>1.29</td></tr><tr><td>250-5-5-1-1</td><td>26197.30</td><td>2.56</td><td>26576.10</td><td>26.45</td><td>378.80</td><td>1.45</td></tr><tr><td>250-5-5-1-2</td><td>26129.73</td><td>3.26</td><td>26556.97</td><td>34.95</td><td>427.23</td><td>1.64</td></tr><tr><td>250-5-5-1-3</td><td>25386.40</td><td>2.84</td><td>25784.30</td><td>34.02</td><td>397.90</td><td>1.57</td></tr><tr><td>250-5-5-1-4</td><td>25586.80</td><td>2.34</td><td>25992.03</td><td>31.64</td><td>405.23</td><td>1.58</td></tr><tr><td>250-5-5-1-5</td><td>40721.77</td><td>4.86</td><td>41237.67</td><td>37.49</td><td>515.90</td><td>1.27</td></tr><tr><td>250-10-5-0-0</td><td>55376.00</td><td>10.35</td><td>55900.43</td><td>31.43</td><td>524.43</td><td>0.95</td></tr><tr><td>250-10-5-0-1</td><td>59234.87</td><td>7.83</td><td>59551.47</td><td>37.65</td><td>316.60</td><td>0.53</td></tr><tr><td>250-10-5-0-2</td><td>54262.60</td><td>8.68</td><td>54657.33</td><td>35.68</td><td>394.73</td><td>0.73</td></tr><tr><td>250-10-5-0-3</td><td>51626.67</td><td>9.97</td><td>52105.73</td><td>34.57</td><td>479.07</td><td>0.93</td></tr><tr><td>250-10-5-0-4</td><td>57155.03</td><td>8.66</td><td>57750.73</td><td>36.08</td><td>595.70</td><td>1.04</td></tr><tr><td>250-10-5-0-5</td><td>98688.90</td><td>13.45</td><td>99201.73</td><td>34.25</td><td>512.83</td><td>0.52</td></tr><tr><td>250-10-5-1-0</td><td>26410.57</td><td>5.71</td><td>26866.77</td><td>34.05</td><td>456.20</td><td>1.73</td></tr><tr><td>250-10-5-1-1</td><td>26189.03</td><td>4.29</td><td>26538.87</td><td>33.99</td><td>349.83</td><td>1.34</td></tr><tr><td>250-10-5-1-2</td><td>25149.17</td><td>5.15</td><td>25598.13</td><td>35.00</td><td>448.97</td><td>1.79</td></tr><tr><td>250-10-5-1-3</td><td>26671.27</td><td>3.54</td><td>27089.60</td><td>38.49</td><td>418.33</td><td>1.57</td></tr><tr><td>250-10-5-1-4</td><td>26317.50</td><td>5.12</td><td>26729.87</td><td>34.43</td><td>412.37</td><td>1.57</td></tr><tr><td>250-10-5-1-5</td><td>45787.90</td><td>6.45</td><td>46145.40</td><td>31.66</td><td>357.50</td><td>0.78</td></tr><tr><td>250-10-10-0-0</td><td>51902.63</td><td>8.52</td><td>52326.03</td><td>36.24</td><td>423.40</td><td>0.82</td></tr><tr><td>250-10-10-0-1</td><td>53349.40</td><td>4.96</td><td>53663.80</td><td>33.53</td><td>314.40</td><td>0.59</td></tr><tr><td>250-10-10-0-2</td><td>46352.07</td><td>7.58</td><td>46770.97</td><td>38.03</td><td>418.90</td><td>0.90</td></tr><tr><td>250-10-10-0-3</td><td>54397.33</td><td>9.80</td><td>54745.93</td><td>25.69</td><td>348.60</td><td>0.64</td></tr><tr><td>250-10-10-0-4</td><td>49214.60</td><td>5.47</td><td>49575.43</td><td>44.01</td><td>360.83</td><td>0.73</td></tr><tr><td>250-10-10-0-5</td><td>92424.20</td><td>9.18</td><td>92821.53</td><td>35.22</td><td>397.33</td><td>0.43</td></tr><tr><td>250-10-10-1-0</td><td>26297.53</td><td>4.05</td><td>26667.67</td><td>28.92</td><td>370.13</td><td>1.41</td></tr><tr><td>250-10-10-1-1</td><td>25386.40</td><td>4.20</td><td>25786.43</td><td>35.09</td><td>400.03</td><td>1.58</td></tr><tr><td>250-10-10-1-2</td><td>25963.63</td><td>5.58</td><td>26470.70</td><td>21.09</td><td>507.07</td><td>1.95</td></tr><tr><td>250-10-10-1-3</td><td>25996.40</td><td>5.25</td><td>26614.77</td><td>27.03</td><td>618.37</td><td>2.38</td></tr><tr><td>250-10-10-1-4</td><td>26132.07</td><td>2.62</td><td>26617.33</td><td>39.61</td><td>485.27</td><td>1.86</td></tr><tr><td>250-10-10-1-5</td><td>41890.40</td><td>9.74</td><td>42464.80</td><td>32.11</td><td>574.40</td><td>1.37</td></tr><tr><td>Avg.</td><td>49330.32</td><td>6.45</td><td>49687.60</td><td>31.41</td><td>357.28</td><td>0.96</td></tr></tbody></table>

To investigate the respective role of the two stages of our algorithm, we carried
out an experiment based on the instances with $n = 250$. We ran our TSTS algorithm 30 times to solve each instance according to the experimental protocol of Section 3.2. The average results from the first stage and the second stage over 30 independent runs are summarized in Table 5. The first column gives the name of instances, columns 2 and 3 show the objective value ($f_1$) obtained by the first stage and computation time ($t_1$) in seconds needed to reach $f_1$. Columns 4 and 5 show the objective value ($f_2$) obtained by the second stage and the computation time ($t_2$) needed to reach $f_2$ from $f_1$. The last two columns indicate the gap between $f_2$ and $f_1$ and the improvement ratio ($\rho$) of $f_2$ over $f_1$, which is calculated as $\rho = 100 \times (f_2 - f_1)/f_1$.

We observe from Table 5 that the first search stage of the TSTS algorithm is able to obtain a high-quality feasible solution for each instance and the solutions obtained in the first stage can be further improved during the second search stage. Furthermore, the improvements of $f_2$ over $f_1$ are significant with an average improvement ratio $\rho$ close to 1%. On the other hand, regarding the computation times needed by the two search stages, we observe that most computational efforts are required by the second search stage and that $t_2$ is about five times larger than $t_1$. Of course, this proportion depends also on the setting of the parameters $\alpha$ and $t_{max}$. These outcomes indicate that both search stages of the TSTS algorithm are indispensable for the high performance of the algorithm. The first search stage is able to generate high-quality feasible solutions while the second search stage is able to further improve the solutions by performing an intensified search in the reached hyperplane.

## 4.3 Sensitivity Analysis of Hash functions

Now, we investigate the impacts of hash functions on the performance of the algorithm and discuss the sensitivity of the associated parameters. For this purpose, we carried out an additional experiment based on 30 representative instances in terms of the numbers of knapsack and demand constraints. We ran our TSTS algorithm 30 times for each instance and each parameter combination of ($\gamma_1, \gamma_2, \gamma_3$), where $\gamma_i$ ($i = 1, 2, 3$) are the parameters used to define the hash functions $h_i$ (see Section 2.3.2 for details). Specifically, we tested 10 different settings, i.e., ($\gamma_1, \gamma_2, \gamma_3) \in \{(1.1, 1.5, 1.8), (1.3, 1.5, 1.8), (1.3, 1.5, 2.0), (1.5, 2.0, 2.5), (1.6, 1.8, 2.0), (1.6, 1.8, 2.5), (1.8, 2.0, 2.2), (1.8, 2.0, 2.5), (1.9, 2.1, 2.3), (2.0, 2.2, 2.5)\}$.

The experimental results are summarized in Table 6, where the first column gives the name of instances, the second row shows the settings of parameters, and the average objective values ($f_{avg}$) obtained over 30 runs are reported in columns 2–11 for each parameter combination and each instance, respectively. In addition, the rows \#Best and Avg. of the table indicate respectively the
<table><caption>Table 6. Influence of the hash functions on the performance of algorithm. Each instance was independently solved 30 times for each parameter combination, and the average objective values ($f_{avg}$) over 30 runs are reported.</caption><thead><tr><th rowspan="2">Instance/(71, 72, 73)</th><th colspan="12">f<sub>avg</sub></th></tr><tr><th>(1, 1, 1, 5, 1, 8)</th><th>(1, 3, 1, 5, 1, 8)</th><th>(1, 3, 1, 5, 2, 0)</th><th>(1, 5, 2, 0, 2, 5)</th><th>(1, 6, 1, 8, 2, 0)</th><th>(1, 6, 1, 8, 2, 5)</th><th>(1, 8, 2, 0, 2, 2)</th><th>(1, 8, 2, 0, 2, 5)</th><th>(1, 9, 2, 1, 2, 3)</th><th>(2, 0, 2, 2, 5)</th></tr></thead><tbody><tr><td>250-5-2-0-0</td><td>78221.23</td><td>78257.70</td><td>78340.20</td><td>78306.50</td><td>78222.97</td><td>78259.90</td><td><strong>78330.10</strong></td><td>78249.13</td><td>78271.70</td><td>78314.23</td></tr><tr><td>250-5-2-0-1</td><td>74711.67</td><td>74823.20</td><td>74810.57</td><td>74820.77</td><td>74749.43</td><td>74719.00</td><td>74796.47</td><td>74871.30</td><td><strong>74881.40</strong></td><td>74763.97</td></tr><tr><td>250-5-2-0-2</td><td>70668.73</td><td>70612.37</td><td>70589.13</td><td>70717.43</td><td>70522.20</td><td><strong>70733.50</strong></td><td>70683.43</td><td>70687.33</td><td>70615.77</td><td>70682.90</td></tr><tr><td>250-5-2-0-3</td><td>80152.93</td><td>80150.67</td><td>80179.63</td><td>80177.47</td><td>80192.50</td><td><strong>80205.67</strong></td><td>80200.03</td><td>80196.33</td><td>80182.67</td><td>80184.60</td></tr><tr><td>250-5-2-0-4</td><td>70805.20</td><td>70802.13</td><td>70828.47</td><td>70808.83</td><td>70827.30</td><td>70825.47</td><td>70836.80</td><td>70838.90</td><td><strong>70854.17</strong></td><td>70823.17</td></tr><tr><td>250-5-2-0-5</td><td>129152.17</td><td>129156.73</td><td>129101.97</td><td>128934.40</td><td>129141.57</td><td>129022.13</td><td>128910.60</td><td>129028.70</td><td>129205.90</td><td><strong>129245.57</strong></td></tr><tr><td>250-5-2-1-0</td><td>26544.90</td><td>26531.37</td><td>26547.13</td><td>26577.33</td><td>26561.60</td><td>26566.57</td><td><strong>26592.30</strong></td><td>26579.20</td><td>26576.87</td><td>26557.97</td></tr><tr><td>250-5-2-1-1</td><td>26744.33</td><td>26750.03</td><td>26764.23</td><td>26802.10</td><td>26789.80</td><td>26803.20</td><td>26794.60</td><td><strong>26817.83</strong></td><td>26812.87</td><td>26817.20</td></tr><tr><td>250-5-2-1-3</td><td>26125.63</td><td>26122.33</td><td>26143.10</td><td>26161.43</td><td>26154.03</td><td>26170.10</td><td><strong>26185.47</strong></td><td>26183.40</td><td>26185.40</td><td>26165.03</td></tr><tr><td>250-5-2-1-4</td><td>27164.03</td><td>27166.27</td><td>27185.90</td><td>27202.93</td><td>27206.27</td><td>27204.73</td><td><strong>27212.97</strong></td><td>27205.23</td><td>27208.03</td><td>27195.53</td></tr><tr><td>250-5-2-1-5</td><td>44252.07</td><td>44267.73</td><td>44284.83</td><td>44291.53</td><td>44277.13</td><td>44283.07</td><td>44300.17</td><td>44280.53</td><td><strong>44306.17</strong></td><td>44285.67</td></tr><tr><td>250-5-5-0-4</td><td>61911.17</td><td>61910.40</td><td>61914.80</td><td>61923.10</td><td>61918.37</td><td>61914.87</td><td><strong>61926.20</strong></td><td>61925.53</td><td>61920.00</td><td>61917.20</td></tr><tr><td>250-5-5-0-5</td><td>127545.60</td><td>127622.33</td><td>127673.70</td><td><strong>127740.23</strong></td><td>127643.83</td><td>127600.00</td><td>127718.67</td><td>127526.43</td><td>127618.57</td><td>127649.40</td></tr><tr><td>250-5-5-1-0</td><td>26870.87</td><td>26871.23</td><td>26878.20</td><td>26908.63</td><td>26898.83</td><td>26900.03</td><td><strong>26910.93</strong></td><td>26902.07</td><td>26908.87</td><td>26907.33</td></tr><tr><td>250-5-5-1-1</td><td>26527.90</td><td>26560.83</td><td>26570.03</td><td>26586.57</td><td>26575.47</td><td>26564.93</td><td><strong>26598.27</strong></td><td>26576.53</td><td>26593.87</td><td>26586.77</td></tr><tr><td>250-10-5-0-0</td><td>55855.80</td><td>55907.33</td><td>55882.50</td><td><strong>55930.33</strong></td><td>55907.27</td><td>55898.90</td><td>55888.23</td><td>55913.90</td><td>55843.83</td><td>55904.90</td></tr><tr><td>250-10-5-0-1</td><td>59484.63</td><td>59488.40</td><td>59496.33</td><td>59513.67</td><td>59533.07</td><td>59527.07</td><td>59534.97</td><td>59534.17</td><td><strong>59558.07</strong></td><td>59500.83</td></tr><tr><td>250-10-5-0-2</td><td>54558.87</td><td>54542.57</td><td>54553.77</td><td>54639.63</td><td>54603.23</td><td>54642.97</td><td><strong>54670.97</strong></td><td>54545.70</td><td>54586.17</td><td>54602.53</td></tr><tr><td>250-10-5-0-3</td><td>52070.43</td><td>52009.47</td><td>52082.17</td><td>52112.63</td><td>52065.67</td><td>52043.67</td><td><strong>52113.03</strong></td><td>52089.00</td><td>52082.63</td><td>52111.47</td></tr><tr><td>250-10-5-1-2</td><td>25530.00</td><td>25515.17</td><td>25562.50</td><td>25589.87</td><td>25567.83</td><td>25591.30</td><td><strong>25614.03</strong></td><td>25586.77</td><td>25594.57</td><td>25579.17</td></tr><tr><td>250-10-5-1-3</td><td>27024.40</td><td>26999.23</td><td>27057.57</td><td><strong>27082.40</strong></td><td>27068.90</td><td>27042.27</td><td>27078.20</td><td>27081.83</td><td>27080.10</td><td>27066.00</td></tr><tr><td>250-10-5-1-4</td><td>26675.00</td><td>26694.23</td><td>26718.73</td><td>26740.40</td><td>26717.37</td><td>26722.43</td><td>26725.93</td><td>26741.33</td><td>26715.90</td><td><strong>26758.10</strong></td></tr><tr><td>250-10-5-1-5</td><td>46090.07</td><td>46094.93</td><td>46122.93</td><td>46145.23</td><td>46123.77</td><td>46137.63</td><td>46129.57</td><td>46132.30</td><td><strong>46154.63</strong></td><td>46138.30</td></tr><tr><td>250-10-10-0-4</td><td>49488.50</td><td>49538.87</td><td>49524.60</td><td>49565.67</td><td>49525.07</td><td>49564.53</td><td>49548.50</td><td>49551.30</td><td><strong>49577.33</strong></td><td>49555.60</td></tr><tr><td>250-10-10-0-5</td><td>92757.03</td><td>92789.73</td><td>92795.13</td><td>92798.97</td><td>92813.90</td><td>92800.37</td><td>92831.43</td><td>92757.33</td><td><strong>92833.17</strong></td><td>92812.40</td></tr><tr><td>250-10-10-1-0</td><td>26610.33</td><td>26624.83</td><td>26645.80</td><td>26656.13</td><td>26656.17</td><td>26645.97</td><td>26654.03</td><td>26666.30</td><td><strong>26668.73</strong></td><td>26642.87</td></tr><tr><td>250-10-10-1-1</td><td>25727.50</td><td>25736.73</td><td>25758.33</td><td>25772.73</td><td>25754.33</td><td>25773.77</td><td>25772.23</td><td>25765.07</td><td><strong>25781.70</strong></td><td>25776.60</td></tr><tr><td>250-10-10-1-2</td><td>26439.20</td><td>26427.07</td><td>26461.90</td><td>26469.03</td><td>26463.20</td><td>26469.17</td><td>26463.10</td><td>26470.77</td><td>26464.57</td><td><strong>26473.93</strong></td></tr><tr><td>250-10-10-1-4</td><td>26546.37</td><td>26563.37</td><td>26572.87</td><td>26592.53</td><td>26590.93</td><td><strong>26602.63</strong></td><td>26598.90</td><td>26589.47</td><td>26600.03</td><td>26600.33</td></tr><tr><td>250-10-10-1-5</td><td>42384.30</td><td>42377.87</td><td>42418.47</td><td>42450.73</td><td>42431.67</td><td>42462.73</td><td>42438.90</td><td><strong>42472.50</strong></td><td>42435.53</td><td>42441.17</td></tr><tr><td>Avg.</td><td>51154.70</td><td>51163.84</td><td>51178.85</td><td>51200.64</td><td>51183.46</td><td>51190.02</td><td>51201.97</td><td>51192.14</td><td><strong>51204.64</strong></td><td>51202.02</td></tr><tr><td>#Best</td><td>0</td><td>0</td><td>0</td><td>3</td><td>0</td><td>0</td><td>10</td><td>2</td><td><strong>9</strong></td><td>3</td></tr></tbody></table>
number of instances for which the associated setting of parameters yielded the best results and the average results over all instances tested.

We observe from Table 6 that the algorithm is sensitive to the setting of the parameters $\gamma_1, \gamma_2$, and $\gamma_3$. For the parameter combinations containing two small parameter values, the TSTS algorithm performed badly. For example, the algorithm with the combination (1.1, 1.5, 1.8) yielded the worst results in terms of Avg. However, when all parameters in ($\gamma_1, \gamma_2, \gamma_3$) take a relatively large value, the algorithm obtained a much better performance. Taking (1.9, 2.1, 2.3) as an example, the algorithm achieved the best results on 9 instances. In summary, the parameters $\gamma_1, \gamma_2$, and $\gamma_3$ have an important impact on the performance of the algorithm, and parameter combinations containing at least two large parameter values lead usually to a good performance of the algorithm.

### 4.4 Effectiveness of Solution-based Tabu Strategy

The solution-based tabu strategy is an essential ingredient of our TSTS algorithm. To show its effectiveness with respect to the popular attribute-based tabu strategy, we created a variant A-TSTS of the TSTS algorithm by replacing the solution-based tabu strategy with the popular attribute-based tabu strategy, while keeping the other TSTS components unchanged. In A-TSTS, the adopted tabu strategy can be simply described as follows. Given an incumbent solution $s = (x_1, x_2, \dots, x_n)$, once a 0-1 variable $x_i$ ($1 \le i \le n$) is flipped as $x_i \leftarrow 1 - x_i$, $x_i$ is forbidden to be flipped again for the next *tt* iterations (*tt* is the tabu tenure) and the associated neighbor solutions are excluded for consideration during the period identified by the tabu tenure. We empirically set $tt = C + rand[0, 2]$ where *C* is a parameter that takes the value of 20 and *rand[0, 2]* is a random integer in [0, 2]. Finally, the tabu status of a variable is disabled if flipping the variable leads to a solution better than all previously visited solutions (this is the so-called aspiration criterion).

To compare TSTS and A-TSTS, we carried out an experiment based on the set of 48 large instances with *n* = 250, where both algorithms were run 30 times according to the experimental protocol given in Section 3.2. The computational results are summarized in Table 7 where we show for each algorithm the best results ($f_{best}$) obtained over 30 runs, the average results ($f_{avg}$), and the worst results obtained ($f_{worst}$). In addition, the row 'Avg.' shows the average results for each performance indicator. Finally, to check whether there exists a significant difference between the two algorithms in terms of $f_{best}$, $f_{avg}$ and $f_{worst}$, we provide the *p*-values from the non-parametric Friedman test in the last row, where a *p*-value smaller than 0.05 implies a significant difference between the compared results.
<caption>Table 7</caption>

Comparison between the solution-based and attribute-based tabu strategies on the instances with n = 250. The better results between the two algorithms are indicated in bold in terms of fbest, favg and fworst.

<table><thead><tr><th rowspan="2">Instance</th><th colspan="2">fbest</th><th colspan="2">favg</th><th colspan="2">fworst</th></tr><tr><th>A-TSTS</th><th>TSTS</th><th>A-TSTS</th><th>TSTS</th><th>A-TSTS</th><th>TSTS</th></tr></thead><tbody><tr><td>250-5-2-0-0</td><td>72278</td><td><strong>78486</strong></td><td>69459.47</td><td><strong>78289.00</strong></td><td>66794</td><td><strong>77644</strong></td></tr><tr><td>250-5-2-0-1</td><td>68945</td><td><strong>75132</strong></td><td>65578.57</td><td><strong>74833.33</strong></td><td>62546</td><td><strong>73702</strong></td></tr><tr><td>250-5-2-0-2</td><td>65744</td><td><strong>70898</strong></td><td>62624.13</td><td><strong>70674.93</strong></td><td>60403</td><td><strong>69762</strong></td></tr><tr><td>250-5-2-0-3</td><td>75654</td><td><strong>80311</strong></td><td>71754.33</td><td><strong>80206.57</strong></td><td>69139</td><td><strong>80065</strong></td></tr><tr><td>250-5-2-0-4</td><td>66935</td><td><strong>70935</strong></td><td>63119.17</td><td><strong>70834.30</strong></td><td>60155</td><td><strong>70583</strong></td></tr><tr><td>250-5-2-0-5</td><td>125571</td><td><strong>130191</strong></td><td>122346.53</td><td><strong>129271.40</strong></td><td>118507</td><td><strong>127061</strong></td></tr><tr><td>250-5-2-1-0</td><td>25126</td><td><strong>26666</strong></td><td>23250.10</td><td><strong>26573.83</strong></td><td>20310</td><td><strong>26457</strong></td></tr><tr><td>250-5-2-1-1</td><td>25352</td><td><strong>26864</strong></td><td>23872.30</td><td><strong>26806.77</strong></td><td>22806</td><td><strong>26690</strong></td></tr><tr><td>250-5-2-1-2</td><td>25204</td><td><strong>27280</strong></td><td>23651.70</td><td><strong>27235.83</strong></td><td>21274</td><td><strong>27109</strong></td></tr><tr><td>250-5-2-1-3</td><td>24796</td><td><strong>26250</strong></td><td>23342.57</td><td><strong>26173.90</strong></td><td>21765</td><td><strong>26098</strong></td></tr><tr><td>250-5-2-1-4</td><td>25474</td><td><strong>27287</strong></td><td>24349.20</td><td><strong>27204.13</strong></td><td>22944</td><td><strong>27131</strong></td></tr><tr><td>250-5-2-1-5</td><td>42388</td><td><strong>44395</strong></td><td>40612.43</td><td><strong>44302.57</strong></td><td>37348</td><td><strong>44163</strong></td></tr><tr><td>250-5-5-0-0</td><td>64755</td><td><strong>68026</strong></td><td>62158.80</td><td><strong>68017.03</strong></td><td>58973</td><td><strong>67978</strong></td></tr><tr><td>250-5-5-0-1</td><td>58390</td><td><strong>60766</strong></td><td>56174.20</td><td><strong>60627.90</strong></td><td>53842</td><td><strong>60258</strong></td></tr><tr><td>250-5-5-0-2</td><td>59571</td><td><strong>62093</strong></td><td>57389.37</td><td><strong>62072.57</strong></td><td>53856</td><td><strong>61960</strong></td></tr><tr><td>250-5-5-0-3</td><td>64279</td><td><strong>66567</strong></td><td>61548.97</td><td><strong>66519.80</strong></td><td>59335</td><td><strong>66384</strong></td></tr><tr><td>250-5-5-0-4</td><td>59003</td><td><strong>61929</strong></td><td>56954.03</td><td><strong>61925.90</strong></td><td>54735</td><td><strong>61878</strong></td></tr><tr><td>250-5-5-0-5</td><td>123840</td><td><strong>127922</strong></td><td>121678.73</td><td><strong>127708.10</strong></td><td>116272</td><td><strong>127211</strong></td></tr><tr><td>250-5-5-1-0</td><td>25188</td><td><strong>26973</strong></td><td>23643.70</td><td><strong>26918.43</strong></td><td>21024</td><td><strong>26853</strong></td></tr><tr><td>250-5-5-1-1</td><td>24472</td><td><strong>26665</strong></td><td>23106.03</td><td><strong>26576.10</strong></td><td>21433</td><td><strong>26462</strong></td></tr><tr><td>250-5-5-1-2</td><td>24316</td><td><strong>26648</strong></td><td>23054.23</td><td><strong>26556.97</strong></td><td>20703</td><td><strong>26403</strong></td></tr><tr><td>250-5-5-1-3</td><td>24165</td><td><strong>25885</strong></td><td>22694.20</td><td><strong>25784.30</strong></td><td>20186</td><td><strong>25695</strong></td></tr><tr><td>250-5-5-1-4</td><td>23813</td><td><strong>26060</strong></td><td>22712.63</td><td><strong>25992.03</strong></td><td>21016</td><td><strong>25882</strong></td></tr><tr><td>250-5-5-1-5</td><td>38977</td><td><strong>41338</strong></td><td>37637.83</td><td><strong>41237.67</strong></td><td>34688</td><td><strong>41104</strong></td></tr><tr><td>250-10-5-0-0</td><td>53124</td><td><strong>56260</strong></td><td>50822.33</td><td><strong>55900.43</strong></td><td>47977</td><td><strong>55344</strong></td></tr><tr><td>250-10-5-0-1</td><td>56060</td><td><strong>59619</strong></td><td>53640.83</td><td><strong>59551.47</strong></td><td>50706</td><td><strong>59330</strong></td></tr><tr><td>250-10-5-0-2</td><td>51944</td><td><strong>54890</strong></td><td>49772.90</td><td><strong>54657.33</strong></td><td>47349</td><td><strong>54367</strong></td></tr><tr><td>250-10-5-0-3</td><td>49409</td><td><strong>52249</strong></td><td>47341.53</td><td><strong>52105.73</strong></td><td>44605</td><td><strong>51588</strong></td></tr><tr><td>250-10-5-0-4</td><td>54681</td><td><strong>58119</strong></td><td>52606.43</td><td><strong>57750.73</strong></td><td>49637</td><td><strong>57113</strong></td></tr><tr><td>250-10-5-0-5</td><td>96521</td><td><strong>99512</strong></td><td>94044.77</td><td><strong>99201.73</strong></td><td>89840</td><td><strong>98604</strong></td></tr><tr><td>250-10-5-1-0</td><td>25431</td><td><strong>26961</strong></td><td>23844.97</td><td><strong>26866.77</strong></td><td>21589</td><td><strong>26716</strong></td></tr><tr><td>250-10-5-1-1</td><td>25399</td><td><strong>26658</strong></td><td>23638.70</td><td><strong>26538.87</strong></td><td>21920</td><td><strong>26390</strong></td></tr><tr><td>250-10-5-1-2</td><td>23836</td><td><strong>25737</strong></td><td>21624.83</td><td><strong>25598.13</strong></td><td>15478</td><td><strong>25322</strong></td></tr><tr><td>250-10-5-1-3</td><td>24940</td><td><strong>27159</strong></td><td>23633.13</td><td><strong>27089.60</strong></td><td>21621</td><td><strong>26952</strong></td></tr><tr><td>250-10-5-1-4</td><td>24819</td><td><strong>26815</strong></td><td>23390.37</td><td><strong>26729.87</strong></td><td>20190</td><td><strong>26635</strong></td></tr><tr><td>250-10-5-1-5</td><td>43814</td><td><strong>46244</strong></td><td>42276.70</td><td><strong>46145.40</strong></td><td>40483</td><td><strong>46112</strong></td></tr><tr><td>250-10-10-0-0</td><td>49931</td><td><strong>52407</strong></td><td>48520.97</td><td><strong>52326.03</strong></td><td>45896</td><td><strong>52045</strong></td></tr><tr><td>250-10-10-0-1</td><td>52102</td><td><strong>53745</strong></td><td>50398.53</td><td><strong>53663.80</strong></td><td>47944</td><td><strong>53493</strong></td></tr><tr><td>250-10-10-0-2</td><td>44797</td><td><strong>46927</strong></td><td>43186.07</td><td><strong>46770.97</strong></td><td>40408</td><td><strong>46487</strong></td></tr><tr><td>250-10-10-0-3</td><td>52271</td><td><strong>54831</strong></td><td>50908.37</td><td><strong>54745.93</strong></td><td>48603</td><td><strong>54441</strong></td></tr><tr><td>250-10-10-0-4</td><td>47965</td><td><strong>49660</strong></td><td>46648.33</td><td><strong>49575.43</strong></td><td>44642</td><td><strong>49327</strong></td></tr><tr><td>250-10-10-0-5</td><td>90501</td><td><strong>92975</strong></td><td>88609.13</td><td><strong>92821.53</strong></td><td>83712</td><td><strong>92473</strong></td></tr><tr><td>250-10-10-1-0</td><td>24671</td><td><strong>26696</strong></td><td>22845.10</td><td><strong>26667.67</strong></td><td>20131</td><td><strong>26564</strong></td></tr><tr><td>250-10-10-1-1</td><td>24350</td><td><strong>25876</strong></td><td>22838.50</td><td><strong>25786.43</strong></td><td>19149</td><td><strong>25721</strong></td></tr><tr><td>250-10-10-1-2</td><td>24341</td><td><strong>26517</strong></td><td>22613.70</td><td><strong>26470.70</strong></td><td>20116</td><td><strong>26418</strong></td></tr><tr><td>250-10-10-1-3</td><td>24577</td><td><strong>26684</strong></td><td>23209.00</td><td><strong>26614.77</strong></td><td>21611</td><td><strong>26518</strong></td></tr><tr><td>250-10-10-1-4</td><td>24679</td><td><strong>26676</strong></td><td>23352.07</td><td><strong>26617.33</strong></td><td>21524</td><td><strong>26511</strong></td></tr><tr><td>250-10-10-1-5</td><td>39576</td><td><strong>42629</strong></td><td>37427.70</td><td><strong>42464.80</strong></td><td>34366</td><td><strong>42376</strong></td></tr><tr><td>Avg.</td><td>47166.15</td><td><strong>49821.10</strong></td><td>45206.42</td><td><strong>49687.60</strong></td><td>42490.65</td><td><strong>49403.75</strong></td></tr><tr><td>p-value</td><td></td><td>4.26e-12</td><td></td><td>4.26e-12</td><td></td><td>4.26e-12</td></tr></tbody></table>
We observe from Table 7 that the solution-based algorithm TSTS dominates the attribute-based algorithm A-TSTS in terms of all indicators, by reporting better results in terms of $f_{best}$, $f_{avg}$ and $f_{worst}$ on all the instances. Furthermore, the small *p*-values indicate that the performance differences between the compared results are statistically significant. Therefore, this experiment confirms that under the two-stage framework of this work, the solution-based tabu strategy is much more suitable than the attribute-based tabu strategy for solving the MDMKP.

## 4.5 Discussion about the Solution-based and Attribute-based Tabu Search Approaches

Attribute-based tabu search is a popular approach, whose key idea is to prevent one attribute or a combination of several attributes of a solution from being changed during a number of iterations since their last changes. For such a method, a tabu attribute or a combination of several attributes is usually associated with a number of tabu solutions. However, unlike attribute-based tabu search, solution-based tabu search tries to record all the visited solutions and prevent them from being revisited during the following search process. Thus, solution-based tabu search ensures a stronger intensification search ability.

Recent studies on several binary optimization cases including two dispersion problems (minimum difference dispersion [29] and maximum min-sum dispersion [19]) and the classic multidimensional knapsack problem [20] demonstrate that solution-based tabu search is more suitable than attribute-based tabu search. On the other hand, our experience on another dispersion problem (max-mean dispersion [18]) does not confirm the advantage of the solution-based tabu search approach over the attribute-based tabu search approach. So one interesting question concerning the solution-based and attribute-based tabu search approaches is under what circumstances one approach will be more suitable than the other. Given that solution-based tabu search has been investigated only very recently, little knowledge is currently available, which makes it difficult to provide a meaningful guidance on the choice between these two approaches. To fully characterize these approaches and understand the relationships between these approaches and the optimization problem under consideration, more studies are clearly needed, which constitutes an interesting research perspective.

Finally, the ideas of the present solution-based tabu search algorithm being quite general, they could conveniently be tested on other binary optimization problems, by adjusting the $\gamma$ parameters of the hash functions (Eq. (15), Section 2.3.2) or by increasing the number of the hash vectors and the associated hash functions.
# 5 Conclusions

In this work, we investigated the NP-hard multidemand multidimensional knapsack problem, by proposing a two-stage tabu search (TSTS) algorithm that combines two solution-based tabu search procedures and a penalty-based evaluation function to explore different search spaces. Computational results on 156 benchmark instances showed that the proposed algorithm is competitive compared to the state-of-art results in the literature, especially for those instances with a large number of knapsack and demand constraints.

The experimental analysis showed the usefulness of the two-stage search strategy and the respective impacts of two stages on the performance of the algorithm. The first search stage is able to reach a promising hyperplane containing high-quality solutions, and the second search stage is able to find elite solutions by an intensified examination of the given hyperplane. We also showed that the hash functions used by the tabu search algorithms are a key component that significantly influences the performance of the algorithm.

This work enriches the existing tools for effectively solving the MDMKP and invites more research and attention on solution-based tabu search for solving binary optimization problems in the future. Specifically, given that the ideas of the two-stage strategy and the solution-based tabu search procedures developed in this work are quite general, it would be interesting to investigate their effectiveness on other problems, especially those related to subset selection problems for which the search space can be divided into a series of hyperplanes. It is also interesting to study search strategies mixing solution-based and attribute-based approaches. As a more fundamental research perspective, studies on a characterization of both solution-based and attribute-based search approaches are needed, which could ease the choice of one or the other approach to solve additional binary optimization problems.

# Acknowledgments

We are grateful to the reviewers for their valuable comments which helped us to improve the paper. This work is partially supported by the National Natural Science Foundation of China (Grant No. 61703213), the Natural Science Foundation of Jiangsu Province of China (Grant No. BK20170904), and NUPTSF (Grant No. NY217154).
References

[1] Arntzen H., Hvattum L.M., Lokketangen A., 2006, Adaptive memory search for multidemand multidimensional knapsack problems. *Computers and Operations Research*, 33, 2508-2525.

[2] Balachandar S.R., 2010, On efficient techniques for NP-hard problems. *PhD Thesis*, Chapter 5, Sastra University, http://hdl.handle.net/10603/17553

[3] Beaujon G.J., Marin S.P., McDonald G.C., 2001. Balancing and optimizing a portfolio of R&D projects. *Naval Research Logistics*, 48(1), 18–40.

[4] Cappanera P., Gallo G., Maffioli F., 2004, Discrete facility location and routing of obnoxious activities. *Discrete Applied Mathematics*, 133, 3–28.

[5] Cappanera P., Trubian M., 2005, A local search based heuristic for the demand constrained multidimensional knapsack problem. *INFORMS Journal on Computing*, 17(1), 82–98.

[6] Carlton W.B., Barnes J.W., 1996, A note on hashing functions and tabu search algorithms. *European Journal of Operational Research*, 95(1), 237–239.

[7] Carlton W.B., Barnes J.W., 1996, Solving the traveling salesman problem with time windows using tabu search. *IIE Transactions*, 28, 617–629.
Carrasco, R., Anthanh P.T., Gallego M., Gortázar F., Duarte A., Martí R., 2015, Tabu search for the max-mean dispersion problem. *Knowledge Based System*, 85, 256–264.

[8] Chen Y. and Hao J.K., 2017, An iterated “hyperplane exploration” approach for the Quadratic Knapsack Problem. *Computers & Operations Research*, 77, 226–239.

[9] Chu P.C., Beasley J.E., 1998, A genetic algorithm for the multidimensional knapsack problem. *Journal of Heuristics*, 4, 63–86.

[10] Delissa L., 2014, The existence and usefulness of equality cuts in the multidemand multidimensional knapsack problem. *Thesis*, Kansas State University, http://krex.k-state.edu/dspace/handle/2097/17399.

[11] Fréville A., 2004, The multidimensional 0-1 knapsack problem: An overview. *European Journal of Operational Research*, 155, 1–21.

[12] Glover F., Laguna M., 1997, Tabu search. Kluwer Academic Publishers, Boston.

[13] Glover F., Kochenberger. G.A., 1996, Critical event tabu search for multidimensional knapsack problems. Osman I.H., Kelly J.P., eds. Metaheuristics: Theory and Applications. Kluwer Academic Publishers, Boston, MA, 407–427.

[14] Gortázar F., Duarte A., Laguna M., Martí R., 2010, Black box scatter search for general classes of binary optimization problems. *Computers & Operations Research*, 37, 1977–1986.
[15] Hanafi S., A. Fréville A., 1998, An efficient tabu search approach for the 0-1 multidimensional knapsack problem. *European Journal of Operational Research*, 106, 659-675.

[16] Hvattum L.M., Løkketangen A., 2007, Experiments using scatter search for the multidemand multidimensional knapsack problem. In: Doerner K.F., Gendreau M., Greistorfer P., Gutjahr W., Hartl R.F., Reimann M. (eds) Metaheuristics. Operations Research/Computer Science Interfaces Series, vol. 39. Springer, Boston, MA.

[17] Hvattum L.M., Arntzen H., Løkketangen A., Glover F., 2010, Alternating control tree search for knapsack/covering problems. *Journal of Heuristics*, 16(3), 239-258.

[18] Lai X.J., Hao J.K., 2016, A tabu search based memetic search algorithm for the max-mean dispersion problem, *Computers & Operations Research*, 72, 118-127.

[19] Lai X.J., Yue D., Hao J.K., Glover F., 2018, Solution-based tabu search for the maximum min-sum dispersion problem. *Information Sciences*, 441, 79-94.

[20] Lai X.J., Hao J.K., Glover F., Lü Z.P., 2018, A two-phase hybrid evolutionary algorithm for the 0-1 multidimensional knapsack problem. *Information Sciences*, 436, 282-301.

[21] Mansini R., Speranza M.G., 2012, CORAL: an exact algorithm for the multidimensional knapsack problem. *INFORMS Journal on Computing*, 24(3), 399-415.

[22] Plastria F., 2001, Static competitive facility location: An overview of optimisation approaches. *European Journal of Operational Research*, 129, 461-470.

[23] Puchinger J., Raidl G.R., Pferschy U., 2009, The multidimensional knapsack problem: structure and algorithms. *INFORMS Journal on Computing*, 22(2), 250-265.

[24] Romero-Moraleses D., Carrizosa E., Conde E., 1997, Semi-obnoxious location models: A global optimization approach. *European Journal of Operational Research*, 102, 295-301.

[25] Shih W., 1979, A branch & bound method for the multiconstraint zero-one knapsack problem. *Journal of the Operational Research Society*, 30, 369-378.

[26] Vasquez M., Hao J.K., A hybrid approach for the 0-1 multidimensional knapsack problem. Proc. of the 17th Intl. Joint Conference on Artificial Intelligence (IJCAI-01), pages 328-333, Seattle, Washington, USA, August 2001. Morgan Kaufmann Publishers.

[27] Vasquez M., Vimont Y., 2005, Improved results on the 0-1 multidimensional knapsack problem. *European Journal of Operational Research*, 165, 70-81.

[28] Vimont Y., Boussier S., Vasquez M., 2008, Reduced costs propagation in an efficient implicit enumeration for the 0-1 multidimensional knapsack problem. *Journal of Combinatorial Optimization*, 15, 165-178.
[29] Wang Y., Wu Q., Glover F., 2017, Effective metaheuristic algorithms for the minimum differential dispersion problem. *European Journal of Operational Research*, 258, 829-843.

[30] Wishon C., Villalobos J.R., 2016, Robust efficiency measures for linear knapsack problem variants. *European Journal of Operational Research*, 254(2), 398-409.

[31] Woodruff D.L., Zemel E., 1993, Hashing vectors for tabu search, *Annals of Operations Research*, 41(2), 123-137.

[32] Yeniay Ö., 2005, Penalty function methods for constrained optimization with genetic algorithms. *Mathematical and Computational Applications*, 10(1), 45-56.

A Appendix

This Appendix presents the detailed computational results of the proposed TSTS algorithm for the third and fourth sets of benchmark instances for which no detailed results are available in the literature. These instances have 100 or 500 items, 30 knapsack constraints and 30 demand constraints, making them more difficult to solve. For each of these instances, the TSTS algorithm was run 30 times under the condition presented in Section 3.2 and the computational results are summarized in Table A.1, where the symbols have the same meanings as in the previous tables. In addition, we report in Table A.2 the computational results of our TSTS algorithm on instances with $n = 250$ under a long time limit of $t_{max} = 300$ (instead of $t_{max} = 60$ used in Section 3). The results reported in this Appendix can serve as references for future comparative studies of new MDMKP algorithms.

We observe from Table A.1 that TSTS is able to reach the best result ($f_{best}$) with a success rate of 100% for 15 out of 30 small instances with $n = 100$, which means a good robustness of our TSTS algorithm on these instances. Note that for some small instances with $n = 100$, $m = 30$, and $q = 30$, it is difficult for some state-of-the-art algorithms in the literature [17] to obtain a feasible solution. However, it is very easy for our TSTS algorithm to obtain a feasible solution for all these instances. For other instances, the standard deviation ($\sigma_f$) of objective values obtained by the TSTS algorithm is relatively small, which indicates a good robustness of the algorithm. Regarding the value of $k$ which represents the number of items selected, it can be seen that the gap between $k_{best}$ and $k_{avg}$ and the standard deviation ($\sigma_k$) of $k$ values obtained are very small, implying that the two-stage strategy of the algorithm is very robust and effective.

Table A.2 shows that our TSTS algorithm improves the best known results for 16 out of 48 instances, matches the best known results for 24 instances, and misses the best known results for only 8 instances. These results indicate
that the performance of our TSTS algorithm can be further improved when a
longer computation time is available.
<caption>Table A.1</caption>

Computational results of the TSTS algorithm on the instances with a large number of constraints under the condition presented in Section 3.2. For each of these instances, there are 30 knapsack constraints and 30 demand constraints.

<table><thead><tr><th>Instance</th><th>f<sub>best</sub></th><th>f<sub>avg</sub></th><th>f<sub>worst</sub></th><th>σ<sub>f</sub></th><th>k<sub>best</sub></th><th>k<sub>avg</sub></th><th>σ<sub>k</sub></th></tr></thead><tbody><tr><td>100-30-30-0-2-1</td><td>11312</td><td>11300.00</td><td>11252</td><td>24.00</td><td>25</td><td>25.20</td><td>0.40</td></tr><tr><td>100-30-30-0-2-2</td><td>9945</td><td>9945.00</td><td>9945</td><td>0.00</td><td>25</td><td>25.00</td><td>0.00</td></tr><tr><td>100-30-30-0-2-3</td><td>11195</td><td>11130.33</td><td>10225</td><td>241.96</td><td>25</td><td>25.07</td><td>0.25</td></tr><tr><td>100-30-30-0-2-4</td><td>11324</td><td>11290.40</td><td>11198</td><td>55.72</td><td>25</td><td>25.00</td><td>0.00</td></tr><tr><td>100-30-30-0-2-5</td><td>9704</td><td>9704.00</td><td>9704</td><td>0.00</td><td>25</td><td>25.00</td><td>0.00</td></tr><tr><td>100-30-30-0-2-6</td><td>23296</td><td>23296.00</td><td>23296</td><td>0.00</td><td>50</td><td>50.00</td><td>0.00</td></tr><tr><td>100-30-30-0-2-7</td><td>22442</td><td>22224.40</td><td>22126</td><td>125.49</td><td>51</td><td>50.27</td><td>0.44</td></tr><tr><td>100-30-30-0-2-8</td><td>23452</td><td>23312.90</td><td>23182</td><td>45.57</td><td>51</td><td>50.13</td><td>0.34</td></tr><tr><td>100-30-30-0-2-9</td><td>22756</td><td>22756.00</td><td>22756</td><td>0.00</td><td>50</td><td>50.00</td><td>0.00</td></tr><tr><td>100-30-30-0-2-10</td><td>24371</td><td>24323.60</td><td>24287</td><td>28.16</td><td>50</td><td>50.00</td><td>0.00</td></tr><tr><td>100-30-30-0-2-11</td><td>33472</td><td>33472.00</td><td>33472</td><td>0.00</td><td>75</td><td>75.00</td><td>0.00</td></tr><tr><td>100-30-30-0-2-12</td><td>32670</td><td>32670.00</td><td>32670</td><td>0.00</td><td>75</td><td>75.00</td><td>0.00</td></tr><tr><td>100-30-30-0-2-13</td><td>32942</td><td>32942.00</td><td>32942</td><td>0.00</td><td>75</td><td>75.00</td><td>0.00</td></tr><tr><td>100-30-30-0-2-14</td><td>35106</td><td>35106.00</td><td>35106</td><td>0.00</td><td>75</td><td>75.00</td><td>0.00</td></tr><tr><td>100-30-30-0-2-15</td><td>30930</td><td>30788.73</td><td>30767</td><td>55.41</td><td>75</td><td>75.00</td><td>0.00</td></tr><tr><td>100-30-30-1-5-1</td><td>5340</td><td>5340.00</td><td>5340</td><td>0.00</td><td>26</td><td>26.00</td><td>0.00</td></tr><tr><td>100-30-30-1-5-2</td><td>4390</td><td>4390.00</td><td>4390</td><td>0.00</td><td>25</td><td>25.00</td><td>0.00</td></tr><tr><td>100-30-30-1-5-3</td><td>4227</td><td>4227.00</td><td>4227</td><td>0.00</td><td>25</td><td>25.00</td><td>0.00</td></tr><tr><td>100-30-30-1-5-4</td><td>4706</td><td>4433.40</td><td>4424</td><td>50.62</td><td>25</td><td>25.97</td><td>0.18</td></tr><tr><td>100-30-30-1-5-5</td><td>2597</td><td>2591.90</td><td>2546</td><td>15.30</td><td>25</td><td>25.00</td><td>0.00</td></tr><tr><td>100-30-30-1-5-6</td><td>10808</td><td>10647.60</td><td>10462</td><td>92.10</td><td>50</td><td>50.00</td><td>0.00</td></tr><tr><td>100-30-30-1-5-7</td><td>9807</td><td>9789.37</td><td>9766</td><td>5.37</td><td>51</td><td>50.03</td><td>0.18</td></tr><tr><td>100-30-30-1-5-8</td><td>10882</td><td>10865.47</td><td>10753</td><td>42.27</td><td>50</td><td>50.10</td><td>0.30</td></tr><tr><td>100-30-30-1-5-9</td><td>10595</td><td>10595.00</td><td>10595</td><td>0.00</td><td>50</td><td>50.00</td><td>0.00</td></tr><tr><td>100-30-30-1-5-10</td><td>10297</td><td>10285.87</td><td>9963</td><td>59.95</td><td>50</td><td>50.03</td><td>0.18</td></tr><tr><td>100-30-30-1-5-11</td><td>11029</td><td>11029.00</td><td>11029</td><td>0.00</td><td>75</td><td>75.00</td><td>0.00</td></tr><tr><td>100-30-30-1-5-12</td><td>11884</td><td>11823.27</td><td>11747</td><td>45.74</td><td>75</td><td>75.00</td><td>0.00</td></tr><tr><td>100-30-30-1-5-13</td><td>10751</td><td>10751.00</td><td>10751</td><td>0.00</td><td>75</td><td>75.00</td><td>0.00</td></tr><tr><td>100-30-30-1-5-14</td><td>11567</td><td>11567.00</td><td>11567</td><td>0.00</td><td>75</td><td>75.00</td><td>0.00</td></tr><tr><td>100-30-30-1-5-15</td><td>10671</td><td>10368.47</td><td>10351</td><td>59.75</td><td>75</td><td>75.00</td><td>0.00</td></tr><tr><td>500-30-30-0-2-1</td><td>85188</td><td>84991.27</td><td>84418</td><td>185.69</td><td>128</td><td>127.57</td><td>0.62</td></tr><tr><td>500-30-30-0-2-2</td><td>82073</td><td>81856.17</td><td>81504</td><td>141.84</td><td>129</td><td>128.07</td><td>0.44</td></tr><tr><td>500-30-30-0-2-3</td><td>77393</td><td>76995.10</td><td>76516</td><td>205.93</td><td>129</td><td>127.40</td><td>0.80</td></tr><tr><td>500-30-30-0-2-4</td><td>82304</td><td>82049.27</td><td>81628</td><td>158.83</td><td>128</td><td>127.37</td><td>0.75</td></tr><tr><td>500-30-30-0-2-5</td><td>83525</td><td>83300.07</td><td>82779</td><td>170.66</td><td>129</td><td>127.87</td><td>0.72</td></tr><tr><td>500-30-30-0-2-6</td><td>145967</td><td>145705.17</td><td>145474</td><td>88.16</td><td>253</td><td>252.73</td><td>0.68</td></tr><tr><td>500-30-30-0-2-7</td><td>152246</td><td>152019.70</td><td>151665</td><td>132.72</td><td>253</td><td>252.67</td><td>0.79</td></tr><tr><td>500-30-30-0-2-8</td><td>157687</td><td>157487.13</td><td>157087</td><td>129.19</td><td>254</td><td>253.30</td><td>0.82</td></tr><tr><td>500-30-30-0-2-9</td><td>153751</td><td>153548.53</td><td>153365</td><td>87.25</td><td>254</td><td>252.33</td><td>0.75</td></tr><tr><td>500-30-30-0-2-10</td><td>142173</td><td>141943.90</td><td>141721</td><td>110.37</td><td>253</td><td>252.67</td><td>0.75</td></tr><tr><td>500-30-30-0-2-11</td><td>185226</td><td>184986.67</td><td>184781</td><td>91.72</td><td>377</td><td>376.97</td><td>0.55</td></tr><tr><td>500-30-30-0-2-12</td><td>194614</td><td>194444.30</td><td>194275</td><td>72.88</td><td>376</td><td>376.87</td><td>0.67</td></tr><tr><td>500-30-30-0-2-13</td><td>208246</td><td>208129.67</td><td>207904</td><td>76.15</td><td>378</td><td>377.53</td><td>0.72</td></tr><tr><td>500-30-30-0-2-14</td><td>215849</td><td>215693.30</td><td>215381</td><td>90.85</td><td>378</td><td>377.67</td><td>0.65</td></tr><tr><td>500-30-30-0-2-15</td><td>194224</td><td>194037.03</td><td>193788</td><td>91.74</td><td>376</td><td>376.57</td><td>0.62</td></tr><tr><td>500-30-30-1-5-1</td><td>51666</td><td>51574.93</td><td>51359</td><td>65.87</td><td>126</td><td>126.50</td><td>0.56</td></tr><tr><td>500-30-30-1-5-2</td><td>50101</td><td>49871.50</td><td>49566</td><td>123.11</td><td>126</td><td>126.33</td><td>0.54</td></tr><tr><td>500-30-30-1-5-3</td><td>51226</td><td>50979.60</td><td>50842</td><td>88.53</td><td>126</td><td>126.13</td><td>0.62</td></tr><tr><td>500-30-30-1-5-4</td><td>51637</td><td>51483.20</td><td>51261</td><td>91.69</td><td>127</td><td>126.77</td><td>0.42</td></tr><tr><td>500-30-30-1-5-5</td><td>52078</td><td>51860.97</td><td>51655</td><td>103.52</td><td>128</td><td>127.00</td><td>0.63</td></tr><tr><td>500-30-30-1-5-6</td><td>84052</td><td>83834.80</td><td>83548</td><td>104.57</td><td>251</td><td>251.03</td><td>0.41</td></tr><tr><td>500-30-30-1-5-7</td><td>82850</td><td>82637.00</td><td>82342</td><td>116.19</td><td>250</td><td>250.87</td><td>0.56</td></tr><tr><td>500-30-30-1-5-8</td><td>82722</td><td>82576.90</td><td>82419</td><td>74.14</td><td>250</td><td>250.70</td><td>0.46</td></tr><tr><td>500-30-30-1-5-9</td><td>82825</td><td>82451.43</td><td>81944</td><td>146.82</td><td>250</td><td>250.23</td><td>0.62</td></tr><tr><td>500-30-30-1-5-10</td><td>82845</td><td>82559.93</td><td>82098</td><td>143.15</td><td>249</td><td>249.67</td><td>0.60</td></tr><tr><td>500-30-30-1-5-11</td><td>88887</td><td>88756.90</td><td>88556</td><td>75.33</td><td>374</td><td>374.23</td><td>0.42</td></tr><tr><td>500-30-30-1-5-12</td><td>87254</td><td>87136.80</td><td>86815</td><td>82.34</td><td>374</td><td>374.20</td><td>0.65</td></tr><tr><td>500-30-30-1-5-13</td><td>87315</td><td>87167.80</td><td>87028</td><td>61.20</td><td>375</td><td>374.80</td><td>0.54</td></tr><tr><td>500-30-30-1-5-14</td><td>87583</td><td>87486.57</td><td>87261</td><td>89.89</td><td>374</td><td>373.90</td><td>0.65</td></tr><tr><td>500-30-30-1-5-15</td><td>87956</td><td>87814.97</td><td>87616</td><td>72.05</td><td>374</td><td>374.10</td><td>0.40</td></tr><tr><td>Avg.</td><td>62265.52</td><td>62139.10</td><td>61957.25</td><td>70.33</td><td>150.88</td><td>150.78</td><td>0.34</td></tr></tbody></table>
<caption>Table A.2</caption>

Computational results of the TSTS algorithm on the instances with $n = 250$ under a time limit of $t_{max} = 300$ seconds. In terms of $f_{best}$, the improved results are indicated in bold and the worse results are indicated in italic compared to the best known objective value (BKV) reported in the literature.

<table><thead><tr><th>Instance</th><th>BKV</th><th>f<sub>best</sub></th><th>f<sub>avg</sub></th><th>f<sub>worst</sub></th><th>σ<sub>f</sub></th><th>k<sub>best</sub></th><th>k<sub>avg</sub></th><th>σ<sub>k</sub></th></tr></thead><tbody><tr><td>250-5-2-0-0</td><td>78486</td><td>78486</td><td>78282.30</td><td>77986</td><td>173.14</td><td>79</td><td>78.17</td><td>0.73</td></tr><tr><td>250-5-2-0-1</td><td>75132</td><td>75132</td><td>74849.07</td><td>74152</td><td>232.22</td><td>78</td><td>76.10</td><td>0.94</td></tr><tr><td>250-5-2-0-2</td><td>71003</td><td>70898</td><td>70676.77</td><td>70137</td><td>217.86</td><td>78</td><td>76.87</td><td>0.92</td></tr><tr><td>250-5-2-0-3</td><td>80311</td><td>80311</td><td>80250.07</td><td>80131</td><td>53.66</td><td>79</td><td>79.10</td><td>0.54</td></tr><tr><td>250-5-2-0-4</td><td>70935</td><td>70935</td><td>70856.43</td><td>70805</td><td>63.06</td><td>79</td><td>78.40</td><td>0.49</td></tr><tr><td>250-5-2-0-5</td><td>130981</td><td>130448</td><td>129283.31</td><td>127720</td><td>686.96</td><td>138</td><td>134.23</td><td>1.36</td></tr><tr><td>250-5-2-1-0</td><td>26666</td><td>26666</td><td>26603.30</td><td>26504</td><td>47.41</td><td>71</td><td>70.23</td><td>0.62</td></tr><tr><td>250-5-2-1-1</td><td>26864</td><td>26864</td><td>26841.70</td><td>26727</td><td>35.40</td><td>69</td><td>68.97</td><td>0.55</td></tr><tr><td>250-5-2-1-2</td><td>27280</td><td>27280</td><td>27232.97</td><td>27052</td><td>54.88</td><td>73</td><td>72.30</td><td>0.86</td></tr><tr><td>250-5-2-1-3</td><td>26269</td><td>26269</td><td>26217.17</td><td>26148</td><td>37.72</td><td>69</td><td>68.63</td><td>0.84</td></tr><tr><td>250-5-2-1-4</td><td>27293</td><td>27293</td><td>27233.30</td><td>27184</td><td>29.95</td><td>70</td><td>70.40</td><td>0.84</td></tr><tr><td>250-5-2-1-5</td><td>44419</td><td>44386</td><td>44318.67</td><td>44022</td><td>90.92</td><td>129</td><td>127.97</td><td>1.40</td></tr><tr><td>250-5-5-0-0</td><td>68026</td><td>68026</td><td>68023.43</td><td>68019</td><td>3.37</td><td>76</td><td>75.63</td><td>0.48</td></tr><tr><td>250-5-5-0-1</td><td>60795</td><td>60785</td><td>60675.60</td><td>60456</td><td>82.68</td><td>73</td><td>72.27</td><td>0.68</td></tr><tr><td>250-5-5-0-2</td><td>62093</td><td>62093</td><td>62072.10</td><td>61960</td><td>35.00</td><td>74</td><td>74.23</td><td>0.56</td></tr><tr><td>250-5-5-0-3</td><td>66567</td><td>66567</td><td>66522.10</td><td>66400</td><td>41.43</td><td>76</td><td>75.27</td><td>0.57</td></tr><tr><td>250-5-5-0-4</td><td>61929</td><td>61929</td><td>61920.00</td><td>61878</td><td>18.10</td><td>76</td><td>75.93</td><td>0.44</td></tr><tr><td>250-5-5-0-5</td><td>127934</td><td>127922</td><td>127769.60</td><td>127240</td><td>187.71</td><td>136</td><td>134.67</td><td>0.70</td></tr><tr><td>250-5-5-1-0</td><td>26966</td><td>26973</td><td>26925.60</td><td>26869</td><td>31.43</td><td>68</td><td>66.93</td><td>0.77</td></tr><tr><td>250-5-5-1-1</td><td>26665</td><td>26665</td><td>26616.73</td><td>26520</td><td>59.80</td><td>66</td><td>65.73</td><td>0.57</td></tr><tr><td>250-5-5-1-2</td><td>26648</td><td>26648</td><td>26586.10</td><td>26536</td><td>22.47</td><td>65</td><td>65.63</td><td>0.48</td></tr><tr><td>250-5-5-1-3</td><td>25923</td><td>25923</td><td>25813.13</td><td>25684</td><td>64.51</td><td>66</td><td>65.83</td><td>0.78</td></tr><tr><td>250-5-5-1-4</td><td>26021</td><td>26064</td><td>26008.77</td><td>25823</td><td>44.13</td><td>67</td><td>66.93</td><td>0.63</td></tr><tr><td>250-5-5-1-5</td><td>41372</td><td>41372</td><td>41270.67</td><td>41129</td><td>53.23</td><td>126</td><td>126.30</td><td>0.64</td></tr><tr><td>250-10-5-0-0</td><td>56306</td><td>56221</td><td>56008.07</td><td>55430</td><td>158.01</td><td>69</td><td>67.67</td><td>0.65</td></tr><tr><td>250-10-5-0-1</td><td>59564</td><td>59619</td><td>59575.30</td><td>59447</td><td>52.03</td><td>71</td><td>71.00</td><td>0.52</td></tr><tr><td>250-10-5-0-2</td><td>54898</td><td>54912</td><td>54700.40</td><td>54367</td><td>179.52</td><td>70</td><td>69.17</td><td>0.78</td></tr><tr><td>250-10-5-0-3</td><td>52399</td><td>52388</td><td>52209.00</td><td>51975</td><td>98.42</td><td>68</td><td>67.57</td><td>0.67</td></tr><tr><td>250-10-5-0-4</td><td>58234</td><td>58234</td><td>57833.13</td><td>57156</td><td>222.30</td><td>69</td><td>67.60</td><td>0.71</td></tr><tr><td>250-10-5-0-5</td><td>99682</td><td>99646</td><td>99359.67</td><td>99023</td><td>176.86</td><td>130</td><td>129.07</td><td>0.73</td></tr><tr><td>250-10-5-1-0</td><td>26867</td><td>26976</td><td>26918.33</td><td>26766</td><td>55.74</td><td>66</td><td>65.03</td><td>0.48</td></tr><tr><td>250-10-5-1-1</td><td>26585</td><td>26658</td><td>26562.03</td><td>26486</td><td>35.34</td><td>67</td><td>66.73</td><td>0.68</td></tr><tr><td>250-10-5-1-2</td><td>25737</td><td>25749</td><td>25661.60</td><td>25515</td><td>59.69</td><td>64</td><td>64.20</td><td>0.60</td></tr><tr><td>250-10-5-1-3</td><td>27162</td><td>27181</td><td>27138.93</td><td>26971</td><td>46.61</td><td>65</td><td>64.93</td><td>0.36</td></tr><tr><td>250-10-5-1-4</td><td>26816</td><td>26856</td><td>26776.10</td><td>26706</td><td>55.74</td><td>66</td><td>65.47</td><td>0.50</td></tr><tr><td>250-10-5-1-5</td><td>46244</td><td>46244</td><td>46170.97</td><td>46137</td><td>23.64</td><td>128</td><td>127.10</td><td>0.30</td></tr><tr><td>250-10-10-0-0</td><td>52441</td><td>52441</td><td>52363.33</td><td>52171</td><td>78.20</td><td>68</td><td>67.07</td><td>0.57</td></tr><tr><td>250-10-10-0-1</td><td>53720</td><td>53745</td><td>53689.97</td><td>53607</td><td>33.25</td><td>68</td><td>68.60</td><td>0.49</td></tr><tr><td>250-10-10-0-2</td><td>46927</td><td>46927</td><td>46830.67</td><td>46546</td><td>87.89</td><td>67</td><td>66.47</td><td>0.62</td></tr><tr><td>250-10-10-0-3</td><td>54782</td><td>54856</td><td>54780.47</td><td>54507</td><td>60.51</td><td>68</td><td>67.50</td><td>0.56</td></tr><tr><td>250-10-10-0-4</td><td>49675</td><td>49675</td><td>49578.80</td><td>49342</td><td>104.58</td><td>67</td><td>66.03</td><td>0.71</td></tr><tr><td>250-10-10-0-5</td><td>92959</td><td>92989</td><td>92823.07</td><td>92465</td><td>141.18</td><td>130</td><td>129.27</td><td>0.73</td></tr><tr><td>250-10-10-1-0</td><td>26696</td><td>26696</td><td>26678.47</td><td>26606</td><td>28.58</td><td>64</td><td>63.63</td><td>0.48</td></tr><tr><td>250-10-10-1-1</td><td>25757</td><td>25893</td><td>25822.07</td><td>25771</td><td>29.03</td><td>62</td><td>63.07</td><td>0.44</td></tr><tr><td>250-10-10-1-2</td><td>26356</td><td>26517</td><td>26490.50</td><td>26438</td><td>35.14</td><td>64</td><td>63.70</td><td>0.46</td></tr><tr><td>250-10-10-1-3</td><td>26684</td><td>26684</td><td>26641.83</td><td>26598</td><td>37.16</td><td>63</td><td>63.47</td><td>0.50</td></tr><tr><td>250-10-10-1-4</td><td>26554</td><td>26676</td><td>26630.10</td><td>26603</td><td>18.02</td><td>65</td><td>64.10</td><td>0.30</td></tr><tr><td>250-10-10-1-5</td><td>42528</td><td>42629</td><td>42520.90</td><td>42306</td><td>70.96</td><td>123</td><td>123.80</td><td>0.48</td></tr><tr><td>Avg.</td><td>49836.48</td><td>49840.56</td><td>49721.10</td><td>49500.44</td><td>88.66</td><td>79.65</td><td>79.15</td><td>0.64</td></tr><tr><td>#Better</td><td></td><td>16</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>#Equal</td><td></td><td>24</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>#Worse</td><td></td><td>8</td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>