Résolution de problèmes de bin packing à une dimension par la programmation DC

Abstract

Nous traitons dans ce travail le problème de bin packing à une dimension (avec et sans coflits) par une méthode exacte de branch & bound et de programmation DC. Le pro- blème de bin packing à une dimension sans conflits consiste à ranger des objets ayant des tailles données dans un minimum de bins (boites) de capacités limitées. Dans la version avec conflits, on ne peut ranger un objet donné dans un même bin qu'un autre avec lequel il est en conflit, le but reste toujours de ranger tous les objets dans un minimum de bins. Le problème ainsi posé est clairement combinatoire, il est de plus NP-complet. Plusieurs approches existent : heuristiques, métaheuristiques, algorithmes exacts. Notre approche s'inscrit dans cette dernière. Nous formu- lons tout d'abord le problème sous forme d'un PL01 (formulation de Kantorovitch), puis nous le reformulons sous forme d'un programme quadratique concave et enfin comme programme DC, la solution optimale se trouve alors être le minimum global du programme DC. Pour la résolution du problème, nous utilisons un algorithme de Branch & Bound issu de l'optimisation discrète coupé à l'algorithme DCA issu de la programmation DC