Content area
Full Text
Comput Optim Appl (2009) 43: 261294
DOI 10.1007/s10589-007-9140-y
Received: 15 May 2006 / Revised: 11 September 2007 / Published online: 7 November 2007 Springer Science+Business Media, LLC 2007
Abstract In this paper, we study an extension of the Linear Multiple Choice Knapsack (LMCK) Problem that considers two objectives. The problem can be used to nd the optimal allocation of an available resource to a group of disjoint sets of activities, while also ensuring that a certain balance on the resource amounts allocated to the activity sets is attained. The rst objective maximizes the prot incurred by the implementation of the considered activities. The second objective minimizes the maximum difference between the resource amounts allocated to any two sets of activities. We present the mathematical formulation and explore the fundamental properties of the problem. Based on these properties, we develop an efcient algorithm that obtains the entire nondominated frontier. The algorithm is more efcient than the application of the general theory of multiple objective linear programming (MOLP), although there is a close underlying relationship between the two. We present theoretical ndings which provide insight into the behavior of the algorithm, and report computational results which demonstrate its efciency for randomly generated problems.
Keywords Linear multiple choice knapsack Balanced resource allocation
Equity Multiobjective linear programming Nondominated frontier
1 Introduction
In recent years, many researchers have focused their efforts on developing criterion space based techniques for the solution of MOLP problems. This is a consequence of
Electronic supplementary material The online version of this article (http://dx.doi.org/10.1007/s10589-007-9140-y
Web End =http://dx.doi.org/10.1007/s10589-007-9140-y ) contains supplementary material, which is available to authorized users.
G. Kozanidis ( )
Systems Optimization Laboratory, Department of Mechanical & Industrial Engineering, University of Thessaly, Volos 38334, Greecee-mail: mailto:[email protected]
Web End [email protected]
Solving the linear multiple choice knapsack problem with two objectives: prot and equity
George Kozanidis
262 G. Kozanidis
the major computational difculties that very often arise when a MOLP is solved in decision space. In this paper, we develop an algorithm for a two objective variation of the linear multiple choice knapsack problem, that is able to obtain the entire frontier of nondominated solutions in criterion space, while working on the decision space of the problem.
The multiple choice knapsack problem is a very commonly used...