Parallel bundle-based decomposition for large-scale structured mathematical programming problems

This paper presents parallel bundle-based decomposition algorithms to solve a class of structured large-scale convex optimization problems. An example in this class of problems is the block-angular linear programming problem. By dualizing, the paper transforms the original problem to an unconstrained nonsmooth concave optimization problem which is in turn solved by using a modified bundle method. Further, this dual problem consists of a collection of smaller independent subproblems which give rise to the parallel algorithms. The paper discusses the implementation on the CRYSTAL multi-computer. Finally, it presents computational experience with block-angular linear programming problems and observes that more than 70% efficiency can be obtained using up to eleven processors for one group of test problems, and more than 60% efficiency can be obtained for relatively smaller problems using up to five processors for another group of problems.