A fast algorithm for quadratic resource allocation problems with nested constraints

Martijn H.H. Schoot Uiterkamp*, Johann L. Hurink, Marco E.T. Gerards

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

3 Downloads (Pure)

Abstract

We study the separable convex quadratic resource allocation problem with lower and upper constraints on nested sums of variables. This problem occurs in many applications, in particular battery scheduling within decentralized energy management (DEM) for smart grids. We present an algorithm for this problem that runs in O(nlogn) time and, in contrast to existing algorithms for this problem, achieves this time complexity using relatively simple and easy-to-implement subroutines and data structures. This makes our algorithm very attractive for real-life adaptation and implementation. Numerical comparisons of our algorithm with a subroutine for battery scheduling within an existing tool for DEM research indicates that our algorithm significantly reduces the overall execution time of the DEM system, especially when the battery is expected to be completely full or empty multiple times in the optimal schedule. Moreover, computational experiments with synthetic data show that our algorithm outperforms the currently most efficient algorithm by more than one order of magnitude. In particular, our algorithm is able to solves all considered instances with up to ten million variables in less than four minutes on a personal computer.

Original languageEnglish
Article number105451
JournalComputers and Operations Research
Volume135
Early online date30 Jun 2021
DOIs
Publication statusE-pub ahead of print/First online - 30 Jun 2021

Keywords

  • Battery
  • Energy
  • Fast algorithm
  • Nested constraints
  • Quadratic programming
  • Resource allocation
  • UT-Hybrid-D

Fingerprint

Dive into the research topics of 'A fast algorithm for quadratic resource allocation problems with nested constraints'. Together they form a unique fingerprint.

Cite this