INNOVATIVE IMPROVED APPROXIMATE SOLUTION METHOD FOR THE INTEGER KNAPSACK PROBLEM, ERROR COMPRESSION AND COMPUTATIONAL EXPERIMENTS

Abstract

Context. Mathematical models of many optimization problems encountered in economics and engineering are taken in the form of an integer knapsack problem. Since this problem belongs to the class of “NP-complete”, that is, “hard to solve” problems, the number of operations required by known methods to find its optimal solution is exponential. This does not allow solving large-scale problems in real time. Therefore, various and fast working approximate solution methods of this problem have been developed. However, it is known that the approximate solution provided by those methods can differ significantly from the optimal solution in most cases. Therefore, after taking any approximate solution as a starting point, there is a demand to develop methods for its further improvement. Development of such methods has both theoretical and great practical importance.

Objective. The main purpose solving of this issue is as follows. The main purpose in performing this work is to first find an initial approximate solution of the problem using any known method, and then work out an algorithm for successively further improvement of this solution. For this purpose, the set of numbers with which the coordinates of the optimal solution and the found approximate solution can differ should be determined. After that, new solutions should be constructed by assigning possible values to the unknowns corresponding to the numbers in that set, and the best among these solutions should be selected. However, the algorithm for constructing such a solution should be simple, require a small number of operations, not cause difficulties from the point of view of programming, be new and be applicable to practical issues.

Method. The essence of the proposed method consists of the following. First, the initial approximate solution of the considered problem and the value of the objective function corresponding to this solution are found by a known rule. After that, the optimal solution of the problem is easily found by a known method, without taking into account the condition that the unknowns are integers. Obviously, this solution can take at most one coordinate fractional value. It is assumed that the coordinates of the optimal solution of the integer knapsack problem and the initial approximate solution may differ around a certain fractional coordinate of the optimal solution of the continuous problem. Then, the minimum number of non-zero coordinates and zero coordinates in the optimal solution is found. Corresponding theorems have been proved for this. It is assumed that the different coordinates of the optimal solution and the initial approximate solution located between those minimal numbers. Therefore, the best solution can be selected by successively changing the coordinates between those minimum numbers one by one.

Results. Extensive calculation experiments were conducted with the application of the proposed method.To have a high quality of this method was confirmed once again through experiments.

Conclusions. The proposed method is new, simple in nature, easy to consider from the programming point of view, and has important practical importance. Thus, we call this solution the innovative improved approximate solution.