École Nationale Supérieure de
Techniques Avancées

Résumé

Ce document décrit une méthode de construction d’arbre de classification, alternative aux mé- thodes heuristiques classiques. Elle consiste à transformer la formulation originelle du problème en un Programme Linéaire en Nombres Entiers. Cette nouvelle formulation ayant deux avantages importants : beaucoup de solveurs sont dédiés à la résolution de ce genre de problème et le font de façon très optimisée ; l’arbre peut être construit en une unique étape, permettant de palier la dépendance entre un noeud et les noeuds construits précédemment des les méthodes récursives. Dans une première partie, la méthode initialement décrite par Dimitri Bertisimas et Jack Dunn est traduite et synthétisée. Une seconde partie est dédiée à son implémention et à la description des principaux résultats obtenus. Finalement, je présente les résultats obtenus pour des tentatives d’améliorations basées sur l’analyse des résultats précédemment évoqués.