On the QAP polytope and a related inequality system
QAP politopu ve ilgili bir doğrusal eşitsizlikler sistemi
- Tez No: 58578
- Danışmanlar: DOÇ. DR. BARBAROS TANSEL
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Karesel Atama Problemi, Hesaplama Karmaşıklığı, The Quadratic Assignment Problem, Computational Complex ity, Polyhedral Theory m
- Yıl: 1997
- 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ı: 43
Özet
ÖZET QAP POLİTOPU VE İLGİLİ BİR DO?RUSAL EŞİTLİKSİZLER SİSTEMİ Beşir U. Amcaoğlu Endüstri Mühendisliği Bölümü Yüksek Lisans Tez Yöneticisi: Doç. Dr. Barbaros Ç. Tansel Ocak, 1997 Karesel Atama Problemi (QAP) NP-zor problem sınıfı içinde averaj çözülebilirliği en az ilerletilmiş olan problemdir. Kısa süre önce Oğuz (1996), "üçgen kısıtları' olarak adlandırdığı yeni kısıtlar önerdi ve bu kısıtların Gezgin Satıcı Problemi (TSP) politopunu tamamıyla tanımladığını ileri sürdü. Biz bu çalışmada üçgen kısıtlarını QAP için kullanıyoruz. Üçgen kısıtlarını içeren ve içermeyen iki ayrı formülasyonun belirlediği politoplar arasındaki ilişkileri irdeliyor ve üçgen kısıtlarının QAP politopunu tamamıyla tanımlaması için gerekli ve yeterli şartlan veriyoruz. Bu çalışmanın bir yan ürünü olarak, n = 4 için QAP politopunun üçgen kısıtları tarafından tamamıyla belirlendiğini ispatlıyoruz.
Özet (Çeviri)
ABSTRACT ON THE QAP POLYTOPE AND A RELATED INEQUALITY SYSTEM Beşir U. Amcaoğlu M.S. in Industrial Engineering Supervisor: Assoc. Prof. Barbaros Ç. Tansel January, 1997 The Quadratic Assignment Problem is computationally one of the most difficult NP-Hard problems. Recently, in 1996, Oguz introduced the so called 'triangle constraints' into an extended model of the Travelling Salesman Problem (TSP) in an attempt to give a full description of the TSP polytope. In this study, we make use of these constraints in the context of the Quadratic Assignment Problem (QAP). We discuss the relationships between the polytopes defined by the formulations with and without triangle constraints and we provide necessary and sufficient conditions for these constraints to give a full description of the QAP polytope. A by-product of our analysis is that the triangle constraints suffice to define the QAP polytope for n = 4.
Benzer Tezler
- A stagnation aware cooperative breakout local search algorithm for the quadratic assignment problem on a multi-core architecture
Çok çekirdekli bir mimari üzerinde karesel atama problemi için iş birliği yapan durgunluk bilinçli yerel arama kaçış algoritması
YAĞMUR AKSAN
Yüksek Lisans
İngilizce
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. AHMET COŞAR
- Finding the best performing solution algorithm for QAP
Karesel atama problemi için en iyi çözüm yönteminin bulunması
BURCU MÜZEYYEN KIYICIĞI
Yüksek Lisans
İngilizce
2010
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolDoğuş ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
DOÇ. DR. EKREM DUMAN
- Granitlerde mineraloji kaynaklı jeolojik sorunların araştırılması: Aksaray (İç anadolu Bölgesi-Türkiye)
The investigation of mineralogy-induced geological problems in granites: Aksaray (Central Anatolia Region - Turkey)
OSMAN SERKAN ANGI
Doktora
Türkçe
2016
Jeoloji Mühendisliğiİstanbul Teknik ÜniversitesiJeoloji Mühendisliği Ana Bilim Dalı
DOÇ. DR. EMİN ÇİFTÇİ
- The Quadratic assigment (QAP) for the optimization of the feeder configuration in the automated production of the printed circuit boards
Baskılı elektronik devre kartının otomatik üretimde besleyici konfigürasyonun karesel atama problemi ile modellenmesi
KÖKSAL ATİK
- Kuadratik atama problemlerinin çözümünde ayrık birey-koloni optimizasyonu modeli
Discrete particle swarm optimization algorithm for the quadratic assignment problem
METİN ŞATIR
Doktora
Türkçe
2008
Endüstri ve Endüstri Mühendisliğiİstanbul ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. EKREM MANİSALI