A lexicographic minimax algorithm for multiperiod resource allocation

A lexicographic minimax algorithm for multiperiod resource allocation

0.00 Avg rating0 Votes
Article ID: iaor1993741
Country: Netherlands
Volume: 55
Issue: 2
Start Page Number: 213
End Page Number: 234
Publication Date: Jun 1992
Journal: Mathematical Programming (Series A)
Authors: , ,
Keywords: allocation: resources
Abstract:

Resource allocation problems are typically formulated as mathematical programs with some special structure that facilitates the development of efficient algorithms. The authors consider a multiperiod problem in which excess resources in one period can be used in subsequent periods. The objective minimizes lexicographically the nonincreasingly sorted vector of weighted deviations of cumulative activity levels from cumulative demands. To this end, the authors first develop a new minimax algorithm that minimizes the largest weighted deviation among all cumulative activity levels. The minimax algorithm handles resource constraints, ordering constraints, and lower and upper bounds. At each iteration, it fixes certain variables at their lower bounds, and sets groups of other variables equal to each other as long as no lower bounds are violated. The algorithm takes advantage of the problem’s special structure; e.g., each term in the objective is a linear decreasing function of only one variable. This algorithm solves large problems very fast, orders of magnitude faster than well known linear programming packages. (The latter are, of course, not designed to solve such minimax problems efficiently.) The lexicographic procedure repeatedly employs the minimax algorithm described above to solve problems, each of the same format but with smaller dimension.

Reviews

Required fields are marked *. Your email address will not be published.