Show simple item record

dc.contributor.advisor Bixby, Robert E.
dc.creatorKilgore, Anne
dc.date.accessioned 2009-06-04T00:44:42Z
dc.date.available 2009-06-04T00:44:42Z
dc.date.issued 1994
dc.identifier.urihttps://hdl.handle.net/1911/13851
dc.description.abstract There has been limited success with parallel implementations of both the simplex method and interior point methods for solving real-world linear programs. Experience with a parallel implementation of CPLEX, a state of the art implementation of the simplex method, on an Intel distributed-memory multiprocessor machine will be described. We will exploit the structure of the class of problems arising from airline crew scheduling. A particular instance with 12,753,313 variables will be studied. This instance is too large to fit on current sequential machines in standard linear programming data structures. We will show how our implementation exploits both distributed memory and parallelism and allows the full problem to be kept in memory. Finally, we will discuss algorithmic ideas that our implementation affords us and show results for a variant of the greatest decrease algorithm, an idea suggested many years ago but never tested on linear programming problems of significant size.
dc.format.extent 64 p.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectOperations research
Mathematics
Computer science
dc.title Very large-scale linear programming: A case study in exploiting both parallelism and distributed memory
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Computer Science
thesis.degree.discipline Engineering
thesis.degree.grantor Rice University
thesis.degree.level Masters
thesis.degree.name Master of Arts
dc.identifier.citation Kilgore, Anne. "Very large-scale linear programming: A case study in exploiting both parallelism and distributed memory." (1994) Master’s Thesis, Rice University. https://hdl.handle.net/1911/13851.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record