An 0(n(log n + log m)) Algorithm for LP Knapsacks with GUB Constraints.

A specialization of the dual simplex method is developed for solving the linear programming LP knapsack problem subject to generalized upper bound GUB constraints. The LPGUB knapsack problem is of interest both for solving more general LP problems by the dual simplex method, and for applying surrogate constraint strategies to the solution of 0-1 Multiple Choice integer programming problems. Computational bounds are provided for this method of 0nlog n log m, where n is the total number of problem variables and m is the number of GUB sets. In the commonly encountered situation where the number of variables in each GUB set is the same, our bound becomes 0n log n. These bounds reduce the previous best estimate of the order of complexity of the LPGUB knapsack problem and provide connections to computational bounds for the ordinary knapsack problem.