Un solveur efficace pour les flots entiers dans les hypergraphes de décision avec des applications aux problèmes de sac à dos orthogonaux

On s'intéresse au problème de maximiser la valeur d'un flot dans un hypergraphe de décision. Ce formalisme permet de modéliser toute une classe de problèmes de découpe guillotine, en particulier le problème du sac à dos guillotine 2D. Je présenterai notre algorithme de résolution, basé sur un algorithme d'étiquettes muni de bornes supérieures améliorées, issues de la programmation linéaire.

En particulier, je rappellerai la méthodologie de génération d'hyperarcs déjà introduite dans la littérature qui permet de résoudre le LP très rapidement en pratique sur de grosses instances, puis je présenterai nos inégalités valides, ainsi qu'une manière dont les bornes peuvent être incluses dans un algorithme d'étiquettes. Je présenterai également les résultats expérimentaux, qui démontrent l'efficacité de notre algorithme par rapport aux autres méthodes proposées dans la littérature.