An exact dynamic programming approach to segmented isotonic regression

Autor: Víctor Bucarey, Salvador Pineda, Martine Labbé, Juan M. Morales
Přispěvatelé: Data Analytics Laboratory, Vrije Universiteit Brussel (VUB), Integrated Optimization with Complex Structure (INOCS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université libre de Bruxelles (ULB)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Département d'informatique [Bruxelles], Université libre de Bruxelles (ULB), Department of Applied Mathematics, Universidad de Málaga [Málaga] = University of Málaga [Málaga], Department of Electrical Engineering, This research has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovationprogramme (grant agreement no. 755705). This work was also supported in part by the Spanish Ministry of Economy, Industry and Competitiveness and the European Regional Development Fund (ERDF) through project ENE2017-83775-P. Martine Labbé has been partially supported by the Fonds de la Recherche Scientifique - FNRS under Grant(s) no PDR T0098.18., European Project: 755705,FlexAnalytics(2018), University of Málaga, Université libre de Bruxelles (ULB)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)-Université de Lille-Centrale Lille-Centre National de la Recherche Scientifique (CNRS)
Jazyk: angličtina
Rok vydání: 2021
Předmět:
G.4
Mathematical optimization
Information Systems and Management
Computer science
020209 energy
Strategy and Management
0211 other engineering and technologies
isotonic regression
Context (language use)
02 engineering and technology
Management Science and Operations Research
Data clustering
Electric power system
Informatique de gestion
Análisis de regresión
FOS: Mathematics
0202 electrical engineering
electronic engineering
information engineering
Théorie de la décision et des choix collectifs
segmented regression
Inverse optimization
Mathematics - Optimization and Control
Cardinality-constrained shortest path problem
90C39
021103 operations research
consumers' price-response
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Bidding
Management
Dynamic programming
Data point
Monotone polygon
Smart grid
Segmented regression
inverse optimization
data clustering
Consumers’ price-response
Optimization and Control (math.OC)
Curve fitting
Isotonic regression
Recherche opérationnelle
Zdroj: Omega, 105
RIUMA. Repositorio Institucional de la Universidad de Málaga
instname
Omega
Omega, 2021, ⟨10.1016/j.omega.2021.102516⟩
Omega, Elsevier, 2021, ⟨10.1016/j.omega.2021.102516⟩
ISSN: 0305-0483
DOI: 10.1016/j.omega.2021.102516⟩
Popis: This paper proposes a polynomial-time algorithm to construct the monotone stepwise curve that minimizes the sum of squared errors with respect to a given cloud of data points. The fitted curve is also constrained on the maximum number of steps it can be composed of and on the minimum step length. Our algorithm relies on dynamic programming and is built on the basis that said curve-fitting task can be tackled as a shortest-path type of problem. Numerical results on synthetic and realistic data sets reveal that our algorithm is able to provide the globally optimal monotone stepwise curve fit for samples with thousands of data points in less than a few hours. Furthermore, the algorithm gives a certificate on the optimality gap of any incumbent solution it generates. From a practical standpoint, this piece of research is motivated by the roll-out of smart grids and the increasing role played by the small flexible consumption of electricity in the large-scale integration of renewable energy sources into current power systems. Within this context, our algorithm constitutes an useful tool to generate bidding curves for a pool of small flexible consumers to partake in wholesale electricity markets.
SCOPUS: ar.j
info:eu-repo/semantics/published
Databáze: OpenAIRE
Externí odkaz: