Geri Dön

Decentralized decomposition methods for block angular linear and integer programming problems

Blok köşegen yapı gösteren doğrusal ve tamsayılı problemler için dağıtık parçalama yöntemleri

  1. Tez No: 459455
  2. Yazar: MÜRÜVVET ASLI AYDIN
  3. Danışmanlar: DOÇ. DR. ZEKİ CANER TAŞKIN
  4. Tez Türü: Doktora
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2016
  8. Dil: İngilizce
  9. Üniversite: Boğaziçi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Endüstri Mühendisliği Bilim Dalı
  13. Sayfa Sayısı: 115

Özet

Bu tezde blok köşegen yapı gösteren doğrusal programlama problemleri için Dağıtık Benders Ayıştırma Yöntemi ve Dağıtık Dantzig-Wolfe Ayrıştırma Yöntemi, tam sayılı programlama problemleri içinse Dağıtık L-Şekil Yöntemi sunuyoruz. Bu yöntemler bütünsel problemi, gösterdiği blok köşegen yapı özelliğinden faydalanarak herbir karar verici için altproblem-yerel ana problem ikililerine ayrıştırır. Karar vericiler bütünsel problemi kendi aralarında merkezi bir yönetime ihtiyaç duymadan, kurdukları iletişim ağı üzerinden gerekli minimum bilgi paylaşımı yaparak işbirliği ile çözerler. Bu tezdeki amacımız, merkezileşmiş bir yöntemden daha hızlı bir yöntem önermek değildir. Amacımız bütünsel problemi merkezi koordinasyon biriminin bulunmadığı ya da kabul edilmediği bir durumda yerel bilgi paylaşmadan, ortak bir fayda için diğerleri ile işbirliği yaparak çözmek isteyen karar vericiler için dağıtık bir koordinasyon yapısı sunmaktır.Doğrusal programlama problemleri için önerilen metodlar arasındaki temel fark paylaşılan bilginin niteliğidir. Dağıtık Benders Ayıştırma Yönteminde ikincil bilgi paylaşımı varken Dağıtık Dantzig-Wolfe Ayrıştırma Yönteminde birincil bilgi paylaşılır. Önerilen yöntemlerin merkezileştirme ile bulunan en iyi çözüme sonlu sayıda döngü ile yakınsadığını ispatlanmıştır. Metodların performans değerlendirmeleri yapılmıştır. Aynı zamanda karar vericiler arasındaki iletişim ağının etkileri de incelenmiştir.

Özet (Çeviri)

In this thesis, we propose \emph{Decentralized Benders decomposition} and \emph{Decentralized Dantzig-Wolfe decomposition} for block angular linear programs and \emph{Decentralized L-Shaped Method} for block angular integer programs. We exploit the block angular structure of the problem to decompose the overall problem into several subproblem-local master problem pairs, each of which is associated with an independent decision maker. Then the decision makers of equal hierarchy level solve the overall problem cooperatively by exchanging minimal required information through a peer-to-peer communication network without need of a central coordination unit. The main difference between the proposed Decentralized Benders Decomposition and Decentralized Dantzig-Wolfe Decomposition is the type of the information disclosed. While Decentralized Benders Decomposition requires exchange of dual information, in Decentralized Dantzig-Wolfe Decomposition primal information is shared. We remark that our goal is not competing with the computational speed of a centralized algorithm. Instead, we primarily aim to propose a decentralized coordination scheme for decision makers that are unwilling to reveal their local data while solving the overall problem for a mutual benefit in such a case a central coordination unit is unavailable or not accepted. We prove that the proposed methods converge to a global optimal solution in a finite number of iterations. Then we conduct computational experiments to evaluate the performance of the proposed methods. Also we investigate the impact of the underlying communication network computationally.

Benzer Tezler

  1. Kripto para birimi bitcoin ile ekonomik göstergeler arasındaki ilişkinin ekonometrik bir analizi

    An econometric analysis of the relationship between crypto currency bitcoin with economic indicator

    YASİN DERE

    Yüksek Lisans

    Türkçe

    Türkçe

    2019

    EkonomiDokuz Eylül Üniversitesi

    İktisat Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ NAGEHAN KESKİN

  2. On the use of polar decomposition in tuning decentralized PID controllers

    Desantralize PID kontrol edicilerin ayarlanmasında kutupsal dekompozisyonun kullanımı

    ÖMER KAYA

    Yüksek Lisans

    İngilizce

    İngilizce

    2000

    Kimya MühendisliğiBoğaziçi Üniversitesi

    Kimya Mühendisliği Ana Bilim Dalı

    PROF. DR. MEHMET C. ÇAMURDAN

    YRD. DOÇ. DR. AHMET ERHAN AKSOYLU

    DOÇ. DR. EŞREF EŞKİNAT

  3. Ayrık zamanlı PID ve PIR kontrolörlerin baskın kutup atama yöntemi ile tasarımı

    Design of discrete time PID and PIR controllers with dominant pole assignment

    AYŞE DUMAN MAMMADOV

    Yüksek Lisans

    Türkçe

    Türkçe

    2021

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Kontrol ve Otomasyon Mühendisliği Ana Bilim Dalı

    PROF. DR. MEHMET TURAN SÖYLEMEZ

  4. Petri ağlarında örtüşmeli ayrıştırma ve genleştirme kullanılarak kontrolör tasarımı

    Controller design on petri nets using overlapping decompositions and expansion

    AYDIN AYBAR

    Doktora

    Türkçe

    Türkçe

    2001

    Elektrik ve Elektronik MühendisliğiAnadolu Üniversitesi

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

    PROF.DR. ALTUĞ İFTAR

  5. Küresel iklim değişiminde doğal afetler ve konut tasarımı ilişkileri

    Natural disasters and housing design relations in global climate change

    LÜTFİYE ÇETİN MURAT

    Yüksek Lisans

    Türkçe

    Türkçe

    2022

    MimarlıkAksaray Üniversitesi

    Jeodezi ve Coğrafi Bilgi Sistemleri Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ HAVVA ÜLGEN BEKİŞOĞLU