LP RELAXATION OF THE 2-DIMENSIONAL KNAPSACK-PROBLEM WITH BOX AND GUB CONSTRAINTS

Authors
BAGCHI A BHATTACHARYYA N CHAKRAVARTI N
Citation
A. Bagchi et al., LP RELAXATION OF THE 2-DIMENSIONAL KNAPSACK-PROBLEM WITH BOX AND GUB CONSTRAINTS, European journal of operational research, 89(3), 1996, pp. 609-617
Citations number
10
Categorie Soggetti
Management,"Operatione Research & Management Science
Journal title
European journal of operational research → ACNP
ISSN journal
03772217
Volume
89
Issue
3
Year of publication
1996
Pages
609 - 617
Database
ISI
SICI code
0377-2217(1996)89:3<609:LROT2K>2.0.ZU;2-#
Abstract
In the present paper we derive an O(n(2) log n) algorithm for the line ar programming (LP) relaxation of the two dimensional knapsack problem with box and generalized upper bound (GUB) constraints. The two dimen sional linear knapsack problem with box constraints and GUB's generali zes the multiple choice linear knapsack problem considered by Dyer and others. The problem arose in an application in a steel tube rolling m ill in India.