Set-based Lagrangean decomposition methods for mathematical programming

Abstract: We present generic Lagrangean frameworks for primal (variable) and dual (constraint) decomposition algorithms for nonlinear mathematical programs with generalized inequalities.

Akin to the Dantzig-Wolfe (DW) method and the Benders Decomposition (BD), we solve a succession of restricted problems/Lagrangean relaxations in a primal setting or relaxed problems/second stage problems in a dual standpoint.

Our approach is generic in the sense that it takes as user-defined inputs

1) a structured subset of the primal (dual) feasibility set, and

2) a mechanism to update it at each iteration.

Depending on the type of subset, the master problems (primal restricted or dual relaxed problem) can have very different structures and properties.

We discuss how the structures of the set and the update mechanism influence the number of iterations required to obtain an optimal or near-optimal solution and the difficulty to solve the master problems. Our meta-algorithm presents a new generic way to prove convergence of – among others – the special cases of DW, BD and recent works arising from an 2009 article of Bienstock and Zuckerberg. We also present linearized schemes to alleviate the computational burden of solving the Lagrangean relaxation in a primal setting or the relaxed problem in a dual setting.

Posted on Apr 18, 2019 in ACGO, Seminars