Separable Lagrangian Decomposition for Quasi-Separable Problems

Antonio Frangioni (), Bernard Gendron () and Enrico Gorgone ()
Additional contact information
Antonio Frangioni: Università di Pisa
Bernard Gendron: Université de Montréal
Enrico Gorgone: Università degli Studi di Cagliari

A chapter in Combinatorial Optimization and Applications, 2024, pp 207-225 from Springer

Abstract: Abstract Lagrangian relaxation is a powerful technique that applies when the removal of some appropriately chosen set of “complicating” constraints makes a(n hard) optimization problem “much easier” to solve. The most common reason for this is that the relaxed problem fully decomposes in (a large number of) independent subproblems. However, a different case happens when the removal of the constraints leaves a number of blocks of semi-continuous variables without constraints between them except those involving the single binary variable commanding them. In this case the relaxation can still be easily solvable, but this involves a two-stage approach whereby the separable blocks are solved first, possibly in parallel, and only then one single problem can be solved to find the optimal value of the design variables. We call this a quasi-separable setting. While the relaxation can be efficiently solved, the fact that it boils down to what formally amounts to a single problem prevents from using techniques—disaggregated master problems, possibly with “easy components”—that allow to solve the corresponding Lagrangian dual more efficiently. We develop an ad-hoc reformulation of the standard master problem of (stabilised) cutting-plane approaches that allow to define the Lagrangian function as the explicit sum of different components, thereby better exploiting the actual structure of the problem, at the cost of introducing a smaller number of extra Lagrangian multipliers w.r.t. what would be required by standard approaches. We also highlight the connection between this reformulation of the master problem and the Lagrangian Decomposition technique. We computationally test our approach on one relevant problem with the required structure, i.e., hard Multicommodity Network Design with budget constraints on the design variables, showing that the approach can outperform state-of-the-art traditional ones.

Date: 2024
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:isochp:978-3-031-57603-4_10

Ordering information: This item can be ordered from
http://www.springer.com/9783031576034

DOI: 10.1007/978-3-031-57603-4_10

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().