Geri Dön

On the QAP polytope and a related inequality system

QAP politopu ve ilgili bir doğrusal eşitsizlikler sistemi

  1. Tez No: 58578
  2. Yazar: BEŞİR UMUT AMCAOĞLU
  3. Danışmanlar: DOÇ. DR. BARBAROS TANSEL
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Karesel Atama Problemi, Hesaplama Karmaşıklığı, The Quadratic Assignment Problem, Computational Complex ity, Polyhedral Theory m
  7. Yıl: 1997
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    İngilizce

    2016

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. AHMET COŞAR

  2. 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

    İngilizce

    2010

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolDoğuş Üniversitesi

    Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı

    DOÇ. DR. EKREM DUMAN

  3. 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

    Türkçe

    2016

    Jeoloji Mühendisliğiİstanbul Teknik Üniversitesi

    Jeoloji Mühendisliği Ana Bilim Dalı

    DOÇ. DR. EMİN ÇİFTÇİ

  4. 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

    Yüksek Lisans

    İngilizce

    İngilizce

    1997

    Endüstri ve Endüstri MühendisliğiBoğaziçi Üniversitesi

    PROF. DR. İLHAN OR

  5. 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

    Türkçe

    2008

    Endüstri ve Endüstri Mühendisliğiİstanbul Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. EKREM MANİSALI