Group for Research in Decision Analysis

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

Carlos Zetina Concordia University, 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.


This seminar is only open to students of GERAD.
We would highly appreciate if you could confirm your attendance.