Quadratic resource allocation with generalized upper bounds Academic Article uri icon

abstract

  • 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.

published proceedings

  • Operations Research Letters

author list (cited authors)

  • Bretthauer, K. M., & Shetty, B.

citation count

  • 36

complete list of authors

  • Bretthauer, Kurt M||Shetty, Bala

publication date

  • February 1997