大规模稀疏线性规划投影主元算法的研究

Linear programming is broadly applied in national economy, science, technology, management, military affairs, and so on. Nowadays the globalization has been quickening its advance, as is resulting in a vast amount of large and sparse linear programming models. Aiming at solving such kind of models efficiently, this project is of great importance both.theoretically and practically. This project introduced a deficient basis, generalized the basis concept from the square m m× matrix to a rectangular s m× matrix, and thereby generalized the simplex algorithm to a eficient-basis-allowing simplex algorithm and a dual deficient-basis-allowing simplex algorithm. Theoretical analysis revealed that the new algorithms have the.convergence property similar to that of the simplex algorithm, but an exceptional characteristic of anti-degeneracy. The more degenerate a model is, the fewer columns the basis has (relative to the number of rows) and the smaller the linear s s× system solved in each iteration is (relative to the conventional m m× system); this reduces not only the negative effects of degeneracy but also the computational complexity per iteration. Moreover, this project developed a method for computing the orthogonal projection of the negative gradient of the objective function onto the null space of any matrix, which is not only a good search direction.but also good at keeping sparcity of the vectors and matrices involved. Using the LU decomposition and appropriate data structure, this project resolved in details the implementation problems of the dual deficient-basis-allowing simplex algorithm. Taking as a plactform MINOS.5.3, developed by Stanford Univesity , one of the best optimization software packages in the world a new package named DPSLP 1.0 was developed. DPSLP 1.0 was tested, and compared against MINOS 5.3 with 49 standard NETLIB test problems. It required 2511 iterations and 53.99 seconds to solve MAROS-R7, the largest of the test problems, while MINOS 5.3 required as high as 481.70 seconds, and still failed to solve the problem as no.further progress was possible for 1000 iterations on end. The new package.outperformed MINOS 5.3 unambiguously, with total CPU time ratio 2.14 for.solving all of the rest 48 test problems. Therefore, our results attainthe advanced world levels.

人类经济活动全球化趋势的加剧导致大规模稀疏线性规划的大量生产。单纯形算法和內点算法在求解此类模型上取得巨大成功，但它们仍有各自不足之处。本项目将研究新型高效算法，通过对基概念的修改和投影技术的恰当应用，在很大程度上吸收单纯型算法的和內点算法的优点而排除它们的缺点，具有重大的理论和实际意义。.