Analysis of Divide-and-Conquer strategies for the 0–1 minimization knapsack problem

Fernando A. Morales () and Jairo A. Martínez ()
Additional contact information
Fernando A. Morales: Universidad Nacional de Colombia, Sede Medellín
Jairo A. Martínez: Universidad EAFIT

Journal of Combinatorial Optimization, 2020, vol. 40, issue 1, No 14, 234-278

Abstract: Abstract We introduce and asses several Divide-and-Conquer heuristic strategies, aimed at solving large instances of the 0–1 Minimization Knapsack Problem. The method subdivides a large problem in two smaller ones (or recursive iterations of the same procedure), in order to lower down the global computational complexity of the original problem, at the expense of a moderate loss of quality in the solution. Theoretical mathematical results are presented to assure a successful algorithmic application of the method and to suggest the potential strategies for its implementation. In contrast, due to the lack of theoretical results, the solution’s quality deterioration is measured empirically by means of Monte Carlo simulations for several types and values of the chosen strategies. Finally, introducing parameters of efficiency we suggest the best strategies depending on the data input.

Keywords: Divide-and-Conquer; Knapsack problem; Monte Carlo simulations; Method’s efficiency.; 90C59; 90C06; 90C10; 65C05; 68U01 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00584-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:40:y:2020:i:1:d:10.1007_s10878-020-00584-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00584-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().