Integer programming formulations and benders decomposition for maximum induced matching problem
Maksimum tetiklenmiş eşleştirme problemi için tamsayı programlama formülasyonu ve benders ayrıştırması
- Tez No: 433956
- Danışmanlar: DOÇ. DR. ZEKİ CANER TAŞKIN, DOÇ. DR. TINAZ EKİM AŞICI
- 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: 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ı: 58
Özet
Bu tezde Maksimum Tetiklenmiş Eşleştirme problemini (MIM), en büyük boyuta sahip tetiklenmiş eşleştirme bulma, inceledik. Bu problem genel çizgeler için NP-zor'dur. Literatürde bulunan formülasyonlardan daha az karar değişkenine sahip tamsayı programlama formülasyonu geliştirdik. Daha sonra, bu problemi düğüm-ağırlıklı çizgeler için genişleterek Maksimum Düğüm-Ağırlıklı Tetiklenmiş Eşleştirme problemini (MVWIM) tanıttık. MIM'in kenar-ağırlıklı versiyonunu tanıttık ve buna Maksimum Kenar-Ağırlıklı Tetiklenmiş Eşleştirme problemi (MEWIM) adını verdik. Literatürde bulunan formülasyonları ve bizim formülasyonumuzu MVWIM ve MEWIM örneklerini çözmek için uyarladık. Maksimum Ağırlıklı Tetiklenmiş Eşleştirme probleminin (MWIM) genelleştirilmiş versiyonunda hem düğümler hem de kenarların ağırlıklı olduğunu varsaydık ve bunun için bir tamsayı programlama formülasyonu verdik. Bu formülasyonda çok fazla karar değişkeni ve kısıt olduğundan, problemi daha küçük problemlere bölmek için Benders parçalama yaklaşımı uyguladık. Daha sonra, algoritmamızın verimliliğini geliştirmek için formülasyonumuza bazı geçerli eşitsizlikler ekledik. Metodumuzun performansını test edebilmek için, farklı yoğunluklara sahip rassal çizgeler ürettik. Sayısal sonuçlara bakarak, yaklaşımımızın literatürde bulunan diğer formülasyonlara göre orta ve büyük yoğunluğa sahip örnekleri belirgin derecede daha hızlı çözdüğü görülebilir.
Özet (Çeviri)
In this thesis, we investigate Maximum Induced Matching problem (MIM), finding an induced matching having the largest cardinality. The problem is NP-hard for general graphs. We develop a binary integer programming formulation with less decision variables compared to other formulations in the literature. Then, we extend the problem for vertex-weighted graphs and introduce Maximum Vertex-Weighted Induced Matching problem (MVWIM). We introduce edge-weighted version of MIM and call it Maximum Edge-Weighted Induced Matching problem (MEWIM). We adapt formulations found in the literature and our formulation to solve MVWIM and MEWIM instances. In generalized version of Maximum Weighted Induced Matching problem (MWIM), we assume both vertices and edges have weights, and give a binary integer programming formulation for it. Since it has many decision variables and constraints, we implement Benders decomposition approach to partition the problem into smaller problems. Then, we add some valid inequalities to our formulation to improve the efficiency of our algorithm. To test the performance of our methodology, we generate random graphs with different densities. By looking at computational results, it can be seen that our approach solves instances with medium and large densities significantly faster than other methods in the literature.
Benzer Tezler
- Uncapacitated multiple allocation hub location problem under congestion
Trafik sıkışıklığı altında çok atamalı kapasite kısıtsız ana dağıtım üssü yerleşim problemi
ÇAĞRI ÖZGÜN KİBİROĞLU
Doktora
İngilizce
2019
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. YUSUF İLKER TOPCU
- Hub location problems under polyhedral demand uncertainty
Çokyüzlü talep belirsizliği altında ADÜ yer seçimi problemleri
MERVE MERAKLI
Yüksek Lisans
İngilizce
2015
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. HANDE YAMAN PATERNOTTE
- Chance-constrained stochastic programming models for humanitarian relief network design
İnsani yardım müdahale ağı tasarımı için olasılıksal kısıt içeren rassal programlama modelleri
ÖZGÜN ELÇİ
Yüksek Lisans
İngilizce
2016
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. NİLAY NOYAN BÜLBÜL
DOÇ. DR. KEREM BÜLBÜL
- The determination of treatment plans for volumetric modulated arc therapy
Hacimsel yoğunluk ayarlı ark sağaltımı planlarının belirlenmesi
PINAR DURSUN
Doktora
İngilizce
2019
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. İSMAİL KUBAN ALTINEL
PROF. DR. ZEKİ CANER TAŞKIN
- Periodic vehicle routing problems with visual attractiveness and driver consistency
Görsel elverişlilik ve sürücü tutarlılığı kısıtları ile periyodik araç rotalama problemi
SAEEDEH AHMADI BASIR
Doktora
İngilizce
2024
Endüstri ve Endüstri MühendisliğiSabancı ÜniversitesiMühendislik ve Doğa Bilimleri Ana Bilim Dalı
ASSISTANT PROF. AMİNE GİZEM TİNİÇ