Title

The Knapsack Problem With Disjoint Multiple‐Choice Constraints

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. Copyright © 1992 Wiley Periodicals, Inc., A Wiley Company

Publication Date

1-1-1992

Publication Title

Naval Research Logistics (NRL)

Volume

39

Issue

2

Number of Pages

213-227

Document Type

Article

Identifier

scopus

Personal Identifier

scopus

DOI Link

https://doi.org/10.1002/nav.3220390206

Socpus ID

84989675145 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84989675145

This document is currently not available here.

Share

COinS