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ı: 108
Ö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
- Terrain visibility and guarding problems
Arazi görünürlük ve koruma problemleri
HALUK ELİŞ
Doktora
İngilizce
2017
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. OSMAN OĞUZ
- Ranking units by target-direction-set value efficiency analysis and mixed integer programming
Hedef-yön-tespitli faydasal etkinlik analizi ve karma tam sayılı programlama ile ünitelerin sıralanması
TAYYAR BÜYÜKBAŞARAN
Yüksek Lisans
İngilizce
2005
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiPROF.DR. MURAT KÖKSALAN
- A mixed-integer programming approach to the clustering problem with an application in customer segmentation
Tam sayılı karma programlama ile kümeleme probleminin modellenmesi ve bir müşteri segmentasyonu uygulaması
BURCU SAĞLAM
Yüksek Lisans
İngilizce
2005
Endüstri ve Endüstri MühendisliğiKoç ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
Y.DOÇ.DR. METİN TÜRKAY
- A bicriteria rescheduling problem on unrelated parallel machines: Network flow and enumeration based approaches
İlgisiz paralel makinelerde iki kriterli yeniden çizelgeleme problemi: Ağ akış ve birerleme tabanlı yaklaşımlar
MELİH ÖZLEN
Doktora
İngilizce
2006
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. MERAL AZİZOĞLU
- Karma modelli düz ve U-tipi montaj hatlarının bazı özel durumlar altında dengelenmesine yönelik çözüm yaklaşımlarının geliştirilmesi
Developing solution approaches for balancing straight and U-type mixed model assembly lines under some particular conditions
NEŞE YALÇIN
Doktora
Türkçe
2011
Endüstri ve Endüstri MühendisliğiErciyes Üniversitesiİşletme Ana Bilim Dalı
PROF. DR. CEMAL ÖZGÜVEN