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

Selcuk Karabati (), Panagiotis Kouvelis () and Gang Yu ()
Additional contact information
Selcuk Karabati: College of Administrative Sciences and Economics, Koç University, Sariyer, Istanbul 80910, Turkey
Panagiotis Kouvelis: Olin School of Business, Washington University, Campus Box 1133, St Louis, Missouri 63130-4899
Gang Yu: Department of MSIS, McCombs School of Business, The University of Texas at Austin, Austin, Texas 78712

Operations Research, 2001, vol. 49, issue 6, 913-922

Abstract: 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.

Keywords: Resource allocation: min-max-sum resource allocation; Optimization: integer optimization; min-max optimization; robust optimization; Mathematical programming: nonlinear integer programming (search for similar items in EconPapers)
Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.49.6.913.10023 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:49:y:2001:i:6:p:913-922

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().