Program > By speacker > Porumbel Daniel

De point de vue dual, la génération de colonnes fonctionne comme une
méthode à base de plans sécants (e.g., "Kelley's cutting plane") dans le polytope dual
P. Pour ajouter itérativement des contraintes duales (colonnes), la
génération de colonnes fait appel à un sous-problème de séparation sur P. On
propose une méthode qui permet d'optimiser P en faisant appel à un
sous-problème d'intersection au lieu du sous-problème de séparation.

Le sous-problème d'intersection demande d'avancer sur la
direction 0->r d'un "rayon" r jusqu'au moment où on intersecte une facette de
P. Plus formellement, étant donné un solution (faisable ou non) r de l'espace dual,
il faut déterminer:
(i) la valeur maximale d'un scalaire t que tr ∈ P,
(ii) une contrainte de P satisfaite avec égalité par tr (i.e., la première
facette de P intersectée en avançant sur la direction r).

Le premier rayon r est la fonction objectif duale: on démarre dans la direction
 avec le plus fort taux d'augmentation de la fonction objectif. Pour converger, la
méthode génère une séquence de rayons (directions), qui se rapprochent
itérativement d'une direction optimale (vers l'optimum du P).

Des résultats numériques seront présentés pour deux problèmes: Cutting-Stock et Arc-Routing.
La nouvelle méthode offre des avantages:

- à chaque itération, le sous-problème d'intersection détermine
une solution dual réalisable et une borne duale. La construction de
ces bornes est différente de celle des bornes Lagrangiennes.

- plus de flexibilité dans le choix de rayons r, ce qui peut rendre le sous-problème d'intersection
même plus facile que celui de séparation. L'idée de base
est la suivante: en utilisant que des valeurs entières r en entrée, même
un sous-problème NP-dur peut devenir "vulnérable" à la programmation
dynamique. Pour résoudre un sous-problème d'intersection, il faut trouver une configuration (pattern, route) a qui
minimise ca/a•r, où ca est le cout de la configuration a (i.e., le coefficient de la fonction objectif
dans la colonne) et "•" est le produit scalaire. Les états peuvent être indexés par des "profits" entiers de forme a•r
(l'idée est utilisée aussi dans des FPTAS pour le sac-à-dos).

Rappelons le sous-problème de génération de colonnes: ca-a•y, où y
est généralement une solution extérieure à P, e.g, l'optimum
du polytope P'⊃P à l'itération courante, ou bien l'optimum d'un programme stabilisé [1].
Par contre, r peut souvent être une solution intérieure du P dans notre
méthode. Pour accélérer la convergence, le plus important est d'avoir une technique pour générer des rayons r pertinents, la direction 0->r doit être proche de 0->opt(P).

Rapport détaillé, résultats numériques:
www.optimization-online.org/DB_FILE/2013/09/4056.pdf

Réfs:
[1] O.Briant, C.Lemaréchal, P.Meurdesoif, S.Michel, N.Perrot, F.Vanderbeck.
Comparison of bundle and classical column generation. Math Prog, 113:299-344,2008.