Minimum spanning tree problems with conflict constraints
Çatışma kısıtlı enküçük kapsar ağaç problemi
- Tez No: 971984
- Danışmanlar: PROF. DR. İSMAİL KUBAN ALTINEL, PROF. DR. TEMEL ÖNCAN
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Dal sınır algoritması, En küçük örten ağaç, Branch bound algorithm, Minimum spanning tree
- Yıl: 2025
- 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ı: Belirtilmemiş.
Özet
Çatışma kısıtlı enküçük kapsar ağaç problemi, enbüyük ağırlıklı kapsar küme ile enküçük kapsar ağaç problemlerinin bir birleşimidir ve NP-zor olduğu kanıtlanmıştır. Bu tez, çatışma kısıtları nedeniyle belirli kenar çiftlerinin aynı anda çözümde yer alamadığı çizgelerde bu problemi ele almaktadır. Çatışma kısıtları özellikle kaynak kısıtlamaları, düzenleyici kurallar veya fiziksel kısıtlamaların belli bağlantıların bir arada var olmasını engellediği senaryolarda, ağ tasarımı uygulamaları için çok önemlidir. Problemin karmaşık çözüm uzayını etkili bir şekilde taramak için dört farklı dal-sınır algoritması geliştirildi. Her algoritma, yenilikçi stratejiler kullanarak hesaplama verimliliğini artırmayı ve kısa sürede etkili çözümler sunmayı hedeflemektedir. Deneysel sonuçlar geliştirilen algoritmaların çok hızlı olduklarını ve yaygın olarak kullanılan bir ticari yazılımı bu açıdan geride bıraktıklarını söyleyebiliriz. Ayrıca bu tezde çatışma kısıtlarının yapısal özellikleri ve bunların çözüm uzayı üzerindeki etkileri kapsamlı biçimde çözümlenmektedir. Bulgular karmaşık kısıtlamalar altında eniyilemenin önemli olduğu telekomünikasyon, ulaştırma ve enerji dağıtım ağları gibi alanlarda geniş kapsamlı uygulama olanakları sunmaktadır. Geliştirilen yöntemler ve elde edilen bulgular hem kuramsal çalışmalarda hem de uygulamalarda karşılaşılan zorluklara yanıt vererek çatışma kısıtlı enküçük kapsar ağaç problemleri için sağlam bir temel oluşturmaktadır. Önerilen yöntemler, var olan çözüm yaklaşımlarını aşmakla kalmayıp, bilinen en iyi çözümleri iyileştirerek ayırıcı koşullar altında eniyileme ve ağ tasarımı yapmak için gelecekteki ilerlemelere de zemin hazırlamaktadır.
Özet (Çeviri)
The minimum spanning tree with conflict constraints (MSTC) problem is a combination of the maximum cardinality stable set and the minimum spanning tree problems, and it is proven to be NP-hard. This thesis investigates this problem in graphs where certain pairs of edges cannot be included simultaneously due to conflict constraints. Such constraints are crucial for applications in network design, particularly in scenarios where resource limitations, regulatory rules, or physical restrictions prevent specific connections from coexisting. We propose four distinct branch-and-bound algorithms to effectively navigate the complex solution space of this problem. Each algorithm incorporates innovative strategies to enhance computational efficiency. Experimental results indicate that the novel algorithms are very fast and outperform a widely used commercial solver. Furthermore, this thesis provides a comprehensive analysis of the structural properties of conflict constraints and their impact on the solution space. These findings have broad implications for applications in telecommunications, transportation, and energy distribution networks, where optimization under complex constraints is essential. By addressing both theoretical and practical challenges, this thesis establishes a foundational framework for computing conflict-free minimum spanning trees. The proposed methodologies not only outperform existing solution procedures but also improve best known solutions and set the stage for future advancements in optimization and network design under disjunctive conditions.
Benzer Tezler
- Using lagrangean relaxation for solving the minimum spanning tree problem with conflicts
Çatışma kısıtlı enküçük kapsar ağaç probleminin çözümü için lagrange gevşetmesinin kullanılması
ABDULSAMED KAĞIT
Yüksek Lisans
İngilizce
2023
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. İSMAİL KUBAN ALTINEL
- Essays on some combinatorial optimization problems with interval data
Verileri aralık sayılar olan bazı en iyileme problemleri üzerine denemeler
HANDE YAMAN
Yüksek Lisans
İngilizce
1998
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUSTAFA Ç. PINAR
- Minimum spanning tree construction using meta-heuristics
Meta-heuristics kullanarak minimum ayar tasarımı inşaatı
NAZHAN AHMED ABDULKAREEM
Yüksek Lisans
İngilizce
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolErciyes ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. BAHRİYE AKAY
- Derece kısıtlı minimum yayılan ağaç problemi için genetik algoritmalar
A genetic algorithm for the degree contrained minimum spannig tree problem
HANİ SH. MAHMOOD
Yüksek Lisans
Türkçe
2005
Endüstri ve Endüstri MühendisliğiGazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. FULYA ALTIPARMAK
- A comparative study of tree encodings for evolutionary computing
Evrimsel algoritmalar için ağaç yapılarının karşılaştırmalı çalışması
ESİN SAKA
Yüksek Lisans
İngilizce
2005
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. GÖKTÜRK ÜÇOLUK
DOÇ. DR. İSMAİL HAKKI TOROSLU