Search Results

Documents authored by Busch, Daniel


Document
PACE Solver Description
PACE Solver Description: A Sparse Pricer for Maximum Agreement Forests

Authors: Daniel Busch and Britta Dorn

Published in: LIPIcs, Volume 398, 21st International Symposium on Parameterized and Exact Computation (IPEC 2026)


Abstract
We briefly describe the solver "Dakopen", submitted to the heuristic track of the PACE Challenge 2026 on the Maximum Agreement Forest problem for two rooted binary trees. After applying data reduction rules, Dakopen solves the LP relaxation of a component-based formulation by column generation and then improves the incumbent in a time-limited branch-and-price phase. The pricing problem is a maximum agreement subtree problem with weights on leaves and internal vertices. Our sparse pricer stores only vertex pairs whose subtrees share a leaf and reuses their evaluation order across dual solutions, so each pricing pass takes time linear in the number of stored pairs.

Cite as

Daniel Busch and Britta Dorn. PACE Solver Description: A Sparse Pricer for Maximum Agreement Forests. In 21st International Symposium on Parameterized and Exact Computation (IPEC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 398, pp. 37:1-37:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{busch_et_al:LIPIcs.IPEC.2026.37,
  author =	{Busch, Daniel and Dorn, Britta},
  title =	{{PACE Solver Description: A Sparse Pricer for Maximum Agreement Forests}},
  booktitle =	{21st International Symposium on Parameterized and Exact Computation (IPEC 2026)},
  pages =	{37:1--37:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-456-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{398},
  editor =	{Korhonen, Tuukka and Lampis, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2026.37},
  URN =		{urn:nbn:de:0030-drops-282100},
  doi =		{10.4230/LIPIcs.IPEC.2026.37},
  annote =	{Keywords: maximum agreement forest, column generation, pricing problem, weighted maximum agreement subtree, sparse dynamic programming, heuristic, PACE 2026}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail