Decentralized decomposition methods for block angular linear and integer progamming problems

Abstract

In this thesis, we propose Decentralized Benders decomposition and Decentralized Dantzig-Wolfe decomposition for block angular linear programs and Decentralized LShaped 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 di erence 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 bene t 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 nite 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.