Analysis of Parallelization and Implementation of the Original and a Modified Dantzig-Wolfe Decomposition Algorithm

To solve optimization problems more efficiently, we often try to find special structures in the problem. One of these structures that occurs in linear programming problems is the block-diagonal structure (A structure in the constraints of the problem). This structure can be found in scheduling problems, multi-commodity problems, etc. Dantzig-Wolfe Decomposition is an algorithm that uses this structure to divide the problem into some smaller subproblems that can be solved easier or faster and then defines a mechanism to manage the results found by these subproblems. In this paper, a modification to the algorithm is discussed. It is proposed that we can avoid solving all the subproblems in all the iterations and just look for a good subproblem instead of the best subproblem in each iteration. It may seem that we are not going the optimal way towards the optimality but numeric tests show that an outstanding improvement in performance is achieved. Then, the process of parallelization of the original and the modified algorithm is analyzed. The contribution of this paper is a modification to the Dantzig-Wolfe algorithm and the proof of cost-effectiveness of the Dantzig-Wolfe algorithm for parallelization, both theoretically and practically.In the analysis part, the complexity of the computations and the complexity of the communications in the parallel form are estimated. It is proved that the communication time complexity is proportional to the number of subproblems multiplied by the number of subproblem columns. It is also proved that the algorithm is cost-effective for parallelization by estimating the computation/communication ratio and verifying that the computation/communication ratio will grow exponentially while increasing the dimensions of the problem.Here, the focus is on Large-Scale Linear Programming Problems and since there is no bench-mark available for the general form of it, a benchmark is created for the evaluation. Of course the bench-mark is available for any further analysis. We will compare four versions of the algorithm:1. The original Dantzig-Wolfe Algorithm (sequential) 2. The modified Dantzig-Wolfe Algorithm (sequential)3. The original Dantzig-Wolfe Algorithm (parallel) 4. The modified Dantzig-Wolfe Algorithm (parallel) At the end, the results of the comparison would be presented using graphs and tables. An example is shown in the figure below. This figure shows the speedup obtained by parallelizing of the Dantzig-Wolfe algorithm.