An O(n2logn) algorithm for the linear knapsack problem with SUB and extended GUB constraints

We present an extension of the well-known generalized upper bound (GUB) constraint and consider a linear knapsack problem with both the extended GUB constraints and the simple upper bound constraints. An efficient algorithm of order O(n²logn) is developed by exploiting structural properties and applying binary search to ordered solution sets, where n is the total number of variables. A numerical example is presented.