| In practice, many large-scale linear programming problems are too large to be solved effectively due to the computer's speed and/or memory limitation, even though today's computers have many more capabilities than before. Algorithms are exploited to solve such large linear programming problems, either in the sequential or parallel computation environment. This study focuses on two parallel algorithms for solving large-scale linear programming problems efficiently.; The first parallel decomposition algorithm discussed in this study is from the theory problems in a special block-angular structure. The theory or the decomposition principle is first examined. Since the subproblems of a linear programming problem can be in any of the three possible cases---optimal solution case, unbounded solution case and no solution case, examples are provided for solving the problem when its subproblems are in any of these cases. The concept of extreme directions is discussed due to its direct connection with the unbounded solution case. A parallel computation code, which can handle all these cases, is implemented in this study with the decomposition principle theory and its performance is tested for large-scale linear programming problems.; Only the problems in the special block-angular structure can be solved with the decomposition principle. For general linear programming problems, this study proposed a new decomposition algorithm named "division by the interior point". The idea of this new algorithm is as follows: with a found interior point inside the feasible region, divide the feasible region into multiple subregions and use multiple processors to solve the problem in each subregion. This new algorithm is first demonstrated with a few small numerical examples. A parallel computation code in this new idea is implemented and tested with large-scale linear programming problems. |
