Méthodes de résolution pour un problème de sac-à-dos en deux dimensions

Session : PPP-1 / Placement, Partionnement, Packing
Mercredi 10 février 11:00 - 12:20 Salle : CI2-22
Quentin Viaud, François Clautiaux, Ruslan Sadykov et François Vanderbeck

Nous comparons différentes méthodes de résolution pour un problème de sac-à-dos en deux dimensions avec contrainte guillotine. Nous fixons le nombre maximum de coupes à 4 et autorisons la rotation des objets à découper. Nous utilisons une représentation par hypergraphe du problème. De cette dernière, nous présentons différentes approches exactes de résolution pour ce problème et les comparons avec les meilleures méthodes de la littérature.

Mots clés : Sac-à-dos en deux dimensions, Formulation étendue, Hypergraphe, Modèle de flot