Pénaliser les directions fractionnaires dans le simplexe en nombres entiers. Application au transport aérien.

Session : PPP-3 / Placement, Partionnement, Packing
Jeudi 11 février 15:00 - 16:40 Salle : CI2-22
Samuel Rosat, Frédéric Quesnel, François Soumis et Issmail Elhallaoui

Le problème de partitionnement est un modèle linéaire en nombres entiers populaire en optimisation car il permet de représenter de nombreux problèmes industriels, notamment ceux d'horaires de personnel ou de véhicules. La structure de son domaine réalisable présente des caractéristiques originales. En particulier, il existe une suite de solutions entières de coût décroissant et menant à une solution optimale, telle que chacune d'elles est un sommet du polyèdre voisin de la précédente. Parmi les algorithmes construits à partir de cette observation se trouve le simplexe en nombres entiers avec décomposition. Dans cet algorithme, la nouvelle solution est généralement obtenue grâce à la résolution d'un programme linéaire sans faire appel à une stratégie de branchement. Nous étudions l'influence de la contrainte de normalisation de ce problème sur l'intégralité de la prochaine solution. Nous proposons de nouveaux choix de normalisation visant à pénaliser les directions menant vers des solutions fractionnaires. Nous développons aussi des méthodes de modification dynamique de la contrainte de normalisation qui font augmenter le taux de directions entières trouvées. Les résultats numériques obtenus démontrent la pertinence de notre approche et permettent de faire passer le taux de problèmes résolus de 78% à presque 100%.

Mots clés : problème de partitionnement, algorithmes primaux, méthodes d'augmentation, normalisation, planification de personnel