Nous présentons une extension du problème des chemins disjoints, dans laquelle des arêtes supplémentaires, dites « levées » (lifted), sont introduites afin de fournir des priorités de connectivité des chemins. Nous appelons le problème d'optimisation résultant le problème des chemins disjoints levés. Nous démontrons que ce problème est NP-dur par réduction à partir du flot multicommodité entier et de 3-SAT. Pour permettre une optimisation globale pratique, nous proposons plusieurs classes d'inégalités linéaires produisant une relaxation LP de haute qualité. En outre, nous proposons des algorithmes efficaces de séparation par plans coupants pour ces inégalités linéaires. Le problème des chemins disjoints levés constitue un modèle naturel pour le suivi d'objets multiples et permet une formulation mathématique élégante des interactions temporelles à longue portée. Les arêtes levées aident à prévenir les échanges d'identité (id switches) et à réidentifier les individus. Notre suiveur basé sur les chemins disjoints levés atteint des affectations quasi optimales par rapport aux détections d'entrée. En conséquence, il obtient de meilleurs résultats sur les trois principaux benchmarks du défi MOT, surpassant significativement les méthodes de pointe.