Research Reports from the Department of Operations
Document Type
Report
Publication Date
2-1-1981
Abstract
A common problem frequently faced by business firms and individual investors is to select a few investment opportunities from many available possibilities. This problem, in its simplest form, can be modeled as a 0-1 knapsack problem. In a more general investment scenario, however, we obtain a model which is a general knapsack problem with a multiple-choice constraint. To solve this problem, an efficient enumerative algorithm is developed. The algorithm includes an efficient procedure to solve the LP-relaxed problem, a reduction algorithm which may allow the initial fixing of some of the variables, and various other implicit enumeration criteria derived from the group problem. Extensive computational experience illustrates the efficiency of the algorithm and related results.
Keywords
Operations research, Investments--Mathematical models, Knapsack problem (Mathematics), Linear programming, Algorithms, Decision making--Mathematical models, Portfolio management--Mathematical models
Publication Title
Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 490
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Mathur, Kamlesh and Morito, Susumu, "An Efficient Algorithm for the General Multiple-Choice Knapsak Problem (GMKP)-- Algorithm Development" (1981). Research Reports from the Department of Operations. 175.
https://commons.case.edu/wsom-ops-reports/175