DROPS

Artifact

Software

ng-arb implementation and MPCST

Authors: Luzie Marianczuk

Abstract

Cite as

Luzie Marianczuk. ng-arb implementation and MPCST (Software, Implementation). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23820,
   title = {{ng-arb implementation and MPCST}}, 
   author = {Marianczuk, Luzie},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:554ff8afbd05550498b755c3de500300f5f2a233}{\texttt{swh:1:dir:554ff8afbd05550498b755c3de500300f5f2a233}} (visited on 2025-07-15)},
   url = {https://gitlab.rlp.net/lumarian/ng-arbs},
   doi = {10.4230/artifacts.23820},
}

Document

DOI: 10.4230/LIPIcs.SEA.2025.24

A New Relaxation for Tree-Based Problems and Minimum Power-Cost Spanning Trees

Authors: Luzie Marianczuk, Ernst Althaus, Stefan Irnich, and Marc E. Pfetsch

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract

In this paper, we investigate lower bounds of tree-based optimization problems in order to obtain effective exact algorithms, such as branch-and-bound algorithms. Our new approach inherits the development of dynamic programming algorithms for constrained shortest path problems, as they occur as subproblems in Lagrangian relaxation algorithms and column generation-based algorithms for variants of the Vehicle Routing Problem. In the q-route relaxation, paths must satisfy a capacity constraint while the elementarity constraint is relaxed, that is, paths may contain cycles. An analogue of q-routes for tree optimization problems are q-arbs, a structure that relaxes elementarity for arborescences. We introduce a generalized formulation of q-arbs for a broad class of tree-based problems, and apply the neighborhood restrictions of so-called ng-routes to them to obtain tighter bounds. We apply the new dynamic programming approach to the Minimum Power-Cost Spanning Tree Problem and show empirically that the resulting bounds are often better than traditional LP-based lower bounds of (mixed) integer programming models.

Cite as

Luzie Marianczuk, Ernst Althaus, Stefan Irnich, and Marc E. Pfetsch. A New Relaxation for Tree-Based Problems and Minimum Power-Cost Spanning Trees. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{marianczuk_et_al:LIPIcs.SEA.2025.24,
  author =	{Marianczuk, Luzie and Althaus, Ernst and Irnich, Stefan and Pfetsch, Marc E.},
  title =	{{A New Relaxation for Tree-Based Problems and Minimum Power-Cost Spanning Trees}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{24:1--24:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.24},
  URN =		{urn:nbn:de:0030-drops-232620},
  doi =		{10.4230/LIPIcs.SEA.2025.24},
  annote =	{Keywords: lower bounds, symmetric connectivity, power range assignment, dynamic programming, optimal substructure}
}

Search Results

Documents authored by Marianczuk, Luzie

ng-arb implementation and MPCST

Abstract

Cite as

A New Relaxation for Tree-Based Problems and Minimum Power-Cost Spanning Trees

Abstract

Cite as

Thanks for your feedback!

Could not send message