An efficient alorithm for the general multiple-choice knapsack problem (GMKP)

K. Mathur*, H. M. Salkin, S. Morito

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    3 Citations (Scopus)


    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.

    Original languageEnglish
    Pages (from-to)253-283
    Number of pages31
    JournalAnnals of Operations Research
    Issue number1
    Publication statusPublished - 1985 Dec


    • capital budgeting
    • general multiple-choice knapsack problem
    • integer programming
    • knapsack problem
    • Mathematical programming

    ASJC Scopus subject areas

    • Management Science and Operations Research
    • General Decision Sciences


    Dive into the research topics of 'An efficient alorithm for the general multiple-choice knapsack problem (GMKP)'. Together they form a unique fingerprint.

    Cite this