-

 

 

 




Optimization Online





 

Discrete optimization methods to fit piecewise-affine models to data points

Edoardo Amaldi(edoardo.amaldi***at***polimi.it)
Stefano Coniglio(coniglio***at***math2.rwth-aachen.de)
Leonardo Taccari(leonardo.taccari***at***polimi.it)

Abstract: Fitting piecewise affine models to data points is a pervasive task in many scientific disciplines. In this work, we address the k- Piecewise Affine Model Fitting with Pairwise Linear Separability problem (k-PAMF-PLS) where, given a set of real points and the corresponding observations, we have to partition the real domain into k pairwise linearly separable subdomains and to determine an affine submodel (function) for each of them so as to minimize the total linear fitting error w.r.t. the observations. To solve k-PAMF-PLS to optimality, we propose a mixed-integer linear programming (MILP) formulation where symmetries are broken by separating the so-called shifted column inequalities. For medium-to-large scale instances, we develop a four-step heuristic involving, among others, a point reassignment step based on the identification of critical points and a domain partition step based on multicategory linear classification. Differently from traditional approaches proposed in the literature for similar fitting problems, in our methods the domain partitioning and submodel fitting aspects are taken into account simultaneously. Computational experiments on real-world and structured randomly generated instances show that, with our MILP formulation with symmetry breaking constraints, we can solve to proven optimality many small-size instances. Our four-step heuristic turns out to provide close-to-optimal solutions for small-size instances, while allowing to tackle instances of much larger size. The experiments also show that the combined impact of the main features of our heuristic is quite substantial when compared to standard variants not including them.

Keywords: data mining; piecewise-affine model fitting; mixed-integer linear programming; heuristics

Category 1: Applications -- Science and Engineering (Data-Mining )

Category 2: Combinatorial Optimization

Category 3: Integer Programming ((Mixed) Integer Linear Programming )

Citation:

Download: [PDF]

Entry Submitted: 03/08/2015
Entry Accepted: 03/09/2015
Entry Last Modified: 03/08/2015

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society