This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Karabati, S. Articles by Yu, G. Search for Related Content

A Min-Max-Sum Resource Allocation Problem and Its Applications

College of Administrative Sciences and Economics, Koç University, Sariyer, Istanbul 80910, Turkey
Olin School of Business, Washington University, Campus Box 1133, St Louis, Missouri 63130-4899
Department of MSIS, McCombs School of Business, The University of Texas at Austin, Austin, Texas 78712
skarabati{at}ku.edu.tr
kouvelis{at}olin.wustl.edu
yu{at}uts.cc.utexas.edu

In this paper we consider a class of discrete resource-allocation problems with a min-max-sum objective function. We first provide several examples of practical applications of this problem. We then develop a branch-and-bound procedure for solving the general case of this computationally intractable problem. The proposed solution procedure employs a surrogate relaxation technique to obtain lower and upper bounds on the optimal objective function value of the problem. To obtain the multipliers of the surrogate relaxation, two alternative approaches are discussed. We also discuss a simple approximation algorithm with a tight bound. Our computational results support the effectiveness of the branch-and-bound procedure for fairly large-size problems.

Subject classifications: Resource allocation: min-max-sum resource allocation; Optimization: integer optimization, min-max optimization, robust optimization; Mathematical programming: nonlinear integer programming.
History: Received September 1995; revision received June 2000; accepted July 2000.