An Alternative to Benders Decomposition : the Barycentric Method

M. Minoux, J-C. Dodu, T. Eve

IBP-Masi 1995/23: Rapport de Recherche Masi / Masi research reports
22 pages - Juillet/July 1995 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: An Alternative to Benders Decomposition : the Barycentric Method

Résumé : Cet article décrit une alternative à la méthode de décomposition de Benders, pour l'optimisation de grands problèmes décomposables avec variables couplantes. La méthode présentée peut être interprétée comme une approche de lagrangien augmenté appliquée à une reformulation du problème initial. Chaque sous-problème implique à la fois les variables locales et une copie des variables couplantes et un terme linéaire et quadra tique dépendant de cette dernière est ajouté à la fonction objectif locale. Au niveau du problème maître, les calculs se réduisent à un calcul de barycentre, d'où le nom de 'Méthode barycentrique'. La faisabilité relativement aux contraintes sur les variables de couplage est préservée au cours des itérations, et une preuve de convergence est donnée. On étudie également des conditions sous lesquelles la convergence linéaire est obtenue.

Abstract : This paper describess an alternative approach to Benders decomposition for large scale optimization problems formed by smaller problems tied together through coupling variables. This may be interpreted as an augmented Lagrangean approach applied to a reformulation of the problem. In the 'barycentric method 'each local subproblem to be solved involves both the local variables and a copy of the coupling variables, and a linear and quadratic term, depending on the latter, is added to the local objective function. At the master problem level, computations are shown to reduce to the determination of a barycenter (hence the name given to the method). Feasibility with respect to the constraints on the coupling variables is shown to be preserved throughout the iteration, and convergence proof of the method is given. Conditions under which linear convergence is obtained are also studied.

Publications internes Masi 1995 / Masi research reports 1995