Geri Dön

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ı

  1. Tez No: 433956
  2. Yazar: BETÜL AHAT
  3. Danışmanlar: DOÇ. DR. ZEKİ CANER TAŞKIN, DOÇ. DR. TINAZ EKİM AŞICI
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2016
  8. Dil: İngilizce
  9. Üniversite: Boğaziçi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    İngilizce

    2019

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. YUSUF İLKER TOPCU

  2. 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

    İngilizce

    2015

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. HANDE YAMAN PATERNOTTE

  3. 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

    İngilizce

    2016

    Endüstri ve Endüstri MühendisliğiSabancı Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. NİLAY NOYAN BÜLBÜL

    DOÇ. DR. KEREM BÜLBÜL

  4. 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

    İngilizce

    2019

    Endüstri ve Endüstri MühendisliğiBoğaziçi Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. İSMAİL KUBAN ALTINEL

    PROF. DR. ZEKİ CANER TAŞKIN

  5. 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

    İngilizce

    2024

    Endüstri ve Endüstri MühendisliğiSabancı Üniversitesi

    Mühendislik ve Doğa Bilimleri Ana Bilim Dalı

    ASSISTANT PROF. AMİNE GİZEM TİNİÇ