École Nationale Supérieure de
Techniques Avancées

Abstract

The following document describes an alternative method to usual heuristic ones to build clas- sification trees. It consists in transforming the original classification problem in a Mixed Integer Optimisation (MIO) formulation. This has two main advantages : the first is that many powerful programs are dedicated to solve this kind of problem and do it very efficiently ; the second is that it allows to build the entire tree in one big step rather than building nodes recursively step by step. In a first part, the method, initially depicted by Dimitri Bertisimas and Jack Dunn, is summa- rized. The following parts are dedicated to its implementation some results and their analysis. I eventually present the results of some methods that I implemented in order to improve the original one.