A minimax resource allocation problem with variable resources

摘要

The problem of optimally allocating the resources to competing activities where the amounts of the resources are not only previosly given but are also to be determined subject to certain linear constraints is considered. The objective is to find such activity levels such that their weighted deviation from a prespecified target is as small as possible. A primal decomposition approach for the problem and derive an explicit formula for the piecewise affine-linear convex objective function of the upper level problem are suggested. The lower level problem is a parametric optimization problem with a bottleneck objective function. If the constraints on the amounts of the resources are all of knapsack type or if there is only one such constraint, then the upper level problem is equivalent to the lower level problem with fixed right-hand sides. In the general case, the problem can efficiently be solved by means of the level method.