Generating optimal robust continuous piecewise linear regression with outliers through combinatorial Benders decomposition

John Alasdair Warwicker and Steffen Rebennack

IISE Transactions, 2023, vol. 55, issue 8, 755-767

Abstract: Using piecewise linear (PWL) functions to model discrete data has applications for example in healthcare, engineering and pattern recognition. Recently, mixed-integer linear programming (MILP) approaches have been used to optimally fit continuous PWL functions. We extend these formulations to allow for outliers. The resulting MILP models rely on binary variables and big-M constructs to model logical implications. The combinatorial Benders decomposition (CBD) approach removes the dependency on the big-M constraints by separating the MILP model into a master problem of the complicating binary variables and a linear sub problem over the continuous variables, which feeds combinatorial solution information into the master problem. We use the CBD approach to decompose the proposed MILP model and solve for optimal PWL functions. Computational results show that vast speedups can be found using this robust approach, with problem-specific improvements including smart initialization, strong cut generation and special branching approaches leading to even faster solve times, up to more than 12,000 times faster than the standard MILP approach.

Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/24725854.2022.2107249 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:uiiexx:v:55:y:2023:i:8:p:755-767

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/24725854.2022.2107249

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().