Geri Dön

Quadratic assignment problem: linearizations and polynomial time solvable cases

Karesel atama problemi: doğrusallaştırmalar ve polinom zamanda çözülebilir durumlar

PDF İndir

  1. Tez No: 180668
  2. Yazar: GÜNEŞ ERDOĞAN
  3. Danışmanlar: PROF. BARBAROS TANSEL
  4. Tez Türü: Doktora
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Karesel Atama Problemi, Doğrusallaştırma, HesaplamaZorluğu, Polinom Zamanlı Çözülebilirlik, Quadratic Assignment Problem, Linearization, ComputationalComplexity, Polynomial Time Solvability
  7. Yıl: 2006
  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ı: Belirtilmemiş.

Ö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

  1. Tez No

    167015

    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

    İngilizce

    2005

    Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik Üniversitesi

    Elektrik ve Elektronik Mühendisliği Ana Bilim Dalı

    PROF. DR. MÜBECCEL DEMİREKLER

  2. Tez No

    486795

    Parallel evolutionary algorithms for quadratic assignment problem

    İkinci derece atama problemi için paralel evrimsel algoritmalar

    ALPER KIZIL

    Yüksek Lisans

    İngilizce

    İngilizce

    2017

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYaşar Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. KORHAN KARABULUT

  3. Tez No

    275871

    A heuristic solution algorithm to quadratic assignment problem

    Kareli atama problemleri için sezgisel yaklaşım

    AYŞE HANDE EROL

    Yüksek Lisans

    İngilizce

    İngilizce

    2010

    Endüstri ve Endüstri MühendisliğiMarmara Üniversitesi

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

    YRD. DOÇ. DR. SEROL BULKAN

  4. Tez No

    442122

    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

  5. Tez No

    33480

    A Polyhedral approach to quadratic assignment problem

    Karesel atama problemine polyhedral bir yaklaşım

    AHMET SERTAÇ MURAT KÖKSALDI

    Yüksek Lisans

    İngilizce

    İngilizce

    1994

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

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

    DOÇ. DR. MUSTAFA AKGÜL

Geri Dön