On the integration of Dantzig-Wolfe and Fenchel decompositions via directional normalizations

arXiv2303.15573MaRDI QIDQ6431045FDOQ6431045

Authors: François Lamothe, Alain Haït, Emmanuel Rachelson, Claudio Contardo, Bernard Gendron 

Publication date: 27 March 2023

Abstract: The strengthening of linear relaxations and bounds of mixed integer linear programs has been an active research topic for decades. Enumeration-based methods for integer programming like linear programming-based branch-and-bound exploit strong dual bounds to fathom unpromising regions of the feasible space. In this paper, we consider the strengthening of linear programs via a composite of Dantzig-Wolfe and Fenchel decompositions. We provide geometric interpretations of these two classical methods. Motivated by these geometric interpretations, we introduce a novel approach for solving Fenchel sub-problems and introduce a novel decomposition combining Dantzig-Wolfe and Fenchel decompositions in an original manner. We carry out an extensive computational campaign assessing the performance of the novel decomposition on the unsplittable flow problem. Very promising results are obtained when the new approach is compared to classical decomposition methods.

Has companion code repository: https://github.com/twistednerves/decomposition_paper_code

This page was built for publication: On the integration of Dantzig-Wolfe and Fenchel decompositions via directional normalizations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6431045)