×

A nonlinear minimax allocation problem with multiple knapsack constraints. (English) Zbl 0749.90073

A nonlinear allocation problem is considered. The minimax objective is described by
\(\min\max_ j f_ j(x_ j)\) (\(f_ j\) are strictly decreasing, continuous functions) and the feasible domain is given by linear inequalities with only nonnegative coefficients. The presented new algorithm determines the optimal set of activities without having to solve nonlinear equations.
Reviewer: R.Nehse (Ilmenau)

MSC:

90C30 Nonlinear programming
49J35 Existence of solutions for minimax problems
91B32 Resource and cost allocation (including fair division, apportionment, etc.)
90B30 Production models
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C06 Large-scale problems in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brown, J. R., The knapsack sharing problem, Operations Research, 27, 341-355 (1979) · Zbl 0394.90065
[2] Brown, J. R., The flow circulation sharing problem, Mathematical programming, 25, 199-227 (1983) · Zbl 0507.90026
[3] Brown, J. R., Sharing (maximin and minimax) constrained optimization, (Working Paper (1989), Graduate School of Management, Kent State University: Graduate School of Management, Kent State University Kent, OH)
[4] J.R. Brown, “Solving knapsack sharing with general tradeoff functions”, Mathematical Programming; J.R. Brown, “Solving knapsack sharing with general tradeoff functions”, Mathematical Programming · Zbl 0733.90064
[5] Czuchra, W., A graphical method to solve a maximin allocation problem, European Journal of Operational Research, 26, 259-261 (1986) · Zbl 0597.90080
[6] Eislet, H. A., Continuous maximin knapsack problems with GLB constraints, Mathematical Programming, 36, 114-121 (1986) · Zbl 0625.90055
[7] Ibaraki, T.; Katoh, N., Resource Allocation Problems: Algorithmic Approaches (1988), MIT Press: MIT Press Cambridge, MA · Zbl 0786.90067
[8] Kaplan, S., Application of programs with maximin objective functions to problems of optimal resource allocation, Operations Research, 22, 802-807 (1974) · Zbl 0282.90048
[9] King, J. H., Allocation of scarce resources in manufacturing facilities, AT&T Technical Journal, 68, 3, 103-113 (1989)
[10] Klein, R. S.; Luss, H., Minimax resource allocation with tree structured substitutable resources, Operations Research, 39 (1991) · Zbl 0728.90078
[11] Luss, H., An algorithm for separable nonlinear minimax problems, Operations Research Letters, 6, 159-162 (1987) · Zbl 0628.90071
[12] H. Luss, “Minimax resource allocation problems: Optimization and parametric analysis”, European Journal of Operational Research; H. Luss, “Minimax resource allocation problems: Optimization and parametric analysis”, European Journal of Operational Research · Zbl 0773.90046
[13] Luss, H.; Gupta, S. K., Allocation of effort among competing activities, Operations Research, 23, 360-366 (1975) · Zbl 0298.90015
[14] Luss, H.; Smith, D. R., Resource allocation among competing activities: A lexicographic minimax approach, Operations Research Letters, 5, 227-231 (1986) · Zbl 0627.90068
[15] Mendelson, H.; Pliskin, S.; Yechiali, U., Optimal storage allocation for serial files, Communications of the ACM, 22, 124-130 (1979) · Zbl 0393.68024
[16] Mjelde, K. M., Max-min resource allocation, BIT, 23, 529-537 (1983) · Zbl 0527.90099
[17] Tang, C. S., A max-min allocation problem: Its solutions and applications, Operations Research, 36, 359-367 (1988) · Zbl 0648.90032
[18] Zipkin, P., Simple ranking methods for allocation of one resource, Management Science, 26, 34-43 (1980) · Zbl 0448.90049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.