Optimization models and algorithms for the hyperplane clustering problem

This is a summary of the author's PhD thesis supervised by Edoardo Amaldi and defended on 3 April 2009 at the Politecnico di Milano. The thesis is written in English and is available from the author upon request. In this work, we extensively study two challenging variants of the general problem of clustering a given set of data points with respect to hyperplanes so as to extract collinearity between them. After pointing out the similarities and differences with previous work on related problems, we propose mathematical programming formulations for our problem variants. Since these problems are difficult to handle due to the nonlinear nonconvexity that arises because of the l 2-norm in the distance function and a large number of binary assignment variables, we develop column generation algorithms and heuristics to tackle them. The efficiency of the methods developed is demonstrated on realistic randomly generated instances along with applications in piecewise linear model fitting and line segment detection in digital images.