Back to Search
Start Over
An iterative rounding strategy-based algorithm for the set-union knapsack problem.
- Source :
-
Soft Computing - A Fusion of Foundations, Methodologies & Applications . Nov2021, Vol. 25 Issue 21, p13617-13639. 23p. - Publication Year :
- 2021
-
Abstract
- The knapsack problem arises in several real-world applications, like manufacturing systems, transportation, cutting and packing, and hydrological studies. In this paper, we investigate the use of an iterative rounding strategy-based algorithm for tackling a special knapsack problem: the set-union knapsack problem. First, the approach builds a series of starting partial solutions by using the principle of fractional values related to a series of linear relaxations of the (sub)instance at hand. Second, each step of the rounding procedure is coupled with an enhanced local search procedure, where its goal is to search around a local partial solution by applying the so-called critical element tailored for the problem studied. Third, both degrading and re-optimization strategies are introduced in order to extend the diversified search space. Finally, all strategies are embedded into an iterative search in order to augmenting the quality of the solutions. The performance of the proposed method is evaluated on benchmark instances of the literature and new large-scale instances; its provided results are compared to those reached by the Cplex solver and the best methods available in the literature. The method seems competitive, where it is able to achieve new (lower) bounds and matches the rest of the bounds. [ABSTRACT FROM AUTHOR]
- Subjects :
- *KNAPSACK problems
*ALGORITHMS
*BACKPACKS
*COMBINATORIAL optimization
Subjects
Details
- Language :
- English
- ISSN :
- 14327643
- Volume :
- 25
- Issue :
- 21
- Database :
- Academic Search Index
- Journal :
- Soft Computing - A Fusion of Foundations, Methodologies & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 152975830
- Full Text :
- https://doi.org/10.1007/s00500-021-06091-8