Integer programming formulations and cutting plane algorithms for the maximum selective tree problem
Maksimum seçmeli ağaç problemi için tamsayılı programlama formülasyonları ve kesme düzlemi algoritmaları
- Tez No: 731392
- Danışmanlar: PROF. DR. TINAZ EKİM AŞICI, PROF. DR. ZEKİ CANER TAŞKIN
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 54
Özet
Bu tezde Maksimum Tetiklenmiş Ağaç Problemi'nin bir çeşit genelleştirilmesi olarak Maksimum Seçmeli Ağaç Problemi (MSelTP) ele alınıyor. MSelTP, düğümleri kümeleştirilmiş yönsüz bir çizge üzerinde, her bir küme başına en fazla bir tane düğüm seçecek ve bu seçimin tetiklediği çizge bir ağaç olacak şekilde en çok sayıda düğüm seçebilmeyi hedefler. Bildiğimiz kadarıyla, birçok benzer optimizasyon problemi çalışılmış olmasına rağmen, MSelTP'nin daha önce çalışılmadığını söyleyebiliriz. MSelTP için biri bağlantılılık kısıtlarına dayalı, diğeri ise döngü eleme kısıtlarına dayalı olmak üzere iki tane karışık tamsayılı programlama formülasyonu önerdik. İlaveten, problemi optimum olarak çözebilmek için iki tane kesme düzlemi yöntemi geliştirdik. Bu iki çözüm yöntemini ve polinom sayıda kısıt içeren tamsayılı programlama formülasyonunu kıyaslamak amacıyla küme sayısı 25'e kadar olan, düğüm sayısı 250'ye kadar olan ve değişen yoğunluklara sahip çizgelerde hesaplamalı deneyler gerçekleştirdik. Deneylerimiz, CPAXnY algoritmasının diğer yöntemlere göre genel olarak daha iyi çalıştığına işaret etmekte, ancak düşük yoğunluklu ve kümelerindeki ortalama düğüm sayısı çok olan çizgelerde CPAX algoritmasının performansı ortalama süre bakımından daha iyi sonuç vermektedir.
Özet (Çeviri)
This thesis 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.
Benzer Tezler
- Robust network design under polyhedral traffic uncertainty
Çokyüzlü trafik belirsizliği durumunda gürbüz ağ tasarımı
AYŞEGÜL ALTIN
Doktora
İngilizce
2007
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. MUSTAFA ÇELEBİ PINAR
- Global optimization methods for optimal power flow and transmission switching problems in electric power systems
Başlık çevirisi yok
BURAK KOCUK
Doktora
İngilizce
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGeorgia Institute of TechnologyDOÇ. DR. SANTANU S. DEY
YRD. DOÇ. DR. X. ANDY SUN
- Mathematical programming approaches for two problems in energy systems
Enerji sistemlerinden iki problem için matematiksel programlama yaklaşimlari
BAHAR CENNET OKUMUŞOĞLU
Yüksek Lisans
İngilizce
2022
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ BURAK KOCUK
DR. ÖĞR. ÜYESİ BESTE BAŞÇİFTCİ
- Modeling and solving dynamic lot sizing problems under different production environment
Farklı üretim ortamlarında dinamik parti büyüklüğü belirleme problemlerinin modellenmesi ve çözümü
BURCU KUBUR ÖZBEL
Doktora
İngilizce
2022
Endüstri ve Endüstri MühendisliğiDokuz Eylül ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ADİL BAYKASOĞLU
- Second-order cone programming based methods for two variants of optimal power flow
Eniyi güç akışı probleminin iki sürümü için ikinci dereceden konik programlama temelli yöntemler
SEZEN ECE KAYACIK
Yüksek Lisans
İngilizce
2020
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ BURAK KOCUK
DR. ÖĞR. ÜYESİ TUĞÇE YÜKSEL BEDİZ