The Knapsack-Problem With Disjoint Multiple-Choice Constraints

    Authors

    V. Aggarwal; N. Deo;D. Sarkar

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    Nav. Res. Logist.

    Keywords

    ALGORITHM; Operations Research & Management Science

    Abstract

    In this article we consider the binary knapsack problem under disjoint multiple-choice constraints. We propose a two-stage algorithm based on Lagrangian relaxation. The first stage determines in polynomial time an optimal Lagrange multiplier value, which is then used within a branch-and-bound scheme to rank-order the solutions, leading to an optimal solution in a relatively low depth of search. The validity of the algorithm is established, a numerical example is included, and computational experience is described.

    Journal Title

    Naval Research Logistics

    Volume

    39

    Issue/Number

    2

    Publication Date

    1-1-1992

    Document Type

    Article

    Language

    English

    First Page

    213

    Last Page

    227

    WOS Identifier

    WOS:A1992HF39100005

    ISSN

    0894-069X

    Share

    COinS