KIT | KIT-Bibliothek | Impressum | Datenschutz

MINLP formulations for continuous piecewise linear function fitting

Goldberg, Noam; Rebennack, Steffen; Kim, Youngdae; Krasko, Vitaliy; Leyffer, Sven

Abstract:
We consider a nonconvex mixed-integer nonlinear programming (MINLP) model proposed by Goldberg et al. (Comput Optim Appl 58:523–541, 2014. https://doi.org/10.1007/s10589-014-9647-y) for piecewise linear function fitting. We show that this MINLP model is incomplete and can result in a piecewise linear curve that is not the graph of a function, because it misses a set of necessary constraints. We provide two counterexamples to illustrate this effect, and propose three alternative models that correct this behavior. We investigate the theoretical relationship between these models and evaluate their computational performance.

Open Access Logo


Verlagsausgabe §
DOI: 10.5445/IR/1000130928
Veröffentlicht am 25.03.2021
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Operations Research (IOR)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2021
Sprache Englisch
Identifikator ISSN: 0926-6003, 1573-2894
KITopen-ID: 1000130928
Erschienen in Computational Optimization and Applications
Verlag Springer
Schlagwörter Mixed-integer nonlinear program; Linear spline regression; Branch-and-bound; Reformulation
Nachgewiesen in Scopus
Web of Science
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page