Continuous maximin knapsack problems with GLB constraints.(English)Zbl 0625.90055
The author proposes an O(n log n) time algorithm for solving the problem \[ \max \min \{c_ jx_ j\},\quad \Sigma a_ jx_ j<b,\quad x_ j\geq 0, \]
\[ x\in \cap_{k}P_ k\text{ where } P_ k=\{x: \sum_{j\in J_ k}x_ j>1_ k,\quad k=1,\quad...,\quad t\}. \] A subproblem with one constraint \(x\in P_ k\) may be solved analytically. A solution of the main problem may be found by simple analysis of the solutions of subproblems. A subproblem with constraint \(\sum_{j\in J_ k}x_ j<1_ k\) may be solved in linear time.
\[ x\in \cap_{k}P_ k\text{ where } P_ k=\{x: \sum_{j\in J_ k}x_ j>1_ k,\quad k=1,\quad...,\quad t\}. \] A subproblem with one constraint \(x\in P_ k\) may be solved analytically. A solution of the main problem may be found by simple analysis of the solutions of subproblems. A subproblem with constraint \(\sum_{j\in J_ k}x_ j<1_ k\) may be solved in linear time.
Reviewer: M.Frumkin
MSC:
| 90C08 | Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
Cite
Full Text:DOI
References:
| [1] | M.E. Dyer, ”An O(n) algorithm for the multiple-choice knapsack linear program,”Mathematical Programming 29 (1984) 57–63. ·Zbl 0532.90068 ·doi:10.1007/BF02591729 |
| [2] | H.A. Eiselt, ”Maximin knapsack problems,” in: M. Breton, ed.,Proceedings of the 1984 ASAC Conference: Management Science/Recherche Opérationelle (1984) 6–18. |
| [3] | F. Glover and D. Klingman, ”An O(n logn) algorithm forLP knapsacks with GUB constraints,”Mathematical Programming 17 (1979) 345–361. ·Zbl 0421.90050 ·doi:10.1007/BF01588255 |
| [4] | T. Ibaraki, T. Hasegawa, K. Teranaka and J. Iwase, ”The multiple choice knapsack problem,”Journal of the Operations Research Society of Japan 21 (1978) 59–95. ·Zbl 0379.90076 |
| [5] | T. Ichimori, ”On min-max integer allocation problems,”Operations Research 32 (1984) 449–450. ·Zbl 0536.90066 ·doi:10.1287/opre.32.2.449 |
| [6] | E.L. Johnson and M.W. Padberg, ”A note on the knapsack problem with special ordered sets,”Operations Research Letters 1 (1981) 18–22. ·Zbl 0493.90062 ·doi:10.1016/0167-6377(81)90019-5 |
| [7] | S. Kaplan, ”Application of programs with maximin objective functions to problems of optimal resource allocation,”Operations Research 22 (1974) 802–807. ·Zbl 0282.90048 ·doi:10.1287/opre.22.4.802 |
| [8] | M.E. Posner and C.-T. Wu, ”Linear max-min programming,”Mathematical Programming 20 (1981) 166–172. ·Zbl 0456.90066 ·doi:10.1007/BF01589343 |
| [9] | P. Sinha and A. Zoltners, ”The multiple choice knapsack problem,”Operations Research 27 (1979) 503–515. ·Zbl 0406.90052 ·doi:10.1287/opre.27.3.503 |
| [10] | E. Zemel, ”The linear multiple choice knapsack problem,”Operations Research 28 (1980) 1412–1423. ·Zbl 0447.90064 ·doi:10.1287/opre.28.6.1412 |
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.
