Construction of Generating Feasible Subsets in the Knapsack Problem

Abstract

A method for constructing a group of generating feasible subsets in the knapsack problem under the condition that the non-dominance depth of a given Pareto layer is greater than zero is developed. The method is based on a multicriterial mathematical model for solving the knapsack problem with two quality criteria and partitioning the initial data set of the knapsack problem into separate Pareto layers. Various methods for constructing generating feasible subsets are proposed depending on the relationship between the coordinates of the elements of the given Pareto layers and the knapsack volume. The structure of the Pareto layers, which are a non-dominance group of a given individual Pareto layer, is determined. It is shown that there is a Pareto layer, starting from which it is not necessary to consider the elements of this layer and all subsequent ones when constructing feasible subsets. This follows from the ordering of the elements of the initial data set of the knapsack problem according to the priority of their inclusion in the feasible subsets.