Dynamic intersection of multiple implicit Dantzig–Wolfe decompositions applied to the adjacent only quadratic minimum spanning tree problem

Dilson Lucas Pereira and Alexandre Salles da Cunha

European Journal of Operational Research, 2020, vol. 284, issue 2, 413-426

Abstract: In this paper, we introduce a dynamic Dantzig–Wolfe (DW) reformulation framework for the Adjacent Only Quadratic Minimum Spanning Tree Problem (AQMSTP). The approach is dynamic in the sense that the structures over which the DW reformulation takes place are defined on the fly and not beforehand. The idea is to dynamically convexify multiple promising regions of the domain, without explicitly formulating DW master programs over extended variable spaces and applying column generation. Instead, we use the halfspace representation of polytopes as an alternative to mathematically represent the convexified region in the original space of variables. Thus, the numerical machinery we devise for computing AQMSTP lower bounds operates in a cutting plane setting, separating projection cuts associated to the projection of the variables used in the extended DW reformulations. Our numerical experience indicates that the bounds are quite strong and the computational times are mostly spent by linear programming reoptimization and not by the separation procedures. Thus, we introduce a Lagrangian Relax-and-cut algorithm for approximating these bounds. The method is embedded in a Branch-and-Bound algorithm for the AQMSTP. Although it does not strictly dominate the previous state-of-the-art exact method, it is able to solve more instances to proven optimality and is significantly faster for the hardest AQMSTP instances in the literature.

Keywords: Combinatorial optimization; Dantzig–Wolfe decomposition; Cutting planes; Lagrangian relaxation; Spanning trees (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719310823
Full text for ScienceDirect subscribers only

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:eee:ejores:v:284:y:2020:i:2:p:413-426

DOI: 10.1016/j.ejor.2019.12.042

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().