Du sous-problème de séparation vers celui d'intersection: nouvelles bornes duales dans la génération de colonnes

Session : GC / Génération de colonnes
Vendredi 12 février 10:30 - 11:50 Salle : CI2-07
Daniel Porumbel

Cet article porte sur le sous-problème d'intersection suivant: étant donné le programme dual de génération de colonnes et une direction duale yin R^n, trouver le maximum t tel que ty soit duale-réalisable. Ce sous-problème peut enrichir la CG classique de plusieurs façons: - on présente une preuve alternative de la borne duale de Farley (une spécialisation de la borne Lagrangienne pour le cas des coûts de colonnes unitaires). Notre preuve a deux avantages: elle peut s'appliquer sur des vecteurs y non-constraints (pas uniquement sur une solution courante), et (ii) elle construit une solution duale réalisable en plus d'une valeur - on présente une borne duale qui peut être calculée pour des coûts non-unitaires.

Mots clés : génération de colonnes, borne de Farley, intersection et séparation