Quadratic resource allocation with generalized upper bounds
Additional Document Info
In this paper we present an algorithm for solving a quadratic resource allocation problem that includes a set of generalized upper bound (GUB) constraints. The problem involves minimizing a quadratic function over one linear constraint, a set of GUB constraints, and bounded variables. GUB constraints, when added to a standard resource allocation problem, can be used to set upper limits on the amount of a resource consumed by one or more subsets of the activities. To solve the problem, we present an efficient algorithm that solves a series of quadratic knapsack subproblems and box constrained quadratic subproblems. Computational results are reported for large-scale problems with as many as 1 00 000 variables and 1 000 constraints. The computational results indicate that our algorithm is up to 4000 times faster than the general purpose nonlinear programming software LSGRG.