An incomplete m-exchange algorithm for solving the large-scale multi-scenario knapsack problem

Song, Xiang ORCID: https://orcid.org/0000-0003-0235-3734, Lewis, Rhyd ORCID: https://orcid.org/0000-0003-1046-811X, Thompson, Jonathan Mark and Wu, Yue 2012. An incomplete m-exchange algorithm for solving the large-scale multi-scenario knapsack problem. Computers & Operations Research 39 (9) , pp. 1988-2000. 10.1016/j.cor.2011.09.012

Full text not available from this repository.

Abstract

This paper introduces a fast heuristic based algorithm for the max-min multi-scenario knapsack problem. The problem is a variation of the standard 0-1 knapsack problem, in which the profits of the items vary under different scenarios, though the capacity of the knapsack is fixed. The objective of the problem is to find the optimal packing of a set of items so that the minimum total profits of the items in the knapsack over all different scenarios is maximized. For some large-scaled instances, traditional branch-and-bound techniques cannot find an optimal solution within reasonable time, thus we propose a collection of incomplete m-exchange algorithms which are able to produce high quality solutions in just a few minutes of cpu time. Various computational results are also given.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Subjects:	Q Science > QA Mathematics
Uncontrolled Keywords:	2-exchange; Multi-scenario; Knapsack problem
Publisher:	Elsevier
ISSN:	0305-0548
Last Modified:	08 Jan 2025 11:49
URI:	https://orca.cardiff.ac.uk/id/eprint/11337

Citation Data

Cited 14 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item