Back to activities
Not ordinary seminar

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


Apr 28, 2016   12:00 PM — 01:00 PM

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.

Charles Gauvin organizer


Room 4488
André-Aisenstadt Building
Université de Montréal Campus
2920, chemin de la Tour Montréal QC H3T 1J4 Canada