Show simple item record

dc.contributor.advisorHall, Julianen
dc.contributor.advisorGondzio, Jaceken
dc.contributor.authorHuangfu, Qien
dc.date.accessioned2013-10-22T13:21:27Z
dc.date.available2013-10-22T13:21:27Z
dc.date.issued2013-07-01
dc.identifier.urihttp://hdl.handle.net/1842/7952
dc.description.abstractThe dual simplex method is frequently the most efficient technique for solving linear programming (LP) problems. This thesis describes an efficient implementation of the sequential dual simplex method and the design and development of two parallel dual simplex solvers. In serial, many advanced techniques for the (dual) simplex method are implemented, including sparse LU factorization, hyper-sparse linear system solution technique, efficient approaches to updating LU factors and sophisticated dual simplex pivoting rules. These techniques, some of which are novel, lead to serial performance which is comparable with the best public domain dual simplex solver, providing a solid foundation for the simplex parallelization. During the implementation of the sequential dual simplex solver, the study of classic LU factor update techniques leads to the development of three novel update variants. One of them is comparable to the most efficient established approach but is much simpler in terms of implementation, and the other two are specially useful for one of the parallel simplex solvers. In addition, the study of the dual simplex pivoting rules identifies and motivates further investigation of how hyper-sparsity maybe promoted. In parallel, two high performance simplex solvers are designed and developed. One approach, based on a less-known dual pivoting rule called suboptimization, exploits parallelism across multiple iterations (PAMI). The other, based on the regular dual pivoting rule, exploits purely single iteration parallelism (SIP). The performance of PAMI is comparable to a world-leading commercial simplex solver. SIP is frequently complementary to PAMI in achieving speedup when PAMI results in slowdown.en
dc.language.isoen
dc.publisherThe University of Edinburghen
dc.relation.hasversionJ. Hall and Q. Huangfu. A high performance dual revised simplex solver. In Proceedings of the 9th international conference on Parallel Processing and Applied Mathematics - Volume Part I, PPAM'11, pages 143{151, Berlin, Heidelberg, 2012. Springer-Verlag.en
dc.relation.hasversionQ. Huangfu and J. J. Hall. Novel update techniques for the revised simplex method. Technical Report ERGO-13-001, School of Mathematics, University of Edinburgh, 2013.en
dc.subjectlinear programmingen
dc.subjectsimplex methoden
dc.subjectparallelizationen
dc.titleHigh performance simplex solveren
dc.typeThesis or Dissertationen
dc.type.qualificationlevelDoctoralen
dc.type.qualificationnamePhD Doctor of Philosophyen


Files in this item

This item appears in the following Collection(s)

Show simple item record