Geri Dön

Solving hard stable marriage problems using logic-based methods

Mantık temelli yöntemler kullanarak zor istikrarlı evlilik problemlerini çözme

  1. Tez No: 762801
  2. Yazar: SELİN EYÜPOĞLU
  3. Danışmanlar: PROF. DR. ESRA ERDEM
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2022
  8. Dil: İngilizce
  9. Üniversite: Sabancı Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 87

Özet

Bu tez çalışmasında, sıralamaların eksik olabileceği (yani bazı partnerlerin tercih edilmediği) veya denklik içerebileceği (yani bazı partnerlerin eşit tercih edildiği), SMTI (eksik ve denklik içeren sıralamalarla istikrarlı evlilik problemi) adı verilen bir SM varyantını ele alıyoruz. Farklı adalet ölçülerine göre optimum istikrarlı eşleşmeleri hesaplamayı amaçlayan üç SMTI varyantını araştırıyoruz: Cinsiyet Eşitlikçi SMTI (cinsiyetler arasında memnuniyet eşitliğini maksimize eder), Eşitlikçi SMTI (tüm kişilerin tercihlerinin toplam memnuniyetini maksimize eder) ve Maksimum Kardinalite SMTI (çiftlerin sayısını maksimize eder). Çözüm kümesi programlaması, kısıtlı programlama ve önermesel gerçeklenebilirlik kullanarak SMTI'ın bu zor türevlerini çözmek için yeni bildirimsel yöntemler sunuyoruz. Yöntemlerin rastgele oluşturulmuş örnekler üzerinde ölçeklenebilirliğini deneysel olarak analiz ediyoruz. Maksimum Kardinalite SMTI için, bu yöntemleri aynı zamanda mevcut tamsayılı doğrusal programlama ve yerel arama yaklaşımlarıyla karşılaştırıyoruz. Problemler daha fazla denklik ve eksiklik içerdiğinde, bildirimsel yöntemlerin yerel arama algoritmalarına göre hesaplama açısından diğer yaklaşımlardan genel olarak daha iyi olduğunu gözlemliyoruz.

Özet (Çeviri)

Matching problems have been studied in economics, starting with the seminal paper of Gale and Shapley, which has led to a Nobel Prize in 2012, utilizing game theory methods with the goal of a mechanism design. One of the well-known matching problems is the Stable Marriage Problem (SM). In SM, for a set of n men and n women, we are given the preferences of individuals: for each man, a complete ranking of the women is specified as preferred partners; similarly, for each woman, a complete ranking of the men is specified as preferred partners. The goal is to marry all men and women (i.e., to find n couples) in such a way that marriages are stable: no man and woman in different couples prefer each other to their partners. We consider a variant of SM, called SMTI, where rankings may be incomplete (i.e., some partners are not acceptable) or may include ties (i.e., some partners are preferred equally). We investigate three hard variants of SMTI, that aim to compute optimal stable matchings with respect to different measures of fairness: Sex-Equal SMTI (maximizes the equality of satisfaction among sexes), Egalitarian SMTI (maximizes the total satisfaction of the preferences of all agents), and Max Cardinality SMTI (minimizes the number of singles). We introduce a suite of novel declarative methods to solve these hard variants of SMTI, using Answer Set Programming (ASP), Constraint Programming (CP), and Propositional Satisfiability (SAT). We empirically evaluate the scalability of methods over randomly generated instances, as the probability of incompleteness and probability of ties change. For Max Cardinality SMTI, we also compare these methods with the existing approaches based on Integer Linear Programming (ILP) and Local Search (including Hill-Climbing and Genetic Algorithms). We observe that the declarative methods (ASP, ILP, CP, SAT) are more promising compared to the local search algorithms as the problems get harder with more ties and incompleteness.

Benzer Tezler

  1. Karınca kolonisi optimizasyonu ve genetik algoritma tabanlı tramp gemi rotalama ve çizelgeleme

    Ant colony optimization and genetic algorithm based tramp ship routing and scheduling

    SEHER SUENDAM ARICI

    Yüksek Lisans

    Türkçe

    Türkçe

    2021

    Denizcilikİstanbul Teknik Üniversitesi

    Deniz Ulaştırma Mühendisliği Ana Bilim Dalı

    DOÇ. DR. EMRE AKYÜZ

  2. Mechanics, dynamics, and stability of orthogonal turn-milling operation

    Dik frezeyle tornalama işleminin mekaniği, dinamiği, ve kararlılığı

    KAVEH RAHIMZADEH BERENJI

    Doktora

    İngilizce

    İngilizce

    2022

    Makine MühendisliğiSabancı Üniversitesi

    Üretim Mühendisliği Ana Bilim Dalı

    PROF. DR. ERHAN BUDAK

  3. Artificial intelligence based and digital twin enabled aeronautical AD-HOC network management

    Yapay zeka tabanlı ve dijital ikiz destekli geçici havasal ağ yönetimi

    TUĞÇE BİLEN

    Doktora

    İngilizce

    İngilizce

    2022

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. BERK CANBERK

  4. Çok makineli güç sisteminde açısal kararlılık analizi ve kontrolör parametre optimizasyonu

    Angular stability analysis and controller parameter optimization in multi-machine power system

    SERDAR EKİNCİ

    Doktora

    Türkçe

    Türkçe

    2015

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektrik Mühendisliği Ana Bilim Dalı

    PROF. DR. AYŞEN DEMİRÖREN