Solving hard stable marriage problems using logic-based methods
Mantık temelli yöntemler kullanarak zor istikrarlı evlilik problemlerini çözme
- Tez No: 762801
- Danışmanlar: PROF. DR. ESRA ERDEM
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- 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
- 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
2021
Denizcilikİstanbul Teknik ÜniversitesiDeniz Ulaştırma Mühendisliği Ana Bilim Dalı
DOÇ. DR. EMRE AKYÜZ
- Cross-cultural management study: An exploration of Turkish expatriate business management in the Philippines
Başlık çevirisi yok
MUSTAFA İSMAİL ERTÜRK
- 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
2022
Makine MühendisliğiSabancı ÜniversitesiÜretim Mühendisliği Ana Bilim Dalı
PROF. DR. ERHAN BUDAK
- 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
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. BERK CANBERK
- Ç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
2015
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
PROF. DR. AYŞEN DEMİRÖREN