Distributed optimization of linear programs using Dantzig-Wolfe decomposition

his thesis studies the optimization of block-angular linear programs using distributed computers. Our approach is based on the Dantzig-Wolfe decomposition algorithm. In a Dantzig-Wolfe decomposition, a block-angular linear program with R blocks is decomposed into R+1 semi-autonomous processes. One of them is the coordinating process which generates prices, and the remaining R processes will respond to the prices through the submission of proposals. Since these processes can be executed concurrently and asynchronously, the control of the flow of prices and proposals information among the processes is critical to the rate the entire system achieves optimality. How does the control of information flow affect the dynamics of the concurrent processes ? This is the subject of our study.

An information scheme in a distributed Dantzig-Wolfe decomposition controls the timing of the availability and utilization of the prices and proposals information. We focus on four information control schemes: the Basic Information Scheme (BIS), the Early Termination Information Scheme (ETIS), the Early Start Information Scheme (ESIS) and the Intermediate Prices Information Scheme (IPIS). The efficiency, load-balance, and communication requirements of using distributed Dantzig-Wolfe decomposition to solve block-angular LP's are studied. For empirical experiments, a distributed Dantzig-Wolfe decomposition algorithm with various information schemes is implemented on the CRYSTAL multicomputer at the University of Wisconsin at Madison. A set of ten test problems, obtained mostly from real applications, is used to conduct the empirical studies. Results which are important in designing and implementing distributed optimization algorithms for solving large-scale LP's are reported. These results also provide a framework for the study of information flow in many real life planning situations.