首页 | 本学科首页   官方微博 | 高级检索  
     


An incomplete m-exchange algorithm for solving the large-scale multi-scenario knapsack problem
Authors:Xiang Song  Rhyd LewisJonathan Thompson  Yue Wu
Affiliation:a Logistics and Management Mathematics Group, Department of Mathematics, University of Portsmouth, Lion Gate Building, Lion Terrace, Portsmouth P01 3HF, UK
b Department of Mathematics, Cardiff University, Senghennydd Road, Cardiff CF24 4AG, UK
c School of Management, University of Southampton Highfield, Southampton SO17 1BJ, UK
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.
Keywords:2-Exchange  Multi-scenario  Knapsack problem
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号