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 LP/GUB 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 0(n(log 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 0(n log n). These bounds reduce the previous best estimate of the order of complexity of the LP/GUB knapsack problem and provide connections to computational bounds for the ordinary knapsack problem.