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 Politecnico di Milano. The written in English available from author upon request. In this work, we extensively study two challenging variants general problem clustering given set data points with respect to hyperplanes so as extract collinearity between them. After pointing out similarities differences previous work related problems, propose mathematical programming formulations for our variants. Since these problems are difficult handle due nonlinear nonconvexity that arises because l2-norm distance function large number binary assignment variables, develop column generation algorithms heuristics tackle efficiency methods developed demonstrated realistic randomly generated instances along applications piecewise linear model fitting line segment detection digital images.