الگوریتم های برنامه ریزی پویا مبتنی بر عملکرد محاسباتی کاهش دولتی اساسی برای مسائل 0-1 پشت وار هدف دوطرفه ه

This paper studies a group of basic state reduction based dynamic programming (DP) algorithms for the multi-objective 0–1 knapsack problem (MKP), which are related to the backward reduced-state DP space (BRDS) and forward reduced-state DP space (FRDS). The BRDS is widely ignored in the literature because it imposes disadvantage for the single objective knapsack problem (KP) in terms of memory requirements. The FRDS based DP algorithm in a general sense is related to state dominance checking, which can be time consuming for the MKP while it can be done efficiently for the KP. Consequently, no algorithm purely based on the FRDS with state dominance checking has ever been developed for the MKP. In this paper, we attempt to get some insights into the state reduction techniques efficient to the MKP. We first propose an FRDS based algorithm with a local state dominance checking for the MKP. Then we evaluate the relative advantage of the BRDS and FRDS based algorithms by analyzing their computational time and memory requirements for the MKP. Finally different combinations of the BRDS and FRDS based algorithms are developed on this basis. Numerical experiments based on the bi-objective KP instances are conducted to compare systematically between these algorithms and the recently developed BRDS based DP algorithm as well as the existing FRDS based DP algorithm without state dominance checking.

The multi-objective 0–1 knapsack problem (MKP) can be viewed as an extension of the single objective 0–1 knapsack problem (KP) [1] to accommodate more than one objective [2]. The MKP can be defined as follows: given a knapsack of capacity WW and a set of nn items, each item associated with rr integer profits, denoted by an rr-dimensional vector (View the MathML sourcecj1,…,cjr), and an integer weight wj,j=1,…,nwj,j=1,…,n. The problem consists of selecting a subset of the items whose total weight does not exceed WW and whose profit objectives are “maximized” in the Pareto sense. The problem can be formulated as the following multi-objective linear integer programming model: equation(1) View the MathML source“max”(∑j=1ncj1xj,…,∑j=1ncjrxj) Turn MathJax on subject to: equation(2) View the MathML source∑j=1nwjxj≤W, Turn MathJax on equation(3) View the MathML sourcexj∈{0,1},j=1,…,n. Turn MathJax on Here binary variables xjxj are used to indicate whether item jj is included in the knapsack or not. In addition, we follow the common assumptions in most literature: WW, wjwj, View the MathML sourcecjk (View the MathML sourcej=1,…,n,k=1,…,r) are positive integers. To avoid trivial solutions, it is assumed that View the MathML sourcewj≤W (j=1,…,nj=1,…,n) and View the MathML source∑j=1nwj>W. Several approaches have been proposed to solve the MKP, involving both approximate methods and exact algorithms. The approximate approaches mainly include the fptas (fully polynomial approximation scheme) [3] and metaheuristics [4], [5], [6], [7] and [8]. The exact approaches include branch and bound (BB) algorithm [9], dynamic programming (DP) based algorithms [10], [11], [12] and [13], and other exact algorithms, for example, an exact algorithm by exploiting the development for the multi-objective linear programming [14]. In this paper, we revisit the DP based exact algorithms and attempt to identify the state reduction techniques efficient to the MKP convincingly based on studying the computational time and memory requirements of a group of DP based algorithms using different reduction techniques for the bi-objective KP (BKP) instances. The study is motivated by the following facts. First, in the multi-objective optimization context, the solution process consists of finding the Pareto frontier (PF) with a number of non-dominated objective vectors in the objective space which corresponds to efficient solutions in the decision space. Usually, the computational effort increases as the number of objectives increases [2] and [15]. It is a hard task to generate the exact PF. However, there is a growing need for efficient exact algorithms from both theoretical and practical viewpoints though the approximate approaches can generate a good approximation of the PF. Second, based on numerical experiments, it is known that DP based algorithms are among the best exact approaches to solve the MKP. Especially, different DP algorithms show different solution time efficiency against different types of the BKP instances. The DP algorithm using labeling (LDP) approaches [10] outperforms BB based algorithm [9] and the dominance based DP (DDP) algorithm [11] outperforms the LDP algorithm. In practice, multiple conflicting objective instances, where the profit objectives are negatively correlated, are more appropriate to model the real-world situations and these instances are called hard instances defined in [11]. The bounding technique based DP (BDP-II) algorithm [12] is more efficient than the DDP algorithm [11] for the non-hard type of instances while less efficient for the hard type of instances. A recently developed two state reduction based DP (TDP) algorithm [13] performs better than the DDP algorithm especially for the hardest type of instances, where the two conflicting objectives are correlated with weight coefficients, while worse for the easy (quasi single objective) instances with two “unconflicting” profit objectives. Finally, the TDP algorithm [13] differs from all the other DP based algorithms in that the former is based on a backward reduced-state DP space (BRDS) while the latter on the forward reduced-state DP space (FRDS). The DP space consists of all of the states and related transitions between the states in the DP process. The LDP algorithm [10] is based on a special type of FRDS without using state dominance relations. The DDP [11] and BDP-II [12] algorithms are hybrid FRDS based DP algorithms. Before the TDP algorithm, the BRDS has never been applied in developing a DP algorithm because it imposes disadvantage for the KP in terms of the memory requirements. The current algorithm development indicates that the BRDS and FRDS respond differently to the MKP. The FRDS in a general sense is related to the state dominance relation. The state dominance relations can be defined as follows: assume that two states ss and ss’ in the DP space represent the solutions to the same sub-problem, then state ss dominates state ss’ if the total weight of items at state ss’ is not smaller than that at state ss and total profit values at state ss’ are not larger than those at state ss. The FRDS is generated by discarding the dominated states in the DP space and the remaining non-dominated states (nodes) are called sparse nodes. The FRDS based sparse node DP (SDP) algorithm has not be applied to solve the MKP though it was used to solve the 0–1 KP for more than three decades ago [16] and extended to solve the integer KP later [17] and [18] because the state dominance checking can be done efficiently for the KP. A standard SDP algorithm which discards all the dominated states can be inefficient for the MKP because the state dominance checking can be time-consuming when the number of objective vectors of a state is large and it is an NP-hard problem to determine whether a given objective vector is dominated or not [19]. Up to now, the usage of the state dominance relation for the MKP appeared only in a hybrid DP algorithm [11], where several dominance relations were applied together. All the above mentioned DP algorithms make use of some techniques to reduce explicitly or implicitly the number of the states in the DP space. In this paper, we restrict our attention to the basic state reduction techniques used to generate BRDS and FRDS, including state dominance relations. The major contributions of the paper can be summarized as follows. First, we propose a variant of multi-objective SDP algorithm with a local state dominance checking to fill the gap for the FRDS based algorithm using state dominance relations for the MKP. Second, we evaluate the relative computational advantage of the BRDS and FRDS based algorithms by conducting time and space analysis. Third, we propose new DP based algorithms by combining the FRDS and BRDS based algorithms in an innovative manner on this basis. Finally, we compare systematically the computational time and memory requirements of different algorithms by constructing the confidence intervals (using statistical inference [20]) so that the conclusions can be made convincingly in a general sense. The paper is organized as follows. In Section 2, we give an overview of the basic state reduction techniques and related reduced-state DP spaces and present a variant of multi-objective SDP algorithm with a local state dominance checking. In Section 3, we analyze the computational time and memory requirements of the BRDS and FRDS based algorithms. In Section 4 we propose different combinations of the BRDS and FRDS based algorithms. In Section 5, we report the computational results of different DP algorithms based on the BRDS and FRDS for the BKP instances.

