Quadratic assignment problem: linearizations and polynomial time solvable cases
Karesel atama problemi: doğrusallaştırmalar ve polinom zamanda çözülebilir durumlar
- Tez No: 180668
- Danışmanlar: PROF. BARBAROS TANSEL
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Karesel Atama Problemi, Doğrusallaştırma, HesaplamaZorluğu, Polinom Zamanlı Çözülebilirlik, Quadratic Assignment Problem, Linearization, ComputationalComplexity, Polynomial Time Solvability
- Yıl: 2006
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 134
Özet
ÖZETKARESEL ATAMA PROBLEM : DOĞRUSALLAŞTIRMALARVE POL NOM ZAMANDA ÇÖZÜLEB L R DURUMLARGüneş ErdoğanEndüstri Mühendisliği Bölümü DoktoraTez Yöneticisi: Prof. Barbaros TanselEkim 2006Karesel Atama Problemi (KAP) bilinen en zor kombinatoryal eniyilemeproblemlerinden biridir. QAPLIB'deki boyutu 36'yı bulan bazı testproblemlerinde başarılı çözümler elde edilmiş olsa da, tam çözüm yöntemleriboyutu 15'i geçen problemlerde genel olarak başarısız olmuştur. Bu tezde,KAP'ın ikili yapısını inceleyip yeni tamsayı programlar sunmaktayız. ?Akış-tabanlı? formülasyonlara odaklanıp, bunları geçerli eşitsizliklerle kuvvetlendirip,dallan-ve-kes algoritması ile edindiğimiz hesapsal tecrübeyi sunmaktayız.Devamla, KAP'ın Doğrusal Atama Problemine tamamen veya kısmenindirgenebilen özel hallerini sunmakta ve verilen bir problemin bu sınıfların birelemanı olup olmadığını kontrol eden prosedürler vermekteyiz. Ayrıca KAP'ınKoopmans-Beckmann formuülasyonunun polinom zamanda çözülebilir sınıflarınıortaya çıkartmaktayız. Son olarak, Bender ayrışımına dayanan kuvvetli bir altsınır sunmaktayız.
Özet (Çeviri)
ABSTRACTQUADRATIC ASSIGNMENT PROBLEM: LINEARIZATIONSAND POLYNOMIAL TIME SOLVABLE CASESGüneş ErdoğanPh.D. in Industrial EngineeringSupervisor: Prof. Barbaros TanselOctober 2006The Quadratic Assignment Problem (QAP) is one of the hardest combinatorialoptimization problems known. Exact solution attempts proposed for instances ofsize larger than 15 have been generally unsuccessful even though successfulimplementations have been reported on some test problems from the QAPLIBup to size 36. In this dissertation, we analyze the binary structure of the QAPand present new IP formulations. We focus on ?flow-based? formulations,strengthen the formulations with valid inequalities, and report computationalexperience with a branch-and-cut algorithm. Next, we present new classes ofinstances of the QAP that can be completely or partially reduced to the LinearAssignment Problem and give procedures to check whether or not an instance isan element of one of these classes. We also identify classes of instances of theKoopmans-Beckmann form of the QAP that are solvable in polynomial time.Lastly, we present a strong lower bound based on Bender?s decomposition.
Benzer Tezler
- Robust set-valued estimation and its application to in-flinht alignment of sins
Dayanıklı küme değerli kestirim ve bunun gövdeye bağlı ataletsel seyrüsefer sistemlerinin uçuş sırasında hizalanması konusuna uygulanması
NİYAZİ BURAK SEYMEN
Yüksek Lisans
İngilizce
2005
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik ve Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. MÜBECCEL DEMİREKLER
- Two-finger keyboard design for turkish language
Türk dili için iki-parmak klavye tasarımı
HÜSEYİN KARATEKE
Yüksek Lisans
İngilizce
2015
Endüstri ve Endüstri MühendisliğiGaziantep ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. KÜRŞAD AĞPAK
- Karesel atama probleminin tavlama benzetimi ve paralel programlama teknikleri kullanarak çözümü
Solving quadratic assignment problem using simulated annealing and parallel programming techniques
SELAHATTİN AKKAŞ
Yüksek Lisans
Türkçe
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolPamukkale ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. KADİR KAVAKLIOĞLU
- Parallel evolutionary algorithms for quadratic assignment problem
İkinci derece atama problemi için paralel evrimsel algoritmalar
ALPER KIZIL
Yüksek Lisans
İngilizce
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYaşar ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. KORHAN KARABULUT
- A heuristic solution algorithm to quadratic assignment problem
Kareli atama problemleri için sezgisel yaklaşım
AYŞE HANDE EROL
Yüksek Lisans
İngilizce
2010
Endüstri ve Endüstri MühendisliğiMarmara ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. SEROL BULKAN