Branch-and-price algorithms for the maximum weight perfect matching problem with conflict constraints
Çatışma kısıtlı en büyük ağırlıklı eşleme problemi için dal-fiyat algoritmaları
- Tez No: 693602
- Danışmanlar: PROF. DR. İSMAİL KUBAN ALTINEL, PROF. DR. TEMEL ÖNCAN
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2021
- 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ı: 86
Özet
Bu çalışmada En Büyük Ağırlıklı Tam Eşleme Probleminin genel bir hali olan Çatışma Kısıtlı En Büyük Ağırlıklı Tam Eşleme Problemini (ÇETEP) ele alıyoruz. Görece yeni bir problem olmasına karşın, moleküler biyolojiden bilgisayarlı çizime kadar birçok alanda ÇETEP olarak gösterimlenen ya da ÇETEP'i altproblem olarak kullanan uygulamalar bulunmaktadır. ÇETEP, NP-zor olduğu kanıtlanmış bir problemdir. Dolayısıyla, ÇETEP için etkin bir çözüm yaklaşımı geliştirmek, hem var olan hem de olası uygulamalar için çok önemlidir. Bilimsel yazında, çatışma kısıtları ile tanımlanmış bir dizi birleşimsel eniyileme problemi bulumaktadır. Bu çalışmaların bir kısmının Dal-Fiyat (DF) algoritmasını ile tatminkar sonuçlar verdiğini görüyoruz. Ayrıca, güncel bilgilerimize göre ÇETEP'i DF yardımıyla çözmeyi amaçlayan bir çalışma bulunmamaktadır. Bu nedenle, DF yaklaşımının ÇETEP'e nasıl uygulanabileceği sorusuna yanıt aramanın ilginç olacağını düşündük. ÇETEP için birkaç Tamsayı Programlama (TP) gösterimi önerdik, DF algoritmaları geliştirdik ve bunları programlayarak sınadık. Bulgularımıza göre bunlardan bazıları ticari çözücüler ile rekabet edebilecek başarımdadır.
Özet (Çeviri)
In this thesis, we consider the Maximum Weight Perfect Matching Problem with Conflict Constraints (MWPMC), which is a generalization of the well-known the Maximum Weight Perfect Matching Problem (MWPMP). Although MWPMC is a relatively recent problem, there are applications modeled as MWPMC or using MWPMC as a subproblem in a wide spectrum from molecular biology to computer graphics. MWPMC is proven to be NP-hard. Hence, a high-performance solution approach is crucial for both existing and potential applications. There are a number of combinatorial optimization problems in the literature involving conflict constraints. We observe that some of the related studies had satisfactory results with Branch-and-Price (B&P) algorithm. Also, no studies aiming to solve MWPMC by using B&P exist to the best of our knowledge. Therefore, we study the question of how B&P algorithm can be applied to the MWPMC. We propose several Integer Programming (IP) formulations for the MWPMC and build corresponding B&P schemes. Then, B&P algorithms are implemented and tested. According to our findings, some of the proposed schemes show performance that can compete with the commercial solvers.
Benzer Tezler
- Optimal resource allocation for delay and energy constrained wireless networks
Gecikme ve enerji kısıtlı kablosuz ağlarda optimal kaynak özgüleme
YALÇIN ŞADİ
Doktora
İngilizce
2015
Elektrik ve Elektronik MühendisliğiKoç ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. SİNEM ÇÖLERİ ERGEN
- Tam kamyon yükü gönderici iş birliğinde kararlı koalisyon seçimi
Stable coalition selection in collaborative truckload transportation procurement
NİHAT ÖNER
Doktora
Türkçe
2021
Endüstri ve Endüstri MühendisliğiTOBB Ekonomi ve Teknoloji ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ GÜLTEKİN KUYZU
- Algorithms for the integer multicommodty network design problem
Tamsayı çoklu ağ tasarımı problemleri için algoritmalar
MUSTAFA RASİM KILINÇ
Yüksek Lisans
İngilizce
2004
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
Y.DOÇ.DR. OYA EKİN KARAŞAN
- Solving the capacitated multifacility Weber problem approximately
Sınırlı sığalı çok tesisli Weber problemi için yaklaşık çözüm yöntemleri
BURAK BOYACI
Yüksek Lisans
İngilizce
2009
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Bölümü
PROF. İ. KUBAN ALTINEL
- Aksaklıklara karşı dayanıklı Havayolu Ekip Eşleme Problemi için çözüm algoritmaları ve karar destek çerçeve önerisi
Solution algorithms and a decision support framework proposal for Robust Airline Crew Pairing Problem
BÜLENT SOYKAN
Doktora
Türkçe
2015
Endüstri ve Endüstri MühendisliğiKara Harp Okulu KomutanlığıHarekat Araştırması Ana Bilim Dalı
PROF. DR. SERPİL EROL