A Parallel Implemetation of the Original and a Modified Dantzig - Wolfe Decomposition Algorithm

Block- diagonal structure occurs frequently in real world large – scale linear programming problems such large-scale scheduling and multi – commodity flows problems. Dantzign – wolfe decomposition is used to solve such proble,s efficiently . parallelization of this algorithm seems to be useful and effective. In this paper, the parallelization of the algorithm is discussed and tested with randomly generated problems using software we have developed for this purpose. Some factors of the problem dimesion that effect the efficiency of the parallel algorithm are discussed . also a slight modification to the dantzig – wolfe decomposition procedure is proposed, discussed and test.

Keywords:

Optimization , Parallel Processing , Large - Scale programming