Submitted by: Submitted by cugila
Views: 499
Words: 2052
Pages: 9
Category: Business and Industry
Date Submitted: 03/23/2011 09:11 AM
A Heuristic Algorithm for Large-Scale Multidimensional Knapsack Problems with Concave Return Functions
Working Notes
INTRODUCTION
The multidimensional knapsack problem considered in this paper can be given the following interpretation. There exists a knapsack of m dimensions. The resource capacity of dimension i is bi. There exist n item types available for placement into the knapsack. The number of identical copies of item type j is uj. If the number of copies of item type j placed in the knapsack is xj then aijxj units of the resource at dimension i are utilised and a return of cj(xj) is realised. The return functions are increasing nonlinear concave functions. The objective is to maximise the return on the number of item types placed in the knapsack subject to the resource capacity constraints.
Many real world allocation problems can be effectively modelled as multidimensional knapsack problems. (Beasley, 2009) and (Lin, 1998) give surveys of multidimensional knapsack problems. Examples include multidimensional models of the profitable loading of a ship, value loading of a space shuttle, stock cutting, research and development problems, capital budgeting problems, (Kellerer, Pferschy and Pisinger, 2004, Chapter 7); financial models, production and inventory management, stratified sampling, optimal design of queuing networks in manufacturing and computer systems, (Bretthauer and Shetty, 2002); inventory allocation in assemble-to-order systems, (Akcay, Li and Xu, 2007); inventory control, design of multiproduct chemical processing equipment and computer network design, (Sherali and Myers, 1985). If the allocation problem involves decreasing returns to scale then it is necessary to model the return functions as increasing concave functions..
The inherent computational difficulty in attempting to obtain exact solutions to multidimensional nonlinear knapsack problems motivated the development of the proposed heuristic algorithm. The problem considered...