License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2023.13
URN: urn:nbn:de:0030-drops-183634
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18363/
Onar, Ömer Burak ;
Ekim, Tınaz ;
Taşkın, Z. Caner
Integer Programming Formulations and Cutting Plane Algorithms for the Maximum Selective Tree Problem
Abstract
This paper considers the Maximum Selective Tree Problem (MSelTP) as a generalization of the Maximum Induced Tree problem. Given an undirected graph with a partition of its vertex set into clusters, MSelTP aims to choose the maximum number of vertices such that at most one vertex per cluster is selected and the graph induced by the selected vertices is a tree. To the best of our knowledge, MSelTP has not been studied before although several related optimization problems have been investigated in the literature. We propose two mixed integer programming formulations for MSelTP; one based on connectivity constraints, the other based on cycle elimination constraints. In addition, we develop two exact cutting plane procedures to solve the problem to optimality. On graphs with up to 25 clusters, up to 250 vertices, and varying densities, we conduct computational experiments to compare the results of two solution procedures with solving a compact integer programming formulation of MSelTP. Our experiments indicate that the algorithm CPAXnY outperforms the other procedures overall except for graphs with low density and large cluster size, and that the algorithm CPAX yields better results in terms of the average time of instances optimally solved and the overall average time.
BibTeX - Entry
@InProceedings{onar_et_al:LIPIcs.SEA.2023.13,
author = {Onar, \"{O}mer Burak and Ekim, T{\i}naz and Ta\c{s}k{\i}n, Z. Caner},
title = {{Integer Programming Formulations and Cutting Plane Algorithms for the Maximum Selective Tree Problem}},
booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)},
pages = {13:1--13:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-279-2},
ISSN = {1868-8969},
year = {2023},
volume = {265},
editor = {Georgiadis, Loukas},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18363},
URN = {urn:nbn:de:0030-drops-183634},
doi = {10.4230/LIPIcs.SEA.2023.13},
annote = {Keywords: maximum induced tree, selective tree, cutting plane, separation algorithm, mixed integer programming}
}
