Groupe d’études et de recherche en analyse des décisions

Benders decomposition from a convex analysis perspective-subgradients, epigraphs and graph approximation

Carlos Zetina Université Concordia, Canada

In this talk we revisit the Benders reformulation for Mixed Integer Linear Programs and analyze it from a convex analysis perspective. We show that the reformulation can be viewed as a convex program in the integer variables, and establish a direct relation between Benders Cuts and subgradients of the objective function. Using these concepts we present the "convex analysis intuition" of Benders iterative algorithm and of the cut selection criteria presented by Magnanti-Wong and Papadakos for selecting optimality cuts. From this analysis, we note the importance of adequately selecting the core point used in the M-W subproblem for faster convergence. Finally, we propose additional selection techniques for Benders cuts based on convex optimization concepts.

Ce séminaire s'adresse seulement aux étudiants du GERAD.
Nous vous remercions de confirmer votre présence.