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ığı, Doğrusal programlama, Polihedral, The Quadratic Assignment Problem, Computational Complex ity, Polyhedral Theory m, Linear programming, Quadratic assignment problem, Polyhedral
- 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ı: Belirtilmemiş.
Ö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
- 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
- Yatay kuyularda basınç düşümü ve verimliliğe etkisi
The influence of pressure drop along the wellbore on horizontal well productivity
NURTEN CAN
Yüksek Lisans
Türkçe
1997
Petrol ve Doğal Gaz Mühendisliğiİstanbul Teknik ÜniversitesiPetrol ve Doğal Gaz Mühendisliği Ana Bilim Dalı
DOÇ. DR. TURHAN YILDIZ
- Topuk-Göynükbelen (Orhaneli-Bursa) yöresi nikel oluşumlarının kökensel incelenmesi
Genetical investigation of nickel occurrences in the vicinity of Topuk-Göynükbelen, Orhaneli-Bursa
YÜKSEL ÖRGÜN
Doktora
Türkçe
1993
Jeoloji Mühendisliğiİstanbul Teknik ÜniversitesiJeoloji Ana Bilim Dalı
PROF.DR. ATİLLA AYKOL
- Picasso'nun seramik çalışmalarında konu seçimleri ve biçim araştırmaları
Başlık çevirisi yok
EREN R. OKAY
Yüksek Lisans
Türkçe
1993
Güzel SanatlarMimar Sinan Güzel Sanatlar ÜniversitesiUygulamalı Sanatlar Ana Bilim Dalı
PROF. BERİL ANILANMERT
- Optimization ıssues in automated assembly of printed circuit boards
Baskılı devre kartları otomatik dizgisinde ortaya çıkan eniyileme problemleri
EKREM DUMAN
