Geri Dön

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ı

  1. Tez No: 693602
  2. Yazar: ALİM BUĞRA ÇINAR
  3. Danışmanlar: PROF. DR. İSMAİL KUBAN ALTINEL, PROF. DR. TEMEL ÖNCAN
  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: 2021
  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ı: 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

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

    İngilizce

    2015

    Elektrik ve Elektronik MühendisliğiKoç Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. SİNEM ÇÖLERİ ERGEN

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

    Türkçe

    2021

    Endüstri ve Endüstri MühendisliğiTOBB Ekonomi ve Teknoloji Üniversitesi

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

    DR. ÖĞR. ÜYESİ GÜLTEKİN KUYZU

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

    İngilizce

    2004

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

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

    Y.DOÇ.DR. OYA EKİN KARAŞAN

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

    İngilizce

    2009

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

    Endüstri Mühendisliği Bölümü

    PROF. İ. KUBAN ALTINEL

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

    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