R.R. Niyazova.
Innovative approximate solution methods and error estimation for the knapsack problem
A new innovative approximate solution method of the knapsack problem is developed. First, any approximate solution to the problem is found in the known manner. After that, the process of improving that solution is built successively. Here, a neighborhood of the fractional-valued coordinate in the optimal solution of the continuous problem is found by a certain rule, and a better solution is selected by replacing the units located in this neighborhood with zeros and then replacing the zeros with units.Using the proposed method, a numerical example is solved and extensive computational experiments are conducted on random problems of different dimensions.
Keywords: Knapsack problem, Approximate solution, Innovative approximate solution, Lower and upper bounds of optimal value, Computational experiments
DOI: https://doi.org/10.54381/icp.2024.1.04
Innovative approximate solution methods and error estimation for the knapsack problem
A new innovative approximate solution method of the knapsack problem is developed. First, any approximate solution to the problem is found in the known manner. After that, the process of improving that solution is built successively. Here, a neighborhood of the fractional-valued coordinate in the optimal solution of the continuous problem is found by a certain rule, and a better solution is selected by replacing the units located in this neighborhood with zeros and then replacing the zeros with units.Using the proposed method, a numerical example is solved and extensive computational experiments are conducted on random problems of different dimensions.
Keywords: Knapsack problem, Approximate solution, Innovative approximate solution, Lower and upper bounds of optimal value, Computational experiments
DOI: https://doi.org/10.54381/icp.2024.1.04