×

A decomposition algorithm for nested resource allocation problems. (English) Zbl 1347.90068

Summary: We propose an exact polynomial algorithm for a resource allocation problem with convex costs and constraints on partial sums of resource consumptions, in the presence of either continuous or integer variables. No assumption of strict convexity or differentiability is needed. The method solves a hierarchy of resource allocation subproblems, whose solutions are used to convert constraints on sums of resources into new bounds for variables at higher levels. The resulting time complexity for the integer problem is \(O(n\log m\log (B/n))\), and the complexity of obtaining an \(\epsilon\)-approximate solution for the continuous case is \(O(n\log m\log (B/\epsilon))\), \(n\) being the number of variables, \(m\) the number of ascending constraints (such that \(m\leq n\)), \(\epsilon\) a desired precision, and \(B\) the total resource. This algorithm matches the best-known complexity when \(m=n\) and improves it when \(\log m=o(\log n)\). Extensive experimental analyses are presented with four recent algorithms on various continuous problems issued from theory and practice. The proposed method achieves a better performance than previous algorithms, solving all problems with up to 1 million variables in less than 1 minute on a modern computer.

MSC:

90C25 Convex programming
91B32 Resource and cost allocation (including fair division, apportionment, etc.)
52A41 Convex functions and convex programs in convex geometry
90B06 Transportation, logistics and supply chain management
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] E. D. Andersen, C. Roos, and T. Terlaky, {\it On implementing a primal-dual interior-point method for conic quadratic optimization}, Math. Program., 95 (2003), pp. 249-277. · Zbl 1030.90137
[2] G. Baxter, {\it A combinatorial lemma for complex numbers}, Ann. Math. Statist., 32 (1961), pp. 901-904. · Zbl 0119.14201
[3] T. Bektas and G. Laporte, {\it The pollution-routing problem}, Transportation Res. B Methodological, 45 (2011), pp. 1232-1250.
[4] R. E. Bellman and S. E. Dreyfus, {\it Applied Dynamic Programming}, Princeton University Press, Princeton, NJ, 1962. · Zbl 0106.34901
[5] R. Bellman, I. Glicksberg, and O. Gross, {\it The theory of dynamic programming as applied to a smoothing problem}, J. SIAM, 2 (1954), pp. 82-88. · Zbl 0058.35901
[6] E. B. Berman, {\it Resource allocation in a PERT network under continuous activity time-cost functions}, Management Sci., 10 (1964), pp. 734-745.
[7] P. Brucker, {\it An O(n) algorithm for quadratic knapsack problems}, Oper. Res. Lett., 3 (1984), pp. 163-166. · Zbl 0544.90086
[8] T. C. E. Cheng, A. Janiak, and M. Y. Kovalyov, {\it Bicriterion single machine scheduling with resource dependent processing times}, SIAM J. Optim., 8 (1998), pp. 617-630. · Zbl 0907.68113
[9] R. Deltheil, {\it Sur la théorie des probabilités géométriques}, Ph.D. thesis, 1920.
[10] M. E. Dyer and J. Walker, {\it An algorithm for a separable integer programming problem with cumulatively bounded variables}, Discrete Appl. Math., 16 (1987), pp. 135-149. · Zbl 0624.90071
[11] A. Federgruen and H. Groenevelt, {\it The greedy procedure for resource allocation problems: Necessary and sufficient conditions for optimality}, Oper. Res., 34 (1986), pp. 909-918. · Zbl 0619.90051
[12] S. Foldes and F. Soumis, {\it PERT and crashing revisited: Mathematical generalizations}, European J. Oper. Res., 64 (1993), pp. 286-294. · Zbl 0779.90039
[13] G. N. Frederickson and D. B. Johnson, {\it The complexity of selection and ranking in X + Y and matrices with sorted columns}, J. Comput. System Sci., 24 (1982), pp. 197-208. · Zbl 0478.68062
[14] D. R. Fulkerson, {\it A network flow computation for project cost curves}, Management Sci., 7 (1961), pp. 167-178. · Zbl 0995.90519
[15] H. H. Gabow and R. E. Tarjan, {\it A linear-time algorithm for a special case of disjoint set union}, J. Comput. System Sci., 30 (1985), pp. 209-221. · Zbl 0572.68058
[16] F. Hanssmann, {\it Determination of optimal capacities of service for facilities with a linear measure of inefficiency}, Oper. Res., 5 (1957), pp. 713-717. · Zbl 1414.90142
[17] H. Hashimoto, T. Ibaraki, S. Imahori, and M. Yagiura, {\it The vehicle routing problem with flexible time windows and traveling times}, Discrete Appl. Math., 154 (2006), pp. 2271-2290. · Zbl 1130.90053
[18] D. S. Hochbaum, {\it Lower and upper bounds for the allocation problem and other nonlinear optimization problems}, Math. Oper. Res., 19 (1994), pp. 390-409. · Zbl 0820.90082
[19] D. S. Hochbaum and S.-P. Hong, {\it About strongly polynomial time algorithms for quadratic optimization over submodular constraints}, Math. Program., 69 (1995), pp. 269-309. · Zbl 0844.90061
[20] D. S. Hochbaum and J. G. Shanthikumar, {\it Convex separable optimization is not much harder than linear optimization}, J. ACM, 37 (1990), pp. 843-862. · Zbl 0721.90060
[21] L. M. Hvattum, I. Norstad, K. Fagerholt, and G. Laporte, {\it Analysis of an exact algorithm for the vessel speed optimization problem}, Networks, 62 (2013), pp. 132-135. · Zbl 1338.68107
[22] T. Ibaraki and N. Katoh, {\it Resource Allocation Problems: Algorithmic Approaches}, MIT Press, Boston, MA, 1988. · Zbl 0786.90067
[23] J. E. Kelley and M. R. Walker, {\it Critical-path planning and scheduling}, in Proceedings of Eastern Joint Computer conference, New York, ACM Press, 1959, pp. 160-173.
[24] H. Lakshmanan and D. P. de Farias, {\it Decentralized resource allocation in dynamic networks of agents}, SIAM J. Optim., 19 (2008), pp. 911-940. · Zbl 1176.90460
[25] N. Maculan, C. P. Santiago, E. M. Macambira, and M. H. C. Jardim, {\it An O(n) algorithm for projecting a vector on the intersection of a hyperplane and a box in \(R^n\)}, J. Optim. Theory Appl., 117 (2003), pp. 553-574. · Zbl 1115.90397
[26] S. N. Majumdar, A. Comtet, and J. Randon-Furling, {\it Random convex hulls and extreme value statistics}, J. Statist. Phys., 138 (2010), pp. 955-1009. · Zbl 1188.82024
[27] D. G. Malcolm, J. H. Roseboom, C. E. Clark, and W. Fazar, {\it Application of a technique for research and development program evaluation}, Oper. Res., 7 (1959), pp. 646-669. · Zbl 1255.90070
[28] F. Modigliani and F. E. Hohn, {\it Production planning over time and the nature of the expectation and planning horizon}, Econometrica, 23 (1955), pp. 46-66. · Zbl 0064.39504
[29] R. D. C. Monteiro and I. Adler, {\it An extension of Karmarkar type algorithm to a class of convex separable programming problems with global linear rate of convergence}, Math. Oper. Res., 15 (1990), pp. 408-422. · Zbl 0708.90068
[30] S. Moriguchi and A. Shioura, {\it On Hochbaum’s proximity-scaling algorithm for the general resource allocation problem}, Math. Oper. Res., 29 (2004), pp. 394-397. · Zbl 1082.90099
[31] A. S. Nemirovsky and D. B. Yudin, {\it Problem Complexity and Method Efficiency in Optimization}, Wiley, New York, 1983.
[32] I. Norstad, K. Fagerholt, and G. Laporte, {\it Tramp ship routing and scheduling with speed optimization}, Transportation Res. C Emerging Technologies, 19 (2011), pp. 853-865.
[33] A. Padakandla and R. Sundaresan, {\it Power minimization for CDMA under colored noise}, IEEE Trans. Commun., 57 (2009), pp. 3103-3112.
[34] A. Padakandla and R. Sundaresan, {\it Separable convex optimization problems with linear ascending constraints}, SIAM J. Optim., 20 (2009), pp. 1185-1204. · Zbl 1198.90319
[35] M. Patriksson, {\it A survey on the continuous nonlinear resource allocation problem}, European J. Oper. Res., 185 (2008), pp. 1-46. · Zbl 1146.90493
[36] D. W. Pentico, {\it The assortment problem: A survey}, European J. Oper. Res., 190 (2008), pp. 295-309.
[37] D. R. Robinson, {\it A dynamic programming solution to cost-time tradeoff for CPM}, Management Sci., 22 (1975), pp. 158-166. · Zbl 0313.90065
[38] D. Ronen, {\it The effect of oil price on the optimal speed of ships}, J. Oper. Res. Soc., 33 (1982), pp. 1035-1040.
[39] W. Sadowski, {\it A few remarks on the assortment problem}, Management Sci., 6 (1959), pp. 13-24. · Zbl 0995.90559
[40] K. S. Srikantan, {\it A problem in optimum allocation}, Oper. Res., 11 (1963), pp. 265-273. · Zbl 0114.12002
[41] F. B. Talbot, {\it Resource-constrained project scheduling with time-resource tradeoffs: The nonpreemptive case}, Management Sci., 28 (1982), pp. 1197-1210. · Zbl 0493.90042
[42] A. Tamir, {\it Efficient algorithms for a selection problem with nested constraints and its application to a production-sales planning model}, SIAM J. Control Optim., 18 (1980), pp. 282-287. · Zbl 0434.90067
[43] R. E. Tarjan, {\it Efficiency of a good but not linear set union algorithm}, J. ACM, 22 (1975), pp. 215-225. · Zbl 0307.68029
[44] A. F. Veinott, {\it Production planning with convex costs: A parametric study}, Management Sci., 10 (1964), pp. 441-460.
[45] Z. Wang, {\it On solving convex optimization problems with linear ascending constraints}, Optim. Lett., 9 (2015), pp. 819-838. · Zbl 1328.90108
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.