A column generation based heuristic algorithm for piecewise linear regression. (1st June 2021)

• Record Type: Journal Article
• Authors: Tunc, Huseyin; Genç, Burkay
• Is Part Of: Expert systems with applications. Volume 171(2021)
• Publication Date: 2021-06-01
• Subjects: Data analytics -- Data fitting -- Piecewise linear regression -- Non-linear regression -- Column generation; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2020.114539
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: Piecewise linear regression problem is addressed. A column generation based heuristic is proposed. Practical and acceptably accurate solutions are achieved for large data sizes. Abstract: Piecewise linear regression is a powerful and flexible regression technique where the dataset is divided into disjoint partitions and a separate regression is computed for each partition. Here, we consider the piecewise linear regression problem where the data partitioning is performed via a fixed number of break points on a predetermined dimension. We develop a column generation heuristic based on a set partitioning formulation of the problem and evaluate its prediction performance using a mixed integer programming formulation introduced earlier as a benchmark. Our results show that the proposed heuristic displays an efficient and robust performance, and also scales up smoothly as the dataset grows.