Decentralized decomposition methods for block angular linear and integer programming problems
- Global styles
- Apa
- Bibtex
- Chicago Fullnote
- Help
Abstract
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. 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.
Collections