In the dynamic programming (DP) context, the basic backward and the forward state reduction techniques are related to generating the backward reduced-state DP space (BRDS) and the forward reduced-state DP space (FRDS), respectively. The state dominance checking is related to the FRDS. In this paper, we have attempted to evaluate the relative computational advantage of the BRDS and FRDS based algorithms by analyzing their memory requirements and computational time and get insight into the techniques that are efficient for the multi-objective 0–1 knapsack problem (MKP) by comparing systematically the performance of the BRDS and FRDS based algorithms as well as their combined variants. The comparisons are made based on constructing the confidence intervals (statistical inference) for the difference between the average solution time and for difference between average requirements of different algorithms so that the conclusions can be made in a general sense instead of the specific data generated in the experiment. The numerical results with different types of bi-objective knapsack problem (BKP) instances show the following results. First, in terms of the single reduced-state DP space based algorithms, the BRDS based algorithm is more efficient for normal BKP instances and large size quasi single objective instances while the FRDS based algorithm (with state dominance checking) is more efficient for the small size quasi single objective instances. Second, the good algorithms should be based on using the computational advantage of the BRDS and FRDS based algorithms complementarily. The best algorithm for dealing with normal BKP instances is the combination of the FRDS based algorithm without state dominance checking and the BRDS based algorithm while the combination of the FRDS based algorithm using state dominance checking and the BRDS based algorithm responds better to quasi single objective instances. The small size quasi single objective instances are close to the single objective instances. The above results imply that the techniques efficient to the MKP are different from those to the single objective case. The BRDS is a valuable asset for the MKP and usage of the state dominance checking needs careful consideration for the MKP. In the multi-objective optimization context, it is difficult to find a single technique that is efficient for all types of instances. Combining different techniques complementarily is a way to develop better algorithms for the MKP.