Title

The Knapsack-Problem With Disjoint Multiple-Choice Constraints

Authors

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