Our 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.
We develop two exact cutting plane procedures to solve the problem to optimality. We conduct computational experiments to compare the results of two solution procedures with solving a compact integer programming formulation of MSelTP.
You can find all the necessary codes to replicate experiments. GenTree.cpp is the main code.