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
