Integer programming approaches to the Dominating Tree Problem
Baskın Ağaç Problemi'ne tamsayılı programlama yaklaşımları
- Tez No: 441956
- Danışmanlar: YRD. DOÇ. DR. MUSTAFA KEMAL TURAL
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2016
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
G=(V,E), V'nin düğüm kümesini, E'nin kenar kümesini temsil ettiği basit, yönlendirilmemiş ve kenarları ağırlıklandırılmış bir çizge olsun. Baskın Ağaç Problemi,DT adı verilen,G üzerindeki her düğümün ya DT'ye ait olacağı ya da DT'deki düğümlerden en az birine komşu olacağı enaz ağırlıklı bir ağaç arar. Bu problem gerçek hayat uygulamaları olan NP-zor bir problemdir. Baskın Ağaç Problemi'nin çözümü endüstri ve tüketici uygulamalarında yaygın olarak kullanılan kablosuz sensör ağları için bir omurga oluşturmak için kullanılmaktadır. Bu tezde, bahsedilen problem için farklı tamsayılı programlama formülasyonları sunulmuştur. Literatürdeki bazı problem örnekleri için en iyi sonuçlar ilk defa sağlanmış, bazıları içinse bulunmuş sezgisel en iyi sonuçların en iyi olduğu gösterilmiştir. Buna ek olarak, problem çözümünde dal-kesme yöntemi de kullanılmıştır.
Özet (Çeviri)
Let G=(V,E) be a simple undirected edge-weighted graph, where V and E denote the set of vertices and edges of G, respectively. The Dominating Tree Problem (DTP) searches for a minimum weighted tree in G, say DT, such that each vertex either belongs to DT or is one-hop away from DT. This problem is an NP-hard but a practical problem. The solution of the DTP is used to construct a backbone for wireless sensor networks, which have a wide usage in many industrial and consumer applications. In this thesis, different integer programming formulations of the problem are introduced. For some instances in the literature, optimal solutions are provided for the first time and for some others best known heuristic solutions are shown to be optimal. Moreover, branch-and-cut approach is applied to the problem.
Benzer Tezler
- Demiryolu yük taşımacılığında optimum katar yükü probleminin incelenmesi
Determination of the optimum train load in railway freight transportation
SADETTİN ÖZEN
- Proses endüstrisinde proses kontrolu problemine hedef programlama ile yaklaşım ve alternatif bir HP algoritması önerisinin bir uygulama üzerinde değerlendirilmesi
An Approach with the technique of goal programming to the problem of process control in process industry and a proposed alternative algorithm for goal programming
ORHAN KURUÜZÜM
Doktora
Türkçe
1986
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ. DR. AYHAN TORAMAN
- Nonlinear seismic response of horizontally layered soil deposits
Başlık çevirisi yok
ADEL MAHMOUD AL-QURA'N
Yüksek Lisans
İngilizce
1987
Jeoloji MühendisliğiOrta Doğu Teknik ÜniversitesiYRD. DOÇ. DR. HALUK SUCUOĞLU