Arşiv ve Dokümantasyon Merkezi
Dijital Arşivi

Integer programming formulations and cutting plane algorithms for the maximum selective tree problem

Basit öğe kaydını göster

dc.contributor Graduate Program in Industrial Engineering.
dc.contributor.advisor Ekim, Tınaz.
dc.contributor.advisor Taşkın, Zeki Caner.
dc.contributor.author Onar, Ömer Burak.
dc.date.accessioned 2023-10-15T07:42:10Z
dc.date.available 2023-10-15T07:42:10Z
dc.date.issued 2022
dc.identifier.other IE 2022 O63
dc.identifier.uri http://digitalarchive.boun.edu.tr/handle/123456789/19797
dc.description.abstract This thesis considers the Maximum Selective Tree Problem (MSelTP) as a gen eralization 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 op timality. 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.
dc.publisher Thesis (M.S.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2022.
dc.subject.lcsh Maximum principles (Mathematics)
dc.title Integer programming formulations and cutting plane algorithms for the maximum selective tree problem
dc.format.pages x, 45 leaves


Bu öğenin dosyaları

Bu öğe aşağıdaki koleksiyon(lar)da görünmektedir.

Basit öğe kaydını göster

Dijital Arşivde Ara


Göz at

Hesabım