Abstract

This paper presents methods for solving allocation problems that can be stated as convex knapsack problems with generalized upper bounds. Such bounds may express upper limits on the total amount allocated to each of several subsets of activities. In addition our model arises as a subproblem in more complex mathematical programs. We therefore emphasize efficient procedures to recover optimality when minor changes in the parameters occur from one problem instance to the next. These considerations lead us to propose novel data structures for such problems. Also, we introduce an approximation method to solve certain equations, which arise during the procedures.

Authors
Awi Federgruen and Paul Zipkin
Format
Journal Article
Publication Date
Journal
Mathematical Programming

Full Citation

Federgruen, Awi and Paul Zipkin
. “Solution techniques for some allocation problems.”
Mathematical Programming
vol.
25
, (January 01, 1983):
13
-
24
.