LP relaxation of the two dimensional knapsack problem with box and GUB constraints

LP relaxation of the two dimensional knapsack problem with box and GUB constraints

0.00 Avg rating0 Votes
Article ID: iaor19982457
Country: Netherlands
Volume: 89
Issue: 3
Start Page Number: 609
End Page Number: 617
Publication Date: Mar 1996
Journal: European Journal of Operational Research
Authors: , ,
Keywords: mineral industries, engineering
Abstract:

In the present paper we derive an O(n2 log n) algorithm for the linear programming (LP) relaxation of the two dimensional knapsack problem with box and generalized upper bound (GUB) constraints. The two dimensional linear knapsack problem with box constraints and GUBs generalizes the multiple choice linear knapsack problem considered by Dyer and others. The problem arose in an application in a steel tube rolling mill in India.

Reviews

Required fields are marked *. Your email address will not be published.