Innovative improved approximate solution method for the integer knapsack problem, error compression and computational experiments

Abstract

EN: 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. UK: Актуальність. Математичні моделі багатьох задач оптимізації, що зустрічаються в економіці та техніці, розглядаються у формі задачі про цілочисельний рюкзак. Оскільки ця задача належить до класу «NP-повних», тобто «важко розв’язуваних», кількість операцій, необхідних відомим методам для знаходження її оптимального розв’язку, експоненціальна. Це не дозволяє вирішувати масштабні завдання в режимі реального часу. Тому розроблено різноманітні та швидкопрацюючі методи наближеного розв’язання цієї задачі. Однак відомо, що наближене рішення, отримане цими методами, у більшості випадків може суттєво відрізнятися від оптимального. Тому після прийняття будь-якого наближеного рішення за вихідну точку виникає потреба розробити методи його подальшого вдосконалення. Розробка таких методів має як теоретичне, так і велике практичне значення. Мета роботи. Основна мета вирішення цього питання полягає в наступному. Основна мета виконання даної роботи полягає в тому, щоб будь-яким відомим методом спочатку знайти вихідний наближений розв’язок задачі, а потім розробити алгоритм для послідовного подальшого вдосконалення цього розв’язку. Для цього необхідно визначити набір чисел, якими можуть відрізнятися координати оптимального і знайденого наближеного розв’язку. Після цього слід побудувати нові розв’язки шляхом присвоєння можливих значень невідомим, що відповідають числам цього набору, і вибрати найкраще з цих розв’язків. Але алгоритм побудови такого рішення повинен бути простим, вимагати невеликої кількості операцій, не викликати труднощів з точки зору програмування, бути новим і застосовним до практичних завдань. Метод. Суть запропонованого способу полягає в наступному. Спочатку за відомим правилом знаходять початковий наближений розв’язок задачі, що розглядається, і відповідне йому значення цільової функції. Після цього оптимальний розв’язок задачі легко знаходить відомим методом без урахування умови цілості невідомих. Очевидно, що цей розв’язок може приймати не більше одного дробового значення координати. Передбачається, що координати оптимального розв’язку цілочисельної задачі про ранець і початкового наближеного розв’язку можуть відрізнятися навколо певної дробової координати оптимального розв’язку неперервної задачі. Потім знайдено мінімальну кількість ненульових координат і нульових координат в оптимальному розв’язку. Для цього доведено відповідні теореми. Передбачається, що різні координати оптимального розв’язку та початкового наближеного розв’язку знаходяться між цими мінімальними числами. Таким чином, найкраще рішення можна вибрати шляхом послідовної зміни координат між цими мінімальними числами один за одним. Результати. Із застосуванням запропонованого методу були проведені численні розрахункові експерименти. Висока якість цього методу ще раз підтверджена експериментально. Висновки. Запропонований метод є новим, простим за своєю суттю, легким для програмування та має важливе практичне значення. Таким чином, ми називаємо це рішення інноваційним покращеним наближеним рішенням.