A Class of Convex Quadratic Nonseparable Resource Allocation Problems with Generalized Bound Constraints

References

• Alexandrescu A (2017) Fast deterministic selection. Raman CSI, Pissis SP, Puglisi SJ, Rajeev, eds. Leibniz Internat. Proc. in Informatics, vol. 75, (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 24:1–24:9.Google Scholar
• Bakker H, Dunke F, Nickel S (2020) A structuring review on multi-stage optimization under uncertainty: Aligning concepts from theory and practice. Omega 96:102080.Google Scholar
• Bartlett MS (1951) An inverse matrix adjustment arising in discriminant analysis. Ann. Math. Statist. 22(1):107–111.Google Scholar
• Beaudin M, Zareipour H (2015) Home energy management systems: A review of modelling and complexity. Renewable Sustainable Energy Rev. 45:318–335.Google Scholar
• Blum M, Floyd RW, Pratt V, Rivest RL, Tarjan RE (1973) Time bounds for selection. J. Comput. Systems Sci. 7(4):448–461.Google Scholar
• Boyd S, Vandenberghe L (2004) Convex Optimization, 7th ed. (Cambridge University Press, Cambridge, UK).Google Scholar
• Bretthauer KM, Shetty B (1997) Quadratic resource allocation with generalized upper bounds. Oper. Res. Lett. 20(2):51–57.Google Scholar
• Bretthauer KM, Shetty B (2002) A pegging algorithm for the nonlinear resource allocation problem. Comput. Oper. Res. 29(5):505–527.Google Scholar
• Cominetti R, Mascarenhas WF, Silva PJS (2014) A Newton’s method for the continuous quadratic knapsack problem. Math. Programming Comput. 6(2):151–169.Google Scholar
• De Waegenaere A, Wielhouwer JL (2012) A breakpoint search approach for convex resource allocation problems with bounded variables. Optim. Lett. 6(4):629–640.Google Scholar
• Deshpande JG, Kim E, Thottan M (2011) Differentiated services QoS in smart grid communication networks. Bell Labs Tech. J. 16(3):61–81.Google Scholar
• Electric Vehicle Database (2020) Tesla model 3 standard range price and specifications: EV database. Accessed March 4, 2020, https://ev-database.org/car/1060/Tesla-Model-3-Standard-Range.Google Scholar
• Engle R, Kelly B (2012) Dynamic equicorrelation. J. Bus. Econom. Statist. 30(2):212–228.Google Scholar
• Esther BP, Kumar KS (2016) A survey on residential demand side management architecture, approaches, optimization models and methods. Renewable Sustainable Energy Rev. 59:342–351.Google Scholar
• Fujishige S (1984) Structures of polyhedra determined by submodular functions on crossing families. Math. Programming 29(2):125–141.Google Scholar
• Gan L, Topcu U, Low SH (2013) Optimal decentralized protocol for electric vehicle charging. IEEE Trans. Power Systems 28(2):940–951.Google Scholar
• Gerards MET, Toersche HA, Hoogsteen G, van der Klauw T, Hurink JL, Smit GJM (2015) Demand side management using profile steering. Proc. IEEE Eindhoven PowerTech (IEEE, Piscataway, NJ), 457759:1–457759:6.Google Scholar
• Gondzio J (2012) Interior point methods 25 years later. Eur. J. Oper. Res. 218(3):587–601.Google Scholar
• Harville DA (1997) Matrix Algebra from a Statistician’s Perspective, 1st ed. (Springer Verlag, New York).Google Scholar
• He P, Zhao L, Zhou S, Niu Z (2013) Water-filling: A geometric approach and its application to aolve generalized radio resource allocation problems. IEEE Trans. Wireless Comm. 12(7):3637–3647.Google Scholar
• Helgason R, Kennington J, Lall H (1980) A polynomially bounded algorithm for a singly constrained quadratic program. Math. Programming 18(1):338–343.Google Scholar
• Hochbaum DS (1994) Lower and upper bounds for the allocation problem and other nonlinear optimization problems. Math. Oper. Res. 19(2):390–409.Link, Google Scholar
• Hochbaum DS, Hong SP (1995) About strongly polynomial time algorithms for quadratic optimization over submodular constraints. Math. Programming 69:269–309.Google Scholar
• Hoogsteen G, Hurink JL, Smit GJM (2019) DEMKit: A decentralized energy management simulation and demonstration toolkit. Proc. IEEE PES Innovative Smart Grid Technologies Europe (IEEE, Piscataway, NJ), 1–5.Google Scholar
• Hoogsteen G, Molderink A, Hurink JL, Smit GJ, Kootstra B, Schuring F (2017) Charging electric vehicles, baking pizzas, and melting a fuse in Lochem. CIRED Open Access Proc. J. 2017(1):1629–1633.Google Scholar
• Ibaraki T, Katoh N (1988) Resource Allocation Problems: Algorithmic Approaches, 1st ed. (MIT Press, Cambridge, MA).Google Scholar
• Katoh N, Shioura A, Ibaraki T (2013) Resource allocation problems. Pardalos PM, Du DZ, Graham RL, eds. Handbook of Combinatorial Optimization (Springer, New York), 2897–2988.Google Scholar
• Kiwiel KC (2007) Breakpoint searching algorithms for the continuous quadratic knapsack problem. Math. Programming 112(2):473–491.Google Scholar
• Kiwiel KC (2008) Variable fixing algorithms for the continuous quadratic knapsack problem. J. Optim. Theory Appl. 136(3):445–458.Google Scholar
• Knuth DE (1998) Sorting and searching. The Art of Computer Programming, vol. 3, 2nd ed. (Addison-Wesley, Reading, MA), 722.Google Scholar
• Kuphaldt TR (2007) Polyphase AC circuits. Lessons In Electric Circuits, 6th ed., 283–346.Google Scholar
• Ledoit O, Wolf M (2003) Improved estimation of the covariance matrix of stock returns with an application to portfolio selection. J. Empirical Finance 10(5):603–621.Google Scholar
• Markowitz H (1952) Portfolio selection. J. Finance 7(1):77–91.Google Scholar
• Megiddo N, Tamir A (1993) Linear time algorithms for some separable quadratic programming problems. Oper. Res. Lett. 13(4):203–211.Google Scholar
• Moriguchi S, Shioura A, Tsuchimura N (2011) M-convex function minimization by continuous relaxation approach: proximity theorem and algorithm. SIAM J. Optim. 21(3):633–668.Google Scholar
• MOSEK-ApS (2019) MOSEK optimizer API for Python, release 9.1.13. (MOSEK-ApS, Copenhagen, Denmark).Google Scholar
• Mou Y, Xing H, Lin Z, Fu M (2015) Decentralized optimal demand-side management for PHEV charging in a smart grid. IEEE Trans. Smart Grid 6(2):726–736.Google Scholar
• Nagano K, Aihara K (2012) Equivalence of convex minimization problems over base polytopes. Japan J. Industrial Appl. Math. 29(3):519–534.Google Scholar
• Patriksson M (2008) A survey on the continuous nonlinear resource allocation problem. Eur. J. Oper. Res. 185(1):1–46.Google Scholar
• Patriksson M, Strömberg C (2015) Algorithms for the continuous nonlinear resource allocation problem: New implementations and numerical studies. Eur. J. Oper. Res. 243(3):703–722.Google Scholar
• Sahni S (1974) Computationally related problems. SIAM J. Comput. 3(4):262–279.Google Scholar
• Schoot Uiterkamp MHH (2016) Robust planning of electric vehicle charging. MSc thesis, University of Twente, Enschede, Netherlands.Google Scholar
• Schoot Uiterkamp MHH, Gerards MET, Hurink JL (2020) ODDO: Online duality-driven optimization. Preprint, submitted August 22, https://arxiv.org/abs/2008.09838.Google Scholar
• Schoot Uiterkamp MHH, Gerards MET, Hurink JL (2022) On a reduction for a class of resource allocation problems. INFORMS J. Comput. Forthcoming.Google Scholar
• Schoot Uiterkamp MHH, Hoogsteen G, Gerards MET, Hurink JL, Smit GJM (2017) Multi-commodity support in profile steering. Proc. IEEE PES Innovative Smart Grid Technologies Conf. Europe (IEEE, Piscataway, NJ), 1–6.Google Scholar
• Schoot Uiterkamp MHH, Hurink JL, Gerards MET (2021) A fast algorithm for quadratic resource allocation problems with nested constraints. Comput. Oper. Res. 135:105451.Google Scholar
• Shams F, Bacci G, Luise M (2014) A survey on resource allocation techniques in OFDM(A) networks. Comput. Networks 65:129–150.Google Scholar
• Siano P (2014) Demand response and smart grids: A survey. Renewable Sustainable Energy Rev. 30:461–478.Google Scholar
• Spedicato E (1975) A bound to the condition number of canonical rank-two corrections and applications to the variable metric method. Calcolo 12(2):185–199.Google Scholar
• Stevenson WD (1975) Elements of Power System Analysis, 3rd ed. (McGraw Hill, New York).Google Scholar
• Tamir A (1993) A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks. Math. Programming 59(1):117–132.Google Scholar
• van der Klauw T, Gerards MET, Hurink JL (2017) Resource allocation problems in decentralized energy management. OR Spectrum 39(3):749–773.Google Scholar
• Végh L (2016) A strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives. SIAM J. Comput. 45(5):1729–1761.Google Scholar
• Vidal T, Gribel D, Jaillet P (2019) Separable convex optimization with nested lower and upper constraints. INFORMS J. Optim. 1(1):71–90.Link, Google Scholar
• Weckx S, Driesen J (2015) Load balancing with EV chargers and PV inverters in unbalanced distribution grids. IEEE Trans. Sustainable Energy 6(2):635–643.Google Scholar
• Wright SE, Lim S (2020) Solving nested-constraint resource allocation problems with an interior point method. Oper. Res. Lett. 48(3):297–303.Google Scholar
• Wright SE, Rohal JJ (2014) Solving the continuous nonlinear resource allocation problem with an interior point method. Oper. Res. Lett. 42(6):404–408.Google Scholar