Under mild assumptions that are satisfied for many network design models, we show that the Lagrangian dual obtained by relaxing the flow constraints is what we call “quasi-separable”. This property implies that the Dantzig-Wolfe (DW) reformulation of the Lagrangian dual exhibits two sets of convex combination constraints, one in terms of the design variables and the other in terms of the flow variables, the latter being linked to the design variables. We compare the quasi-separable DW reformulation to the standard disaggregated DW reformulation. We illustrate the concepts on a particular case, the budget-constrained multicommodity capacitated unsplittable network design problem.
Quasi-separable dantzig-wolfe reformulations for network design
Frangioni A.
;Gorgone E.
2020-01-01
Abstract
Under mild assumptions that are satisfied for many network design models, we show that the Lagrangian dual obtained by relaxing the flow constraints is what we call “quasi-separable”. This property implies that the Dantzig-Wolfe (DW) reformulation of the Lagrangian dual exhibits two sets of convex combination constraints, one in terms of the design variables and the other in terms of the flow variables, the latter being linked to the design variables. We compare the quasi-separable DW reformulation to the standard disaggregated DW reformulation. We illustrate the concepts on a particular case, the budget-constrained multicommodity capacitated unsplittable network design problem.
I metadati presenti in IRIS UNICA sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono protetti da diritto d'autore, salvo diversa indicazione.
